http://poj.org/problem?id=2892
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 51000
using namespace std; int stack1[maxn],top;
struct node
{
int l,r;
int len,ren;
}p[maxn*]; void up(int i)
{
p[i].len=p[i<<].len; p[i].ren=p[i<<|].ren;
if(p[i<<].len==(p[i<<].r-p[i<<].l+))
p[i].len+=p[i<<|].len;
if(p[i<<|].ren==(p[i<<|].r-p[i<<|].l+))
p[i].ren+=p[i<<].ren;
}
void build_tree(int i,int l,int r)
{
p[i].l=l; p[i].r=r;
if(l==r)
{
p[i].len=p[i].ren=;
return ;
}
int mid=(l+r)>>;
build_tree(i<<,l,mid);
build_tree(i<<|,mid+,r);
up(i);
} void update(int id,int i,int oper)
{
if(p[i].l==p[i].r)
{
p[i].len=p[i].ren=oper;
return;
}
int mid=(p[i].l+p[i].r)>>;
if(id<=mid)
update(id,i<<,oper);
else
update(id,i<<|,oper);
up(i);
} int search1(int id,int i)
{
if(p[i].l==p[i].r)
return p[i].len;
int mid=(p[i].l+p[i].r)>>;
if(id<=mid)
{
if(p[i<<].r-p[i<<].ren+<=id)
return p[i<<].ren+p[i<<|].len;
else
search1(id,i<<);
}
else
{
if(p[i<<|].len+p[i<<|].l->=id)
return p[i<<].ren+p[i<<|].len;
else
search1(id,i<<|);
}
} int main()
{
int n,q,a;
while(scanf("%d%d",&n,&q)!=EOF)
{
build_tree(,,n);
top=;
getchar();
while(q--)
{
char ch;
scanf("%c",&ch);
if(ch=='D')
{
scanf("%d",&a);
update(a,,);
stack1[top++]=a;
}
else if(ch=='Q')
{
scanf("%d",&a);
printf("%d\n",search1(a,));
}
else if(ch=='R')
{
if(top>)
{
update(stack1[--top],,);
}
}
getchar();
}
}
return ;
}