做了一些区间合并，现在已经比较理解了，关键一点是要知道，任何一个连续区，不断向下，一定会被分隔开。
这道题的query，要求包含节点x的1的连续长度。如果m+1-rmax[lson]<=pos && pos<=m+lmax[rson]那么直接返回这一段，否则x所在的连续1区间必定在左子区间或右子区间，继续往下找即可。
#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=5e4;
int lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
int st[maxn+10],top;
inline int max(int a,int b){return a>b?a:b;}
void pushup(int id,int l,int r)
{
int m=(l+r)/2;
int lenl=m-l+1,lenr=r-m;
mmax[id]=max(mmax[lson],mmax[rson]);
mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
lmax[id]=lmax[lson];
rmax[id]=rmax[rson];
if(lmax[lson]==lenl) lmax[id]+=lmax[rson];
if(rmax[rson]==lenr) rmax[id]+=rmax[lson];
return;
}
void build(int id,int l,int r)
{
lmax[id]=rmax[id]=mmax[id]=r-l+1;
if(l==r) return;
int m=(l+r)/2;
build(lson,l,m);
build(rson,m+1,r);
return;
}
void update(int id,int l,int r,int pos,int v)
{
if(l==r)
{
lmax[id]=rmax[id]=mmax[id]=v;
return;
}
int m=(l+r)/2;
if(pos<=m) update(lson,l,m,pos,v);
else update(rson,m+1,r,pos,v);
pushup(id,l,r);
return;
}
int query(int id,int l,int r,int pos)
{
if(l==r) return mmax[id];
int m=(l+r)/2;
if(m+1-rmax[lson]<=pos && pos<=m+lmax[rson]) return rmax[lson]+lmax[rson];
if(pos<=m) return query(lson,l,m,pos);
else return query(rson,m+1,r,pos);
}
int main()
{
int i,j;
int n,m;
char com[5];
int x;
while(~scanf("%d%d",&n,&m))
{
top=0;
build(1,1,n);
for(i=1;i<=m;i++)
{
scanf("%s",com);
if(com[0]!=’R') scanf("%d",&x);
else
{
if(!top) continue;
update(1,1,n,st[top--],1);
}
if(com[0]==’D') update(1,1,n,x,0),st[++top]=x;
if(com[0]==’Q') printf("%d\n",query(1,1,n,x));
}
}
return 0;
}