题目大意：
三个操作
D pos 将pos位置摧毁，让它和周围不相连。
Q pos 问和pos 相连的有多少个村庄。
R 修复最近摧毁的村庄。
思路分析：
树状数组记录这个区间有多少个1。
如果 [s-e] 有e-s+1个1 的话。那么这个区间是相连的。
这样的话，我们就可以用二分的办法求出与某个位置最大相连的数量。
还有这里二分
while(l<=r)
{
if(满足)
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
#include#include #include #include #define maxn 55555 using namespace std; int n,m; int c[maxn]; int lowbit(int x) { return (x&(-x)); } int sum(int x) { int ret=0; while(x>0) { ret+=c[x]; x-=lowbit(x); } return ret; } void add(int x,int d) { while(x<=n) { c[x]+=d; x+=lowbit(x); } } int top; int stack[maxn]; int main() { while(scanf("%d%d",&n,&m)!=EOF) { memset(c,0,sizeof c); for(int i=1;i<=n;i++) { add(i,1); } char str[5]; while(m--) { scanf("%s",str); if(str[0]=='D') { int pos; scanf("%d",&pos); // if(sum(pos)-sum(pos-1)==0)continue; add(pos,-1); stack[top++]=pos; } else if(str[0]=='R') { int pos=stack[--top]; add(pos,1); } else { int cur,l,r,ans,rs,re; scanf("%d",&cur); if(sum(cur)-sum(cur-1)==0) { printf("0\n"); continue; } l=cur;r=n; while(l<=r) { int mid=(l+r)>>1; if(sum(mid)-sum(cur-1)==mid-cur+1) { ans=mid; l=mid+1; } else r=mid-1; } re=ans; l=1;r=cur; while(l<=r) { int mid=(l+r)>>1; if(sum(cur)-sum(mid-1)==cur-mid+1) { ans=mid; r=mid-1; } else l=mid+1; } rs=ans; // printf("%d %d\n",re,rs); printf("%d\n",re-rs+1); } } } return 0; }