poj3667:http://poj.org/problem?id=3667
题目大意：Hotel有N（1 ≤ N ≤ 50,000）间rooms，并且所有的rooms都是连续排列在同一边，groups需要check in 房间，要求房间的编号为连续的r..r+Di-1并且r是最小的；visitors同样可能check out，并且他们每次check out都是编号为Xi ..Xi +Di-1 (1 ≤ Xi ≤ N-Di+1)的房间，题目的输入有两种样式：
1 a : groups需要check in a间编号连续的房间
2 a b ： visitors check out 房间，其中房间编号是 a…a+b-1要求对于每次request，输出为groups分配数目为a的房间中编号最小的房间编号
题解：用 线段树维护区间的连续最大值，最大左连续，最大右连续。查询时，如果当前节点的sum值大等于val，则看该区间的左连续，若左连续大等于val，直接返回left；否则，看左二子，如果左儿子的sum值大于等于val，则进入左儿子进行查询，如果不满足，再看左儿子的右连续+右儿子的左连续是否大等于val，若大于则直接返回左儿子右连续的起点值,否则进入右儿子进行查询。否则，返回0.如果返回的不是0，就进行区间更新。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 int u,v,w; 7 int n,m; 8 struct Node{ 9 int left; 10 int right; 11 int lsum,rsum,sum; 12 int lazy; 13 }node[50002*4]; 14 void build(int l,int r,int idx){ 15 node[idx].left=l; 16 node[idx].right=r; 17 node[idx].lazy=0;//lazy标记 18 if(l==r){ 19 node[idx].sum=node[idx].lsum=node[idx].rsum=1; 20 return; 21 } 22 int mid=(l+r)/2; 23 build(l,mid,idx<<1); 24 build(mid+1,r,idx<<1|1); 25 node[idx].sum=node[idx].lsum=node[idx].rsum=r-l+1; 26 } 27 void pushup(int idx){ 28 if(node[idx<<1].lsum==node[idx<<1].right-node[idx<<1].left+1) 29 node[idx].lsum=node[idx<<1].lsum+node[idx<<1|1].lsum; 30 else 31 node[idx].lsum=node[idx<<1].lsum; 32 if(node[idx<<1|1].rsum==node[idx<<1|1].right-node[idx<<1|1].left+1) 33 node[idx].rsum=node[idx<<1].rsum+node[idx<<1|1].rsum; 34 else 35 node[idx].rsum=node[idx<<1|1].rsum; 36 node[idx].sum=node[idx<<1].rsum+node[idx<<1|1].lsum; 37 node[idx].sum=max(node[idx<<1].sum,max(node[idx].sum,node[idx<<1|1].sum)); 38 } 39 void pushdown(int idx){ 40 if(node[idx].lazy==1){ 41 node[idx<<1].sum=node[idx<<1|1].sum=0; 42 node[idx<<1].lsum=node[idx<<1].rsum=0; 43 node[idx<<1|1].lsum=node[idx<<1|1].rsum=0; 44 node[idx<<1].lazy=node[idx<<1|1].lazy=1;//很重要，开始忘记往下传递问题 45 node[idx].lazy=0; 46 } 47 if(node[idx].lazy==2){ 48 node[idx<<1].lsum=node[idx<<1].rsum=node[idx<<1].sum=node[idx<<1].right-node[idx<<1].left+1; 49 node[idx<<1|1].lsum=node[idx<<1|1].rsum=node[idx<<1|1].sum=node[idx<<1|1].right-node[idx<<1|1].left+1; 50 node[idx<<1].lazy=node[idx<<1|1].lazy=2; 51 node[idx].lazy=0; 52 } 53 } 54 void update1(int l,int r,int val,int idx){ 55 if(node[idx].left==l&&node[idx].right==r&&val==1){ 56 node[idx].sum=0; 57 node[idx].lsum=node[idx].rsum=0; 58 node[idx].lazy=1; 59 return; 60 } 61 if(node[idx].left==l&&node[idx].right==r&&val==0){ 62 node[idx].sum=node[idx].right-node[idx].left+1; 63 node[idx].lsum=node[idx].rsum=node[idx].right-node[idx].left+1; 64 node[idx].lazy=2; 65 return; 66 } 67 pushdown(idx); 68 int mid=(node[idx].right+node[idx].left)/2; 69 if(mid>=r)update1(l,r,val,idx<<1); 70 else if(mid<l)update1(l,r,val,idx<<1|1); 71 else{ 72 update1(l,mid,val,idx<<1); 73 update1(mid+1,r,val,idx<<1|1); 74 } 75 pushup(idx); 76 } 77 int update2(int val,int idx){ 78 if(node[idx].sum>=val){ 79 pushdown(idx); 80 if(node[idx].lsum>=val){ 81 return node[idx].left; 82 } 83 else if(node[idx<<1].sum>=val)return update2(val,idx<<1); 84 else if(node[idx<<1].rsum+node[idx<<1|1].lsum>=val) 85 return node[idx<<1].right-node[idx<<1].rsum+1; 86 else 87 return update2(val,idx<<1|1); 88 } 89 else { 90 return 0; 91 } 92 } 93 int main(){ 94 scanf("%d%d",&n,&m); 95 build(1,n,1); 96 for(int i=1;i<=m;i++){ 97 cin>>u; 98 if(u==1){ 99 cin>>v; 100 int ans=update2(v,1); 101 printf("%d ",ans); 102 if(ans>0)//这里不要有分好，我几次就是死在了这里 103 update1(ans,ans+v-1,1,1); 104 } 105 else{ 106 cin>>v>>w; 107 update1(v,v+w-1,0,1); 108 } 109 } 110 }