HDU 1540 Tunnel Warfare

题意：

题目有三种操作 :

D:  摧毁村庄

Q: 查询相连的村庄

R: 修复上次被摧毁的村庄

这个题目的关键部分就是 对线段的修改部分, 也是最难的部分, 这部分理解了, 这个题目就基本会了.

这个题目跟HOTEL类似，每个节点里包含：cav(这个节点所代表的区间，能够连续的最大子区间长度)，lv(左边开始数，连续区间长度)，rv(右边数起，连续区间的长度)，flag表示该区间是否存在连续区间。先把每个节点里的rv,lv,cav初始化成该区间的长度。

然后是查询函数，首先将节点的值往下传递（为了下面的操作），当要查询的节点位置小于该区间的mid，继续讨论，如果这个节点在从左子树的右边开始的连续区间内，则问题转换成：s[num+num].rv+search(mid+1,num+num+1);如果要查询的节点的位置大于mid，继续讨论，如果该节点在右子树左边开始的连续区间内，则问题转换成：s[num+num+1].lv+search(mid,num+num);最后当当前节点的c[num].cav==0(就是说这个区间不存在连续子区间，所以不必要继续找了，直接返回他的cav)或者c[num].cav==len(num)(就是说这个区间完全连续！当然返回啦)再或者这个区间只有一个节点了也直接返回，不用再找了。

然后就是更新函数了，更新函数首先还是把该节点的值往下传递，为了子树上面的操作，然后分左右子树进行分别更新，最关键的是

s[num].lv=s[num+num].lv;
	s[num].rv=s[num+num+1].rv;
	s[num].cav=max( max(s[num+num].cav,s[num+num+1].cav),s[num+num].rv+s[num+num+1].lv);
	if(s[num].lv==len(num+num))
		s[num].lv+=s[num+num+1].lv;
	if(s[num].rv==len(num+num+1))
		s[num].rv+=s[num+num].rv;

然后也没什么注意的地方了 呵呵 


#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

struct node{
	int a,b;
	int lv,rv,cav,flag;
}s[200010];

int t[50010];

int len(int x){
	return s[x].b-s[x].a+1;
}

void init(int x){
	s[x].cav=s[x].lv=s[x].rv=s[x].flag?0:len(x);
}

int Build(int x,int y,int num){
	s[num].a=x;	s[num].b=y;
	s[num].flag=num==1?0:-1;
	s[num].lv=s[num].rv=s[num].cav=len(num);
	if(x==y){
		return 0;	
	}
	int mid=(x+y)/2;
	Build(x,mid,num+num);
	Build(mid+1,y,num+num+1);
}

int search(int x,int num){
	if(s[num].cav==0||s[num].cav==len(num)||s[num].a==s[num].b)
		return s[num].cav;
	if(s[num].flag!=-1){
		s[num+num].flag=s[num+num+1].flag=s[num].flag;
		s[num].flag=-1;
		init(num+num);	init(num+num+1);
	}
	int mid=(s[num].a+s[num].b)/2;
	if(x<=mid){
		if(x>mid-s[num+num].rv)
			return s[num+num].rv+search(mid+1,num+num+1);
		else 
			return search(x,num+num);
	}
	else{
		if(x<=mid+s[num+num+1].lv)
			return s[num+num+1].lv+search(mid,num+num);
		else
			return search(x,num+num+1);
	}
	
}

int modify(int x,int num,int flag){
	if(s[num].a==s[num].b){
		s[num].flag=flag;
		init(num);
		return 0;	
	}
	if(s[num].flag!=-1){
		s[num+num].flag=s[num+num+1].flag=s[num].flag;
		s[num].flag=-1;
		init(num+num);	init(num+num+1);
	}
	int mid=(s[num].a+s[num].b)/2;
	if(x<=mid)
		modify(x,num+num,flag);
	else 
		modify(x,num+num+1,flag);
	s[num].lv=s[num+num].lv;
	s[num].rv=s[num+num+1].rv;
	s[num].cav=max( max(s[num+num].cav,s[num+num+1].cav),s[num+num].rv+s[num+num+1].lv);
	if(s[num].lv==len(num+num))
		s[num].lv+=s[num+num+1].lv;
	if(s[num].rv==len(num+num+1))
		s[num].rv+=s[num+num].rv;
}

int main(){
    int n,x,cas,i,times;
    char c[20];
    while(scanf("%d %d",&n,&cas)!=EOF){
        memset(t,0,sizeof(t));
        times=1;
        Build(1,n,1);
        while(cas--){
            scanf("%s",c);
            if('D'==c[0]){
                scanf("%d",&x);
                t[times++]=x;
                modify(x,1,1);
            }    
            else if('Q'==c[0]){
                scanf("%d",&x);
                int k=search(x,1);
                printf("%d\n",k);
            }
            else{   if(times==1)
                    continue;
                x=t[--times];
                modify(x,1,0);
            }
        }
    }
    return 0;
}