hdu1540:http://acm.hdu.edu.cn/showproblem.php?pid=1540
题意：给你一列村庄，每个村庄给一个标号，1--n，然后毁掉一些村庄，或者重建几个村庄,重建是按照毁掉的反序建的，也就是说，最新建的是最后毁掉的那个村庄。在这些过程中会有一些查询，查询pos这个村庄所在的最长的连续村庄的个数。
题解：很容易想到用线段树来维护，维护区间的最大左连续和最大右连续值，毁掉就是单点更新操作，同时把毁掉的村庄一次放入队列中，重建的时候只要从队列中取出即可。唯一难的是查询操作。一开始，我没有想到如何查询。最后只好查询了别人的代码。分几种情况， 如果pos在该区间的左连续或者右连续中，直接返回左连续或者右连续的值。如果不在，则需要判断是否在左儿子里面。若在左儿子里面，则需要判断是否在左儿子的右连续中如果在，则需要以右儿子的左端点为查询对象在右子树中 查询，然后把左儿子和右儿子的查询结果
相加，返回。如果pos在右儿子，同理。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 using namespace std; 6 struct Node{ 7 int left,right; 8 int lsum,rsum; 9 }node[50002<<2]; 10 int ans[10000]; 11 int top; 12 int n,m; 13 void build(int l,int r,int idx){//普通的建树 14 node[idx].left=l; 15 node[idx].right=r; 16 if(l==r){ 17 node[idx].lsum=node[idx].rsum=1; 18 return; 19 } 20 int mid=(l+r)/2; 21 build(l,mid,idx<<1); 22 build(mid+1,r,idx<<1|1); 23 node[idx].lsum=node[idx].rsum=r-l+1; 24 } 25 void pushup(int idx){//区间左连续和右连续的维护 26 if(node[idx<<1].lsum==node[idx<<1].right-node[idx<<1].left+1)//左连续的处理 27 node[idx].lsum=node[idx<<1].lsum+node[idx<<1|1].lsum; 28 else 29 node[idx].lsum=node[idx<<1].lsum; 30 if(node[idx<<1|1].rsum==node[idx<<1|1].right-node[idx<<1|1].left+1)//右连续的处理 31 node[idx].rsum=node[idx<<1].rsum+node[idx<<1|1].rsum; 32 else 33 node[idx].rsum=node[idx<<1|1].rsum; 34 } 35 void update(int pos,int val,int idx){//单点更新 36 if(node[idx].left==node[idx].right){ 37 node[idx].lsum=node[idx].rsum=val; 38 return; 39 } 40 int mid=(node[idx].left+node[idx].right)/2; 41 if(mid>=pos)update(pos,val,idx<<1); 42 else update(pos,val,idx<<1|1); 43 pushup(idx); 44 } 45 int query(int pos,int idx){//查询，分情况讨论 46 if(pos<=node[idx].left+node[idx].lsum-1) 47 return node[idx].lsum; 48 if(pos>=node[idx].right-node[idx].rsum+1)//这里无法保证pos一定在叶子节点的左连续或者右连续中，因为该村庄可能已经被毁 49 return node[idx].rsum; 50 //printf("%d ",node[idx].left); 51 if(node[idx].left==node[idx].right)return node[idx].lsum;//到达叶子节点时候要返回，因为上面的条件无法保证 52 int mid=(node[idx].left+node[idx].right)/2; 53 if(mid>=pos){ 54 if(pos>=node[idx<<1].right-node[idx<<1].rsum+1) 55 return query(pos,idx<<1)+query(node[idx<<1|1].left,idx<<1|1); 56 else 57 return query(pos,idx<<1); 58 } 59 else { 60 if(pos<=node[idx<<1|1].lsum+node[idx<<1|1].left-1) 61 return query(pos,idx<<1|1)+query(node[idx<<1].right,idx<<1); 62 else 63 return query(pos,idx<<1|1); 64 } 65 } 66 int main(){ 67 char temp;int data; 68 while(~scanf("%d%d",&n,&m)){ 69 top=-1; 70 build(1,n,1); 71 while(m--){ 72 cin>>temp; 73 if(temp=='D'){ 74 cin>>data; 75 ans[++top]=data; 76 update(data,0,1); 77 } 78 else if(temp=='R'){ 79 int tt=ans[top--]; 80 update(tt,1,1); 81 } 82 else{ 83 cin>>data; 84 printf("%d ",query(data,1)); 85 } 86 } 87 } 88 }