题意：两个操作 ： 1 选出靠左的长度为a的区间。
2 把从 a到a+b的区间清空。
线段树区间合并+lazy
// by caonima // hehe #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cmath> using namespace std; const int MAX= 1e5+ 10; int Lsum[MAX<< 2],Rsum[MAX<< 2],Msum[MAX<< 2]; int col[MAX<< 2]; void push_up( int o, int m) { Lsum[o]=Lsum[o<< 1]; Rsum[o]=Rsum[o<< 1| 1]; if(Lsum[o]==(m-(m>> 1))) Lsum[o]+=Lsum[o<< 1| 1]; if(Rsum[o]==(m>> 1)) Rsum[o]+=Rsum[o<< 1]; Msum[o]=max(max(Msum[o<< 1],Msum[o<< 1| 1]),Rsum[o<< 1]+Lsum[o<< 1| 1]); return ; } void push_down( int o, int m) { if(col[o]!=- 1) { col[o<< 1]=col[o<< 1| 1]=col[o]; Lsum[o<< 1]=Rsum[o<< 1]=M sum[o<< 1]= col[o] ? 0 : (m-(m>> 1)); Lsum[o<< 1| 1]=Rsum[o<< 1| 1]=Msum[o<< 1| 1]= col[o] ? 0 : ((m>> 1)); col[o]=- 1; } } void build( int L, int R, int o) { col[o]=- 1; if(L==R) { Lsum[o]=Rsum[o]=Msum[o]= 1; return ; } int mid=(L+R)>> 1; build(L,mid,o<< 1); build(mid+ 1,R,o<< 1| 1); push_up(o,R-L+ 1); } int Query( int L, int R, int o, int len) { if(L==R) { return L; } push_down(o,R-L+ 1); int mid=(L+R)>> 1; if(Msum[o<< 1]>=len) return Query(L,mid,o<< 1,len); else if(Rsum[o<< 1]+Lsum[o<< 1| 1]>=len) return mid-Rsum[o<< 1]+ 1; else return Query(mid+ 1,R,o<< 1| 1,len); push_up(o,R-L+ 1); } void Update( int L, int R, int o, int ls, int rs, int val) { if(ls<=L&&rs>=R) { Msum[o]=Lsum[o]=Rsum[o]= val ? 0 : (R-L+ 1); col[o]=val; return ; } push_down(o,R-L+ 1); int mid=(L+R)>> 1; if(ls<=mid) Update(L,mid,o<< 1,ls,rs,val); if(rs>mid) Update(mid+ 1,R,o<< 1| 1,ls,rs,val); push_up(o,R-L+ 1); } int main() { int n,m,op,v,ls,rs; while(scanf( " %d %d ",&n,&m)== 2) { build( 1,n, 1); for( int i= 0;i<m;i++) { scanf( " %d ",&op); if(op== 1) { scanf( " %d ",&v); if(Msum[ 1]<v) printf( " 0\n "); else { int res=Query( 1,n, 1,v); printf( " %d\n ",res); Update( 1,n, 1,res,res+v- 1, 1); } } else { scanf( " %d %d ",&ls,&rs); Update( 1,n, 1,ls,ls+rs- 1, 0); } } } return 0;
}