首页 > 代码库 > POJ2892 Tunnel Warfare

POJ2892 Tunnel Warfare

题解:

树状数组+二分裸题。

对于二分时的细节问题,要仔细分析再确定.

代码:

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>#include<set>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x))  #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int maxn=50010;const int mod=1e9+7;const int INF=1e9;int n,m,c[maxn];int pre[maxn],x,cnt;char op;int lowbit(int x){return x&-x;}void add(int x,int v){    while(x<=n){        c[x]+=v;        x+=lowbit(x);    }}int sum(int x){    int num=0;    while(x){        num+=c[x];        x-=lowbit(x);    }    return num;}int L_Bin(int l,int r){   int R=r,m,goal=r;   while(l<r){         m=(l+r)>>1;         if(sum(R)-sum(m)==R-m){              goal=m+1;              r=m;         }         else l=m+1;   }   return goal;}int R_Bin(int l,int r){   int L=l,m,goal=l;   while(l<=r){         m=(l+r)>>1;         if(sum(m)-sum(L)==m-L){              goal=m;              l=m+1;         }         else r=m-1;   }   return goal;}int main(){    while(~scanf("%d%d",&n,&m)){        CLR(c);        cnt=0;        for(int i=1;i<=n;i++) add(i,1);        for(int i=1;i<=m;i++){           scanf(" %c",&op);           if(op==D){                 scanf("%d",&x);                 add(x,-1);                 pre[cnt++]=x;           }           if(op==R) add(pre[--cnt],1);           if(op==Q){                scanf("%d",&x);                if(sum(x)-sum(x-1)==0){                    printf("0\n");                    continue;                }                 int L=L_Bin(0,x);                int R=R_Bin(x,n);                //cout<<L<<" "<<R<<endl;                printf("%d\n",R-L+1);           }        }    }    return 0;}

 

POJ2892 Tunnel Warfare