題意：可以標(biāo)記區(qū)間上某些節(jié)點(diǎn)或者取消標(biāo)記，并查詢與x連續(xù)的未被標(biāo)記的結(jié)點(diǎn)數(shù)。
這題和Hotel類似，由于換成了單節(jié)點(diǎn)操作，不需要區(qū)間操作的延遲標(biāo)記，維護(hù)起來更方便。
#include<iostream>
#include<algorithm>
using namespace std;
int const maxn=50010;
#define LL(i) (i<<1)
#define RR(i) ((i<<1)+1)
struct node
{
int l,r;
int lval,rval;
int len()
{
return r-l+1;
}
}ST[maxn*4];
int n,m;
void build(int l,int r,int i)
{
ST[i].l=l;
ST[i].r=r;
if(l==r)
{
ST[i].lval=1;
ST[i].rval=1;
return;
}
int mid=(l+r)>>1;
build(l,mid,LL(i));
build(mid+1,r,RR(i));
ST[i].lval=ST[i].len();
ST[i].rval=ST[i].len();
}
void update(int x,int op,int i)
{
if(ST[i].l==ST[i].r)
{
if(op==1)
ST[i].lval=ST[i].rval=0;
else if(op==0)
ST[i].lval=ST[i].rval=1;
return;
}
int mid=(ST[i].l+ST[i].r)>>1;
if(x<=mid) update(x,op,LL(i));
else update(x,op,RR(i));
ST[i].lval=ST[LL(i)].lval;
ST[i].rval=ST[RR(i)].rval;
if(ST[LL(i)].lval==ST[LL(i)].len())
ST[i].lval+=ST[RR(i)].lval;
if(ST[RR(i)].rval==ST[RR(i)].len())
ST[i].rval+=ST[LL(i)].rval;
}
int Query(int x,int i)
{
if(ST[i].l==ST[i].r)
return ST[i].lval;
int mid=(ST[i].l+ST[i].r)>>1;
if(x<=mid)
{
if(x<=ST[i].lval)
return ST[i].lval;
if(x>=ST[LL(i)].r-ST[LL(i)].rval+1)
return ST[LL(i)].rval+ST[RR(i)].lval;
else return Query(x,LL(i));
}
else
{
if(x>=ST[i].r-ST[i].rval+1)
return ST[i].rval;
if(x<=ST[RR(i)].l+ST[RR(i)].lval-1)
return ST[RR(i)].lval+ST[LL(i)].rval;
else return Query(x,RR(i));
}
}
int d[maxn];
int pd=0;
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
build(1,n,1);
char op[100];
int x;
pd=0;
for(int i=0;i<m;i++)
{
scanf("%s",op);
if(op[0]=='D')
{
scanf("%d",&x);
update(x,1,1);
d[pd++]=x;
}
else if(op[0]=='Q')
{
scanf("%d",&x);
printf("%d\n",Query(x,1));
}
else
{
update(d[--pd],0,1);
}
}
}
return 0;
}