POJ 2892 Tunnel Warfare（树状数组+二分）

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int maxn = 501252 ;
int tree[maxn],data[maxn]  ;
bool vis[maxn] ;
int  n , m ;

int lowbit(int x)
{
    return (x & (-x)) ;
}

void add(int x,int value)
{
    for(int i = x ; i <= n ; i += lowbit(i))
        tree[i] += value ;
}
int get(int x)
{
    int sum = 0 ;
    for(int i = x ; i ; i -= lowbit(i))
        sum += tree[i] ;
    return sum ;
}

int binary_search(int v)
{
    int l = 1 , r = n+1 ,i = n+2;//n+2是为了防止最后一个村庄找不到的时候没有返回值
    while(l <= r)
    {
        int mid = (l + r) >> 1 ;
        if(get(mid) >= v)
        {
            r = mid-1 ;
            i = mid ;
        }
        else l = mid+1 ;
    }
    return i ;
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        int a , i = 0;
        while(m--)
        {
            getchar() ;
            char ch ;
            scanf("%c",&ch) ;
            if(ch == ‘D‘)
            {
                scanf("%d",&a) ;
                data[++i] = ++a ;//被摧毁的村庄都存在data数组里
                vis[a] = true ;
                add(a,1) ;
            }
            else if(ch == ‘Q‘)
            {
                scanf("%d",&a) ;
                a ++ ;
                if(vis[a]) printf("0\n") ;
                else
                {
                    int sum1,sum2 ;
                    a = get(a) ;
                    sum1 = binary_search(a) ;
                    sum2 = binary_search(a+1) ;
                    printf("%d\n",sum2-sum1-1) ;
                }
            }
            else if(ch == ‘R‘)
            {
                a = data[i--] ;
                vis[a] = false ;
                add(a,-1) ;
            }
        }
    }
    return 0;
}