hdu1540:http://acm.hdu.edu.cn/showproblem.php?pid=1540
题意：给你一列村庄，每个村庄给一个标号，1--n，然后毁掉一些村庄，或者重建几个村庄,重建是按照毁掉的反序建的，也就是说，最新建的是最后毁掉的那个村庄。在这些过程中会有一些查询，查询pos这个村庄所在的最长的连续村庄的个数。
题解：很容易想到用线段树来维护，维护区间的最大左连续和最大右连续值，毁掉就是单点更新操作，同时把毁掉的村庄一次放入队列中，重建的时候只要从队列中取出即可。唯一难的是查询操作。一开始，我没有想到如何查询。最后只好查询了别人的代码。分几种情况， 如果pos在该区间的左连续或者右连续中，直接返回左连续或者右连续的值。如果不在，则需要判断是否在左儿子里面。若在左儿子里面，则需要判断是否在左儿子的右连续中如果在，则需要以右儿子的左端点为查询对象在右子树中 查询，然后把左儿子和右儿子的查询结果
相加，返回。如果pos在右儿子，同理。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct Node{
int left,right;
int lsum,rsum;
}node[<<];
int ans[];
int top;
int n,m;
void build(int l,int r,int idx){//普通的建树
node[idx].left=l;
node[idx].right=r;
if(l==r){
node[idx].lsum=node[idx].rsum=;
return;
}
int mid=(l+r)/;
build(l,mid,idx<<);
build(mid+,r,idx<<|);
node[idx].lsum=node[idx].rsum=r-l+;
}
void pushup(int idx){//区间左连续和右连续的维护
if(node[idx<<].lsum==node[idx<<].right-node[idx<<].left+)//左连续的处理
node[idx].lsum=node[idx<<].lsum+node[idx<<|].lsum;
else
node[idx].lsum=node[idx<<].lsum;
if(node[idx<<|].rsum==node[idx<<|].right-node[idx<<|].left+)//右连续的处理
node[idx].rsum=node[idx<<].rsum+node[idx<<|].rsum;
else
node[idx].rsum=node[idx<<|].rsum;
}
void update(int pos,int val,int idx){//单点更新
if(node[idx].left==node[idx].right){
node[idx].lsum=node[idx].rsum=val;
return;
}
int mid=(node[idx].left+node[idx].right)/;
if(mid>=pos)update(pos,val,idx<<);
else update(pos,val,idx<<|);
pushup(idx);
}
int query(int pos,int idx){//查询，分情况讨论
if(pos<=node[idx].left+node[idx].lsum-)
return node[idx].lsum;
if(pos>=node[idx].right-node[idx].rsum+)//这里无法保证pos一定在叶子节点的左连续或者右连续中，因为该村庄可能已经被毁
return node[idx].rsum;
//printf("%d\n",node[idx].left);
if(node[idx].left==node[idx].right)return node[idx].lsum;//到达叶子节点时候要返回，因为上面的条件无法保证
int mid=(node[idx].left+node[idx].right)/;
if(mid>=pos){
if(pos>=node[idx<<].right-node[idx<<].rsum+)
return query(pos,idx<<)+query(node[idx<<|].left,idx<<|);
else
return query(pos,idx<<);
}
else {
if(pos<=node[idx<<|].lsum+node[idx<<|].left-)
return query(pos,idx<<|)+query(node[idx<<].right,idx<<);
else
return query(pos,idx<<|);
}
}
int main(){
char temp;int data;
while(~scanf("%d%d",&n,&m)){
top=-;
build(,n,);
while(m--){
cin>>temp;
if(temp=='D'){
cin>>data;
ans[++top]=data;
update(data,,);
}
else if(temp=='R'){
int tt=ans[top--];
update(tt,,);
}
else{
cin>>data;
printf("%d\n",query(data,));
}
}
}
}