题目链接
http://poj.org/problem?id=3667
题目
火山经营着一个停车场，假设的停车场有N车位（编号1-N）都在一条线上，最初所有车位都没停车。经常有人来定车位，
他要定连续的k(1 ≤ k ≤ N)个车位。火山要确定是否能够满足客人的要求，如果能，他要将这k个连续的车位安排在编
号最小的地方停下。若不能，则客人不停在火山的停车场。在某一时间，有些车会被车主开走了。火山的停车场很大，
火山想让学弟学妹写个程序帮助他。
Input
第1行输入 N 和 M。N是车位个数，M是（停车和开走车操作的总次数）
接下来M行，先输入操作类型（1或2）
若是1，表示有人来停车，再输入k
若是2，再输入l,r, 表示区间[l,l+r] 的车被开走了。
N (1 ≤ N ≤ 50,000) M (1 ≤ M < 50,000)
Output
当输入为1时，若火山的停车场有连续的k个车位，那么输出第一辆车停的最小的编号，否则输出0。
Sample Input
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
Sample Output
1
4
7
0
5
Hint
样例解释：停车场有10个车位，6次操作。第一个人定了3个连续的车位时，第一辆车停在1的位置（即输出）
第二次预定3个连续的车位时，第一辆车停在4的位置，因为前三个位置被人定了。同理，下个人再来定时，
只能从编号为7的车位开始停。此时（1-9）的车位都停了车，下个人在来定三个位置，就不能满足他的要求，输出0.
2 5 5。 5开始的连续5个车位都被人开走了。现在（5-10）都是空的，下个人来定时3个位置，火山就把他们安排在
起始为置为5的位置。
分析
线段树区间合并问题。
线段树问题的难点在于确定结点维护的信息以及区间更新。
lsum表示从该结点维护的区间的最左侧向右连续的最多空位数。rsum表示从该结点维护的区间的最右侧向左连续的最多空位数。sum表示该结点维护的区间的最多连续空位数。
lsum和rsum的更新直接由左右子结点的lsum和rsum更新即可。
sum的更新不仅与左右子结点的sum有关，还与左右子结点的lsum和rsum有关。这就是问题的难点所在。区间信息的更新不是那么直接，需要自己确定好需要哪些信息来完成更新。
AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define lson p*2
#define rson (p*2+1)
using namespace std;
const int maxn=7e4+100;//5e4不行？很迷...,哪位大佬知道原因，告诉我啊orz
struct node
{int l,r;//结点所表示的区间int lsum,rsum,sum;//结点信息int col;//延迟标记,-1表示不变，0表示清空，1表示覆盖
}T[maxn<<2];//四倍空间void up(int p)//由子结点回溯更新父结点
{int mid=(T[p].l+T[p].r)>>1;T[p].lsum=T[lson].lsum;T[p].rsum=T[rson].rsum;if(T[p].lsum==mid-T[p].l+1) T[p].lsum+=T[rson].lsum;//向上直接更新父结点if(T[p].rsum==T[p].r-mid) T[p].rsum+=T[lson].rsum;//向上直接更新父结点T[p].sum=max(T[lson].sum,max(T[rson].sum,T[lson].rsum+T[rson].lsum));//区间合并更新父结点，区间最大=max{左区间最大，右区间最大，区间接口}。
}
void down(int p)
{if(T[p].col==-1) return ;//不用变int mid=(T[p].l+T[p].r)>>1;T[lson].lsum=T[lson].rsum=T[lson].sum=(mid-T[p].l+1)*T[p].col; //更新左子树T[rson].lsum=T[rson].rsum=T[rson].sum=(T[p].r-mid)*T[p].col; //更新右子树T[lson].col=T[p].col;//延迟标记传递T[rson].col=T[p].col;T[p].col=-1;//清空延迟标记return ;
}
void build(int p,int l,int r)//建树
{T[p].l=l;T[p].r=r;T[p].col=-1;//延迟标记得从上到下建立int mid=(l+r)>>1;if(l==r){T[p].lsum=r-l+1;T[p].rsum=r-l+1;T[p].sum=r-l+1;return ;}build(lson,l,mid);build(rson,mid+1,r);up(p);
}
void update(int p,int x,int y,int c)
{int mid=(T[p].l+T[p].r)>>1;if(T[p].l==x && T[p].r==y){T[lson].col=T[p].col;T[rson].col=T[p].col;T[p].col=c;T[p].lsum=(y-x+1)*c;T[p].rsum=(y-x+1)*c;T[p].sum=(y-x+1)*c;return ;}down(p);if(y<=mid) update(lson,x,y,c);else if(x>mid) update(rson,x,y,c);else{update(lson,x,mid,c);update(rson,mid+1,y,c);}up(p);
}
int query(int p,int k)
{if(T[p].lsum>=k){return T[p].l;//递归终止条件}down(p);if(T[lson].sum>=k) return query(lson,k);else if(T[lson].rsum+T[rson].lsum>=k){int ans= T[lson].r-T[lson].rsum+1;return ans;}else return query(rson,k);
}
int main()
{int n,m;while(~scanf("%d%d",&n,&m)){build(1,1,n);while(m--){int op,k;scanf("%d",&op);if(op==1){scanf("%d",&k);int ans;if(T[1].sum<k){ans=0;printf("0\n");continue;}else ans=query(1,k);printf("%d\n",ans);update(1,ans,ans+k-1,0);}else{int x,y;scanf("%d%d",&x,&y);update(1,x,x+y-1,1);}}}return 0;
}