POJ 2892 Tunnel Warfare (樹狀數組+二分)

題目大意：

三個操作

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;
}