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=;
LL value[maxn<<],ll[maxn<<],rl[maxn<<],ml[maxn<<];//ll是rt左边连续为1的个数，rl是右边，ml是左右两边
void btree(int l,int r,int rt)
{
ll[rt]=rl[rt]=ml[rt]=r-l+;//初始化全部为1
if(l==r)return ;
int m=(l+r)>>;
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)>>;
if(k<=m)update(k,flag,ls);
else update(k,flag,rs);
if((ll[rt]=ll[rt<<])==m-l+)ll[rt]+=ll[rt<<|];//更新左边
if((rl[rt]=rl[rt<<|])==r-m)rl[rt]+=rl[rt<<];
ml[rt]=max(max(ml[rt<<],ml[rt<<|]),rl[rt<<]+ll[rt<<|]);//更新ml的值
}
LL query(int k,int l,int r,int rt)
{
if(l==r||ml[rt]==r-l+||ml[rt]==)return ml[rt];
int m=(l+r)>>;
if(k<=m)//查询点在左侧
{
if(k>m-rl[rt<<])return query(k,ls)+query(m+,rs);
else return query(k,ls);
}
else
{
if(k<m++ll[rt<<|])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(,n,);
while(m--){
char op[];
scanf("%s",&op);
if(op[]!='R')
{
scanf("%d",&k);
if(op[]=='D')
{
a.push(k);
update(k,,,n,);
}
if(op[]=='Q')printf("%lld\n",query(k,,n,));
}
else
{
update(a.top(),,,n,);
a.pop();
}
}
}
return ;
}