又是一道求連續區間的問題，不過這次給了連續區間的某個位置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<stdio.h>
#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<stdio.h>
#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<stdio.h>
#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 ;
int mid=l+r>>1;
build(lson);
build(rson);
}
int max(canshu){
if(l>=r&&l>=rt)return l;
if(r>=l&&r>=rt)return r;
return rt;
}
void pushup(canshu){
int mid=l+r>>1;
lv[rt]=lv[ls]+(sum[ls]==mid-l+1?lv[rs]:0);
rv[rt]=rv[rs]+(sum[rs]==r-mid?rv[ls]:0);
sum[rt]=max(sum[ls],sum[rs],rv[ls]+lv[rs]);
}
int pos,c,flag,as;
void update(canshu){
if(l==r){
tset(rt,!c);
// printf("upd: l=%d r=%d sum=%d lv=%d rv=%d\n",l,r,sum[rt],lv[rt],rv[rt]);
return ;
}
int mid=l+r>>1;
if(pos<=mid)update(lson);
else update(rson);
pushup(l,r,rt);
// printf("upd: l=%d r=%d sum=%d lv=%d rv=%d\n",l,r,sum[rt],lv[rt],rv[rt]);
}
void quer(canshu){
if(!flag)return ;
if(pos<=l){
if(sum[rt]==r-l+1)as+=sum[rt];
else as+=lv[rt],flag=0;
return ;
}
int mid=l+r>>1;
if(pos<=mid)quer(lson);
quer(rson);
}
void quel(canshu){
if(!flag)return ;
if(pos>=r){
if(sum[rt]==r-l+1)as+=sum[rt];
else as+=rv[rt],flag=0;
return ;
}
int mid=l+r>>1;
if(pos>mid)quel(rson);
quel(lson);
}
int stk[X],top;
int main(){
int n,m,i,j;
char st[3];
while(~scanf("%d%d",&n,&m)){
build(1,n,1);top=1;
while(m--){
scanf("%s",st);
if(st[0]=='R'&&top){
pos=stk[top-1];c=0;top--;
update(1,n,1);
}
if(st[0]=='D'){
scanf("%d",&pos);
stk[top++]=pos;c=1;
update(1,n,1);
}
if(st[0]=='Q'){
scanf("%d",&pos);
as=0;
flag=1;quer(1,n,1);
flag=1;quel(1,n,1);
printf("%d\n",as?as-1:0);
}
}
}
return 0;
}
#include<stdio.h>
#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 ;
int mid=l+r>>1;
build(lson);
build(rson);
}
int max(canshu){
if(l>=r&&l>=rt)return l;
if(r>=l&&r>=rt)return r;
return rt;
}
void pushup(canshu){
int mid=l+r>>1;
lv[rt]=lv[ls]+(sum[ls]==mid-l+1?lv[rs]:0);
rv[rt]=rv[rs]+(sum[rs]==r-mid?rv[ls]:0);
sum[rt]=max(sum[ls],sum[rs],rv[ls]+lv[rs]);
}
int pos,c,flag,as;
void update(canshu){
if(l==r){
tset(rt,!c);
// printf("upd: l=%d r=%d sum=%d lv=%d rv=%d\n",l,r,sum[rt],lv[rt],rv[rt]);
return ;
}
int mid=l+r>>1;
if(pos<=mid)update(lson);
else update(rson);
pushup(l,r,rt);
// printf("upd: l=%d r=%d sum=%d lv=%d rv=%d\n",l,r,sum[rt],lv[rt],rv[rt]);
}
void quer(canshu){
if(!flag)return ;
if(pos<=l){
if(sum[rt]==r-l+1)as+=sum[rt];
else as+=lv[rt],flag=0;
return ;
}
int mid=l+r>>1;
if(pos<=mid)quer(lson);
quer(rson);
}
void quel(canshu){
if(!flag)return ;
if(pos>=r){
if(sum[rt]==r-l+1)as+=sum[rt];
else as+=rv[rt],flag=0;
return ;
}
int mid=l+r>>1;
if(pos>mid)quel(rson);
quel(lson);
}
int stk[X],top;
int main(){
int n,m,i,j;
char st[3];
while(~scanf("%d%d",&n,&m)){
build(1,n,1);top=1;
while(m--){
scanf("%s",st);
if(st[0]=='R'&&top){
pos=stk[top-1];c=0;top--;
update(1,n,1);
}
if(st[0]=='D'){
scanf("%d",&pos);
stk[top++]=pos;c=1;
update(1,n,1);
}
if(st[0]=='Q'){
scanf("%d",&pos);
as=0;
flag=1;quer(1,n,1);
flag=1;quel(1,n,1);
printf("%d\n",as?as-1:0);
}
}
}
return 0;
}
