这些天一直在啃HH牛的线段树完全版里面讲得比我的结题报告好多了。弱菜飘过......
其实我只是看懂了神犇的代码，然后自己手动模拟一遍，然后把CODE默写出来.....
里面的实现还是有些不懂....
干脆自己写个注释利于理解好了.....
弱菜觉得难处理的地方就是 合并操作 PushDown 和 PushUp
故添加了注释
#include<iostream>
#define MAXN 50005
using namespace std;int lsum[MAXN<<2],msum[MAXN<<2],rsum[MAXN<<2];
int cover[MAXN<<2];int max( int a,int b ){ return a>b?a:b; }void PushUp( int rt,int m )
{lsum[rt]=lsum[rt<<1]; //当前lsum直接取左子树的lsum[]值 rsum[rt]=rsum[rt<<1|1]; //当前sum直接取右子树德rsum[]值 if( lsum[rt]==(m-(m>>1)) )lsum[rt]+=lsum[rt<<1|1];//若左子树是满的，则向右拓展 求和 if( rsum[rt]==m>>1 )rsum[rt]+=rsum[rt<<1];//若右子树是满的，则向左拓展 求和 msum[rt]=max( lsum[rt<<1|1]+rsum[rt<<1],max( msum[rt<<1],msum[rt<<1|1]) );//当前msum的值为左右子树中空闲点，和 左子树的右边和右子树的左边的和中最大值
}void PushDown( int rt,int m )
{if( cover[rt]!=-1 ){cover[rt<<1]=cover[rt<<1|1]=cover[rt]; //向子树PushDown //判断给子树赋值 lsum[rt<<1]=rsum[rt<<1]=msum[rt<<1]=cover[rt]?0:(m-(m>>1));lsum[rt<<1|1]=rsum[rt<<1|1]=msum[rt<<1|1]=cover[rt]?0:m>>1;cover[rt]=-1;//推完后还原; }
}void build( int l,int r,int rt )
{lsum[rt]=rsum[rt]=msum[rt]=r-l+1;cover[rt]=-1;if( l==r )return ; int m=(r+l)>>1;build( l,m,rt<<1 );build( m+1,r,rt<<1|1 );return ;
}void update( int l,int r,int c,int L,int R,int rt )
{if( l<=L&&R<=r ){cover[rt]=c;msum[rt]=lsum[rt]=rsum[rt]=cover[rt]?0:R-L+1;return ;}PushDown( rt,R-L+1 );int m=(L+R)>>1;if( l<=m )update( l,r,c,L,m,rt<<1 );if( r>m )update( l,r,c,m+1,R,rt<<1|1 );PushUp( rt,R-L+1);
}int query( int w,int l,int r,int rt )
{if( l==r )return l;PushDown(rt,r-l+1);int m=(l+r)>>1;if( msum[rt<<1]>=w )return query(w,l,m,rt<<1 );else if( lsum[rt<<1|1]+rsum[rt<<1]>=w ) return m-rsum[rt<<1]+1;return query( w,m+1,r,rt<<1|1 );
}int main()
{int n,m;int a,b,c;while( scanf("%d %d",&n,&m )!=EOF ){build(1,n,1);while( m-- ){scanf( "%d %d",&a,&b );if( a==1 ){if( msum[1]<b ){ printf( "0\n" );continue; }c=query( b,1,n,1 );printf( "%d\n",c );update( c,c+b-1,1,1,n,1 );}else{scanf( "%d",&c );update( b,b+c-1,0,1,n,1 );}}}return 0;
}