题目地址：http://poj.org/problem?id=3667
因为要求出1~n中有len长度的连续线段
所以线段树中至少要保存L~R的最大连续长度MaxLen
还要思考两个区间合并成一个区间时，MaxLen可能是左半边的MaxLen和右半边MaxLen取最长一个
又或者是左半边的MaxLen加右半边的MaxLen（当空的区间在中间是连起来的）
所以线段树要保存从L起向右的连续空区间长度LeftLen，和R起向左边的连续空区间长度RightLen
假设点1的儿子是2，3
1.MaxLen=max( max(2.MaxLen,3.MaxLen) , 2.RightLen+3.LeftLen)
还要保存一个标志表示是否该区间满员或者是空
AC code：688MS
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=50000+5;
const int INF=(1<<30);
struct Node{int L,R,mid;int MaxLen,LeftLen,RightLen; //L~R最大线段长度，从L开始的最大线段长都，从R开始的 int Occupied; //0无住客 ,1 满住客 Node *pLeft,*pRight;void init(){if(Occupied==1) MaxLen=LeftLen=RightLen=0;else if(Occupied==0) MaxLen=LeftLen=RightLen=R-L+1;}Node(int L=0,int R=0):L(L),R(R){pLeft=pRight=NULL;Occupied=0;mid=(L+R)/2;MaxLen=LeftLen=RightLen=R-L+1;}
}tree[maxn*2];
int nNode;
void BuildTree(Node *root,int s,int e)
{*root=Node(s,e);if(s==e) return;root->pLeft=++nNode+tree;root->pRight=++nNode+tree;BuildTree(root->pLeft,s,root->mid);BuildTree(root->pRight,root->mid+1,e);
}
void update(Node *root)
{int LO=root->pLeft->Occupied,RO=root->pRight->Occupied;int &TO=root->Occupied;if(LO==-1||RO==-1) TO=-1;else if(LO==1&&RO==1) TO=1;else if(LO==0&&RO==0) TO=0;else TO=-1;if(TO==1||TO==0) root->init();else {root->MaxLen=max(root->pLeft->MaxLen,root->pRight->MaxLen);root->MaxLen=max(root->MaxLen,root->pLeft->RightLen+root->pRight->LeftLen);root->LeftLen =root->pLeft->LeftLen;root->RightLen=root->pRight->RightLen;if(root->pLeft->Occupied==0) root->LeftLen+=root->pRight->LeftLen;if(root->pRight->Occupied==0) root->RightLen+=root->pLeft->RightLen;}
}
void Add(Node *root,int s,int e)
{if(root->Occupied!=-1&&root->L!=root->R) { //每次都要更新 root->pLeft->Occupied=root->pRight->Occupied=root->Occupied;root->pLeft->init(); root->pRight->init();}if(root->L==s&&root->R==e){root->LeftLen=root->RightLen=root->MaxLen=0;root->Occupied=1;return;}if(e<=root->mid) Add(root->pLeft,s,e);else if(s>=root->mid+1) Add(root->pRight,s,e);else {Add(root->pLeft,s,root->mid);Add(root->pRight,root->mid+1,e);}update(root);
}
void Delete(Node *root,int s,int e)
{if(root->Occupied!=-1&&root->L!=root->R) {root->pLeft->Occupied=root->pRight->Occupied=root->Occupied;root->pLeft->init(); root->pRight->init();}if(root->L==s&&root->R==e){root->Occupied=0;root->LeftLen=root->RightLen=root->MaxLen=e-s+1;return;}if(e<=root->mid) Delete(root->pLeft,s,e);else if(s>=root->mid+1) Delete(root->pRight,s,e);else {Delete(root->pLeft,s,root->mid);Delete(root->pRight,root->mid+1,e);}update(root);
}
int QueryLen(Node *root,int len)
{ if(root->Occupied!=-1&&root->L!=root->R) {root->pLeft->Occupied=root->pRight->Occupied=root->Occupied;root->pLeft->init(); root->pRight->init();}if(root->pLeft->MaxLen>=len) return QueryLen(root->pLeft ,len);else if(root->pLeft->RightLen+root->pRight->LeftLen>=len) return root->pLeft->R-root->pLeft->RightLen+1;else if(root->pRight->MaxLen>=len) return QueryLen(root->pRight,len);else return 0;
}
int main()
{int N,M,c,n,m;scanf("%d%d",&N,&M);nNode=0; BuildTree(tree,1,N);while(M--){scanf("%d",&c);if(c==1) {scanf("%d",&n);int ans=QueryLen(tree,n);cout<<ans<<endl;if(ans) Add(tree,ans,ans+n-1);}else {scanf("%d%d",&n,&m);Delete(tree,n,n+m-1);}}return 0;
}