题意：

n个村庄排成一排，3种操作。

1，摧毁某个村庄

2，问与某个村庄x直接或间接连在一起的村庄有几个（包括它自己）

3，重建最后被摧毁的村庄

用1表示村庄村庄，0表示已被摧毁，维护好区间和。对于一个询问 x ，找到最大的 x2 满足 sum(x,x2)=x2−x+1 ，还有 最小的 x1 满足sum(x1,x)=x−x1+1 ，则与它相连的村庄个数为 x2−x1+1 个。可以用二分法去找。

从样例可以看出，3操作可以进行多步撤消，用一个栈将摧毁的过程记录下来就好。

另：对于单点更新区间求和，用树状数组更快。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define debug(x) cout<<"debug "<
          
           <
           
            >1;const int maxn = 50001 << 2;int n,m;struct sgt{ int sum[maxn]; void init(int node,int L,int R){ if(L == R)sum[node] = 1; else{ MID;CHD; init(lc,L,mid); init(rc,mid+1,R); sum[node] = sum[lc]+sum[rc]; } } void update(int pos,int v,int node,int L,int R){ if(L == R){ sum[node] = v; } else { MID;CHD; if(pos <= mid) update(pos,v,lc,L,mid); else update(pos,v,rc,mid+1,R); sum[node] = sum[lc]+sum[rc]; } } int query(int from,int to,int node,int L,int R){ if(from <= L && R <= to){ return sum[node]; } MID;CHD; int ans = 0; if(from <= mid)ans += query(from,to,lc,L,mid); if(to > mid)ans += query(from,to,rc,mid+1,R); return ans; } int solve(int x){ if(query(x,x,1,1,n)==0)return 0; int ans = 0; int L = x,R = n+1; while(L < R){ MID; if(query(x,mid,1,1,n) == (mid-x+1))L = mid+1; else R = mid; } ans += L-x; L = 0,R = x; while(L < R){ MID; if(query(mid,x,1,1,n)==(x-mid+1))R = mid; else L = mid+1; } ans += x-R; //注意不要把x点记重复 return ans; }}tree;int main(){ while(scanf("%d%d",&n,&m) == 2){ tree.init(1,1,n); stack
            
              s; int ls,q; char c; while(m--){ scanf(" %c",&c); switch(c){ case 'D': scanf("%d",&ls); s.push(ls); tree.update(ls,0,1,1,n); break; case 'R': if(!s.empty()){ tree.update(s.top(),1,1,1,n); s.pop(); } break; case 'Q': scanf("%d",&q); int ans = tree.solve(q); printf("%d\n",ans); break; } } } return 0;}
            
           
          
         
        
       
      
     

版权声明：本文为博主原创文章，未经博主允许不得转载。