添加 lsum[ ] , rsum[ ] , msum[ ] 来记录从左到右的区间，从右到左的区间和最大的区间；
#include<stdio.h> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 50005 int rsum[maxn<<2],lsum[maxn<<2],msum[maxn<<2];//msum[]维护区间1…N中的最大连续区间长度 int mark[maxn<<2]; int max(int x,int y) { return x>y?x:y; } void pushup(int l,int r,int rt) { int m=(l+r)/2; lsum[rt]=lsum[rt<<1]; rsum[rt]=rsum[rt<<1|1]; msum[rt]=max(msum[rt<<1],msum[rt<<1|1]); if(lsum[rt<<1]==m-l+1) lsum[rt]=lsum[rt<<1]+lsum[rt<<1|1]; if(rsum[rt<<1|1]==r-m) rsum[rt]=rsum[rt<<1|1]+rsum[rt<<1]; msum[rt]=max(msum[rt],lsum[rt<<1|1]+rsum[rt<<1]); } void pushdown(int l,int r,int rt) { if(mark[rt]!=-1) { int len=r-l+1; mark[rt<<1]=mark[rt]; mark[rt<<1|1]=mark[rt]; if(mark[rt]==0) { lsum[rt<<1]=rsum[rt<<1]=msum[rt<<1]=0; lsum[rt<<1|1]=rsum[rt<<1|1]=msum[rt<<1|1]=0; } else { lsum[rt<<1]=rsum[rt<<1]=msum[rt<<1]=len-len/2; rsum[rt<<1|1]=lsum[rt<<1|1]=msum[rt<<1|1]=len/2; } mark[rt]=-1; } } void build(int l,int r,int rt) { mark[rt]=-1; if(l==r) { lsum[rt]=rsum[rt]=msum[rt]=1; return ; } int m=(l+r)/2; build(lson); build(rson); pushup(l,r,rt); } void updata(int L,int R,int c,int l,int r,int rt) { if(l>=L&&R>=r) { mark[rt]=c; if(mark[rt]==0) { lsum[rt]=rsum[rt]=msum[rt]=0; } else lsum[rt]=rsum[rt]=msum[rt]=r-l+1; return ; } pushdown(l,r,rt); int m=(l+r)/2; if(m>=L) updata(L,R,c,lson); if(R>m) updata(L,R,c,rson); pushup(l,r,rt); } int query(int num,int l,int r,int rt) { if(l==r) { return l; } pushdown(l,r,rt); int m=(l+r)/2; int ret; if(msum[rt<<1]>=num)//由于从最左边开始坐位子，所以rsum[rt<<1]> { return query(num,lson); } else if(lsum[rt<<1|1]+rsum[rt<<1]>=num) return m-rsum[rt<<1]+1; else return query(num,rson); } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { build(1,n,1); int a,b,c; while(m--) { scanf("%d",&a); if(a==1) { scanf("%d",&b); if(b>msum[1]) printf("0 "); else { int ret=query(b,1,n,1); printf("%d ",ret); updata(ret,ret+b-1,0,1,n,1); } } else { scanf("%d%d",&b,&c); updata(b,b+c-1,1,1,n,1); } } } }