~~~~

线段树区间合并~

两种操作:

1、输出满足连续区间最左边的值。

2、更新一段连续区间。

?

~~~~

?

#include
  
   
#include
   
     #include
    
      #define INF 0x7fffffff #define lson rt<<1,s,m #define rson rt<<1|1,m+1,e #define N 55555 using namespace std; struct node { int v; int lm,rm,sm; }tre[N<<2]; void build(int rt,int s,int e) { tre[rt].v=-1; tre[rt].lm=tre[rt].rm=tre[rt].sm=e-s+1; if(s==e) return ; int m=(s+e)>>1; build(lson); build(rson); } void pushdown(int rt,int m) //成段更新操作。 { if(tre[rt].v!=-1) { tre[rt<<1].v=tre[rt<<1|1].v=tre[rt].v; tre[rt<<1].lm=tre[rt<<1].rm=tre[rt<<1].sm=tre[rt].v? 0:m-(m>>1); tre[rt<<1|1].lm=tre[rt<<1|1].rm=tre[rt<<1|1].sm=tre[rt].v? 0:m>>1; tre[rt].v=-1; } } void pushup(int rt,int m) //区间合并操作。 { tre[rt].lm=tre[rt<<1].lm; tre[rt].rm=tre[rt<<1|1].rm; if(tre[rt].lm==m-(m>>1)) tre[rt].lm+=tre[rt<<1|1].lm; if(tre[rt].rm==(m>>1)) tre[rt].rm+=tre[rt<<1].rm; tre[rt].sm=max(tre[rt<<1].sm,max(tre[rt<<1|1].sm,tre[rt<<1].rm+tre[rt<<1|1].lm)); } int query(int n,int rt,int s,int e) { if(s==e) return s; pushdown(rt,e-s+1); int m=(s+e)>>1; //因为要输出最左边的位置。 if(tre[rt<<1].sm>=n) return query(n,lson); else if(tre[rt<<1].rm+tre[rt<<1|1].lm>=n) return m-tre[rt<<1].rm+1; //两个子区间的中间区域。 else return query(n,rson); } void update(int l,int r,int v,int rt,int s,int e) { if(l==s && r==e) { tre[rt].v=v; tre[rt].lm=tre[rt].rm=tre[rt].sm=v? 0:e-s+1; return ; } pushdown(rt,e-s+1); int m=(s+e)>>1; if(r<=m) update(l,r,v,lson); else if(l>m) update(l,r,v,rson); else { update(l,m,v,lson); update(m+1,r,v,rson); } pushup(rt,e-s+1); } int main() { int n,m; while(~scanf(%d%d,&n,&m)) { build(1,1,n); for(int i=0;i
     
      =num) { int k=query(num,1,1,n); printf(%d ,k); update(k,k+num-1,1,1,1,n); } else puts(0); } else { int k,num; scanf(%d %d,&k,&num); update(k,k+num-1,0,1,1,n); } } } return 0; } 
     
    
   
  

?