又是一道求连续区间的问题，不过这次给了连续区间的某个位置pos，
那么就可以有一种简单的方法就是求pos之前有多少个1，设置为x，
然后再求之前有x个1的位置posl,和x+1个1的位置posr，
那么连续的区间就是posr-posl-1
注意就是把0和n+1当做1，还有如果posl==pos的时候，说明pos就是1，那么连续区间就是0。
代码：
[cpp]
#include
#define ls rt*2
#define rs rt*2+1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define canshu int l,int r,int rt
#define X 200010
int sum[X],stk[X/4],pos,d,c;
void pushup(int rt){
sum[rt]=sum[ls]+sum[rs];
}
void update(canshu){
if(l==r){
sum[rt]=c;
return ;
}
int mid=l+r>>1;
if(pos<=mid)update(lson);
else update(rson);
pushup(rt);
}
void que(canshu){
if(l==r){
d=l;
return ;
}
int mid=l+r>>1;
if(c<=sum[ls])que(lson);
else {c-=sum[ls];que(rson);}
}
int quesum(canshu){
if(pos>=r)return sum[rt];
int mid=l+r>>1,as;
as=quesum(lson);
if(pos>mid)as+=quesum(rson);
return as;
}
int main(){
int i,n,m,tot,top=1;
char st[3];
scanf("%d%d",&n,&m);
n++;
while(m--){
scanf("%s",st);
if(st[0]=='D'){
scanf("%d",&pos);
c=1;stk[top++]=pos;
update(0,n,1);
}
if(st[0]=='Q'){
scanf("%d",&pos);
tot=quesum(0,n,1);
c=tot;que(0,n,1);
if(d==pos){puts("0");continue;}
c=tot+1;pos=d;
que(0,n,1);
printf("%d\n",d-pos-1);
}
if(st[0]=='R'){
pos=stk[top-1];top--;
c=0;
update(0,n,1);
}
}
return 0;
}
#include
#define ls rt*2
#define rs rt*2+1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define canshu int l,int r,int rt
#define X 200010
int sum[X],stk[X/4],pos,d,c;
void pushup(int rt){
sum[rt]=sum[ls]+sum[rs];
}
void update(canshu){
if(l==r){
sum[rt]=c;
return ;
}
int mid=l+r>>1;
if(pos<=mid)update(lson);
else update(rson);
pushup(rt);
}
void que(canshu){
if(l==r){
d=l;
return ;
}
int mid=l+r>>1;
if(c<=sum[ls])que(lson);
else {c-=sum[ls];que(rson);}
}
int quesum(canshu){
if(pos>=r)return sum[rt];
int mid=l+r>>1,as;
as=quesum(lson);
if(pos>mid)as+=quesum(rson);
return as;
}
int main(){
int i,n,m,tot,top=1;
char st[3];
scanf("%d%d",&n,&m);
n++;
while(m--){
scanf("%s",st);
if(st[0]=='D'){
scanf("%d",&pos);
c=1;stk[top++]=pos;
update(0,n,1);
}
if(st[0]=='Q'){
scanf("%d",&pos);
tot=quesum(0,n,1);
c=tot;que(0,n,1);
if(d==pos){puts("0");continue;}
c=tot+1;pos=d;
que(0,n,1);
printf("%d\n",d-pos-1);
}
if(st[0]=='R'){
pos=stk[top-1];top--;
c=0;
update(0,n,1);
}
}
return 0;
}
另外一种想法就是维护区间左端连续值，右端连续值，
然后在询问的过程中，递归的区间肯定是从左到右的，
那么从pos开始往右的每一个区间看是否全是0，如果全是0，继续求下一个区间，
否则加上这个区间的左端连续值。
同理如果每次先询问右孩子，那么区间的求解过程是从右往左的，
就可以求出pos向左连续的区间。
两个加在一起就好了。同理注意pos为1的情况。
代码：
[cpp] view plaincopyprint
#include
#define ls rt*2
#define rs rt*2+1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define canshu int l,int r,int rt
#define X 200010
int sum[X],lv[X],rv[X];
void tset(int rt,int s){
sum[rt]=lv[rt]=rv[rt]=s;
}
void build(canshu){
tset(rt,r-l+1);
if(l==r)return ;