首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。