https://vjudge.net/contest/66989#problem/I
#include<iostream> #include<cstdio> #include<cmath> #include<stack> #include<cstring> #include<algorithm> using namespace std; #define LL long long #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 const int maxn=50010; LL value[maxn<<2],ll[maxn<<2],rl[maxn<<2],ml[maxn<<2];//ll是rt左边连续为1的个数，rl是右边，ml是左右两边 void btree(int l,int r,int rt) { ll[rt]=rl[rt]=ml[rt]=r-l+1;//初始化全部为1 if(l==r)return ; int m=(l+r)>>1; btree(ls); btree(rs); } void update(int k,int flag,int l,int r,int rt)//flag=0代表摧毁，=1代表重建 { if(l==r) { ll[rt]=rl[rt]=ml[rt]=flag;//更新叶子节点的值 return ; } int m=(l+r)>>1; if(k<=m)update(k,flag,ls); else update(k,flag,rs); if((ll[rt]=ll[rt<<1])==m-l+1)ll[rt]+=ll[rt<<1|1];//更新左边 if((rl[rt]=rl[rt<<1|1])==r-m)rl[rt]+=rl[rt<<1]; ml[rt]=max(max(ml[rt<<1],ml[rt<<1|1]),rl[rt<<1]+ll[rt<<1|1]);//更新ml的值 } LL query(int k,int l,int r,int rt) { if(l==r||ml[rt]==r-l+1||ml[rt]==0)return ml[rt]; int m=(l+r)>>1; if(k<=m)//查询点在左侧 { if(k>m-rl[rt<<1])return query(k,ls)+query(m+1,rs); else return query(k,ls); } else { if(k<m+1+ll[rt<<1|1])return query(m,ls)+query(k,rs); else return query(k,rs); } } int main() { int n,m,k; while(~scanf("%d%d",&n,&m)){ stack<int>a; btree(1,n,1); while(m--){ char op[2]; scanf("%s",&op); if(op[0]!='R') { scanf("%d",&k); if(op[0]=='D') { a.push(k); update(k,0,1,n,1); } if(op[0]=='Q')printf("%lld ",query(k,1,n,1)); } else { update(a.top(),1,1,n,1); a.pop(); } } } return 0; }