题意：

给个长度为n的全为0的序列，m种操作，1 di表示求序列中最早出现的长度为di的值为0的连续子序列，并把这个连续子序列赋为1；2 xi，di表示将[xi,xi+di-1]置为0。n，m≤50000。

题解：

用一个线段树，维护三个值：最长为0连续子序列，最长为0后缀，最长为0前缀。然后注意一下合并就行了。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 150010 7 using namespace std; 8  9 inline int read(){10     char ch=getchar(); int f=1,x=0;11     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}12     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();13     return f*x;14 }15 int ls[maxn],rs[maxn],ms[maxn],len[maxn],tg[maxn],n,m;16 void update(int x){17     ms[x]=max(rs[x<<1]+ls[x<<1|1],max(ms[x<<1],ms[x<<1|1]));18     ls[x]=(ms[x<<1]==len[x<<1])?len[x<<1]+ls[x<<1|1]:ls[x<<1];19     rs[x]=(ms[x<<1|1]==len[x<<1|1])?len[x<<1|1]+rs[x<<1]:rs[x<<1|1];20 }21 void pushdown(int x){22     if(len[x]>1){23         if(tg[x]==0){24             ms[x<<1]=ls[x<<1]=rs[x<<1]=len[x<<1]; tg[x<<1]=0;25             ms[x<<1|1]=ls[x<<1|1]=rs[x<<1|1]=len[x<<1|1]; tg[x<<1|1]=0; tg[x]=-1;26         }27         if(tg[x]==1){28             ms[x<<1]=ls[x<<1]=rs[x<<1]=0; tg[x<<1]=1;29             ms[x<<1|1]=ls[x<<1|1]=rs[x<<1|1]=0; tg[x<<1|1]=1; tg[x]=-1;30         }31     }32 }33 void build(int x,int l,int r){34     len[x]=r-l+1; tg[x]=-1; if(l==r){ls[x]=rs[x]=ms[x]=1; return;}35     int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); update(x);36 }37 int query(int x,int l,int r,int v){38     pushdown(x); if(ms[x]
         
          >1;39     if(ms[x<<1]>=v)return query(x<<1,l,mid,v); if(rs[x<<1]+ls[x<<1|1]>=v)return mid-rs[x<<1]+1;40     return query(x<<1|1,mid+1,r,v);41 }42 void fill(int x,int l,int r,int ql,int qr){43     pushdown(x);44     if(ql<=l&&r<=qr){ms[x]=ls[x]=rs[x]=0; tg[x]=1; return;} int mid=(l+r)>>1;45     if(ql<=mid)fill(x<<1,l,mid,ql,qr); if(mid
          
           <<1|1,mid+1,r,ql,qr);46 update(x);47 }48 void clear(int x,int l,int r,int ql,int qr){49 pushdown(x);50 if(ql<=l&&r<=qr){ms[x]=ls[x]=rs[x]=len[x]; tg[x]=0; return;} int mid=(l+r)>>1;51 if(ql<=mid)clear(x<<1,l,mid,ql,qr); if(mid
           
            <<1|1,mid+1,r,ql,qr);52 update(x);53 }54 int main(){55 n=read(); build(1,1,n); m=read();56 inc(i,1,m){57 int x=read();58 if(x==1){ int y=read(),z=query(1,1,n,y); printf("%d\n",z); if(z)fill(1,1,n,z,z+y-1);}59 if(x==2){ int y=read(),z=read(); clear(1,1,n,y,y+z-1);}60 }61 return 0;62 }
           
          
         
        
       
      
     

 

20160926