这题卡了我很久！不过也给了我很多的启示.. 因为自己对线段树的理解还是很浅显的所以这个题也便总是过不了，一直卡着卡着。遵照三鲜的原则，现在我做题极少看别人的代码，但是又没有人可以和我一起讨论的，所以今天还是看了下别人的解题报告，因为我想不出了，看着看着我发现了一个问题----->我丫的把题目读错了！太2了！区间合并线段树已经学习的差不多了，可能会在小的细节方面出点叉子，但是对基本的线段树运用的得还不错了。认真的去体会线段树的美，二叉的精巧，与构思的美妙。还是那句话：二叉树只是一个数据结构，类似于其他的数据结构一样，要有算法的辅助才能体现得出他的美。
决定要向那些大牛们学习，做一个勤奋的好孩子~虽然和他们没得什么联系... 有目标总归是好的。
在这题中学会了使用vector容器，我编码极少用STL，也没有什么机会用。不过用起来还是挺舒服的，功能强大啊~另外对于二分查找也有了新的感悟，本来在有序的序列中，就可以不用夹逼法了，定义一个维度就OK了~因为原来看错题，导致查询工作不能使用二分查找，于是便悲催得~~
另外给我的启示就是对于二叉树，不一定非得全部放在树形结构里面做，可以另外定义变量，开始我自己想思路的时候想把所有的操作都置于树形结构中做，但是发现这样做下去很困难！实现困难，查找也麻烦。后来改成了两个一维数组来额外存贮这部分的信息，于是乎，代码实现起来也简便了。所以线段树要活学活用~
加油！！
#include<stdio.h>
#include<vector>
using namespace std;
#define MAXN 50005struct node{int ltemp,rtemp,mtemp;
}tree[MAXN<<2];int col[MAXN<<2];struct block{int s,t;block( int a,int b ){s=a,t=b;}
};vector<block> B;int max( int a,int b ){ return a>b?a:b; }void PushUp( int rt , int m )
{tree[rt].ltemp=tree[rt<<1].ltemp;tree[rt].rtemp=tree[rt<<1|1].rtemp;if( tree[rt].ltemp==m-(m>>1) )tree[rt].ltemp+=tree[rt<<1|1].ltemp;if( tree[rt].rtemp==m>>1 )tree[rt].rtemp+=tree[rt<<1].rtemp;tree[rt].mtemp=max( tree[rt<<1|1].ltemp+tree[rt<<1].rtemp,max( tree[rt<<1].mtemp,tree[rt<<1|1].mtemp) );
}void PushDown( int rt,int m )
{if( col[rt]!=-1 ){col[rt<<1]=col[rt<<1|1]=col[rt];tree[rt<<1].ltemp=tree[rt<<1].mtemp=tree[rt<<1].rtemp=col[rt]?0:(m-(m>>1));tree[rt<<1|1].ltemp=tree[rt<<1|1].mtemp=tree[rt<<1|1].rtemp=col[rt]?0:(m>>1);col[rt]=-1;}
}void build( int l,int r,int rt )
{col[rt]=-1;tree[rt].ltemp=tree[rt].mtemp=tree[rt].rtemp=r-l+1;if( l==r )return ;int m=( l+r )>>1;build( l,m,rt<<1 );build( m+1,r,rt<<1|1 );
}int query( int w,int l,int r,int rt )
{int m=( l+r )>>1;if( l==r ) return l;PushDown( rt,r-l+1 );if( tree[rt<<1].mtemp>=w )return query( w,l,m,rt<<1 );else if( tree[rt<<1|1].ltemp+tree[rt<<1].rtemp>=w )return m-tree[rt<<1].rtemp+1;elsereturn query( w,m+1,r,rt<<1|1 );}void update( int l,int r,int c,int L,int R,int rt )
{if( l<=L&&R<=r ){col[rt]=c;tree[rt].ltemp=tree[rt].mtemp=tree[rt].rtemp=col[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 Bin( int at )
{int left=0;int right=B.size()-1;int m;while( left<=right ){m=( left+right )>>1;if( at>=B[m].s )left=m+1;elseright=m-1;}return left;
}int main()
{int n,m;char com[10];int date,i;while( scanf("%d %d",&n,&m)!=EOF ){build( 1,n,1 );B.clear();while( m-- ){scanf( "%s",&com );if( com[0]=='N' ){scanf( "%d",&date );if( date>tree[1].mtemp )printf( "Reject New\n" );else{int at=query( date,1,n,1 );block k(at,at+date-1);int index=Bin(at);//printf( "%d\n",index );B.insert( B.begin()+index,k );update( at,at+date-1,1,1,n,1 );printf( "New at %d\n",at );}}else if( com[0]=='R' ){update(1,n,0,1,n,1);B.clear();printf( "Reset Now\n" );}else if( com[0]=='G' ){scanf( "%d",&date );if( date>B.size() ){printf( "Reject Get\n" );continue;}elseprintf( "Get at %d\n",B[date-1].s );}else if( com[0]=='F' ){scanf( "%d",&date );int index=Bin(date)-1;//printf( "%d\n",index );if( index!=-1 && B[index].t>=date ){printf( "Free from %d to %d\n",B[index].s,B[index].t );update( B[index].s,B[index].t,0,1,n,1 );B.erase( B.begin()+index );}elseprintf( "Reject Free\n" );}}printf( "\n" );}return 0;
}