学步园

http://poj.org/problem?id=2892

题意：有n个连续的村庄，编号1~n，有三种操作：

D X：摧毁X村庄； R：修复后摧毁的村庄（后摧毁的先修复）；Q X：询问与X村庄有直接或间接相连的村庄数。

思路：与poj 3667类似，都是求满足条件的连续最长区间，属于区间合并问题。不过这个相对简单，因为这个是单点更新，不用考虑延迟操作。求最长连续区间长度时，一般节点增加三个域，lx，rx，ax，分别表示从左边数最长连续区间，从右边数最长连续区间，整个区间中满足条件的最长连续区间。lx,rx是为了在子区间合并时，方便更新，也方便查询。

单点更新时，更新完这个点后，要UP上去，即也要更新它的父亲节点，包括lx，rx，ax。

查询某个点所在的满足条件的最长区间长度时，首先要弄清递归终止的条件：该区间长度为1或该区间全部为空或全部不为空，因为当前区间全为空或全不空时，其子区间也一定是这样的状态，所以不必继续递归，直接返回该区间的长度即可。若上面没走掉，就继续递归。具体思路见代码解释。

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

const int maxn = 50005;

struct line
{
	int l,r;
	int lx,rx,ax;
}tree[maxn<<2];

void build(int v, int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	tree[v].lx = tree[v].rx = tree[v].ax = r-l+1;
	if(l == r)
		return;
	int mid = (l+r)>>1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
}

//将pos节点状态更新为flag
void update(int v, int pos, int flag)
{
	if(tree[v].l == tree[v].r)//找到该节点，直接更新
	{
		tree[v].lx = tree[v].rx = tree[v].ax = flag;
		return;
	}
	int mid = (tree[v].l+tree[v].r)>>1;
	if(pos <= mid)
		update(v*2,pos,flag);	//递归左子树
	else update(v*2+1,pos,flag);//递归右子树
	
	//更新完这个节点后要把新信息UP上来
	if(tree[v*2].ax == tree[v*2].r-tree[v*2].l+1)
		tree[v].lx = tree[v*2].ax + tree[v*2+1].lx;
	else tree[v].lx = tree[v*2].lx;

	if(tree[v*2+1].ax == tree[v*2+1].r-tree[v*2+1].l+1)
		tree[v].rx = tree[v*2+1].ax + tree[v*2].rx;
	else tree[v].rx = tree[v*2+1].rx;

	tree[v].ax = max(max(tree[v*2].ax,tree[v*2+1].ax),tree[v*2].rx+tree[v*2+1].lx);
}

//询问pos所在区间满足条件的最长连续区间长度
int query(int v, int pos)
{
	if(tree[v].l == tree[v].r || tree[v].ax == 0 || tree[v].ax == tree[v].r-tree[v].l+1)
		return tree[v].ax;//递归终止条件，当该区间全空或全满的时候递归终止，不必访问子节点，直接返回。

	int mid = (tree[v].l+tree[v].r)>>1;
	if(pos <= mid)//pos在左子树
	{
		if(pos >= tree[v*2].r-tree[v*2].rx+1)
			return tree[v*2].rx+tree[v*2+1].lx;
		else return query(v*2,pos);
	}
	else		  //pos在右子树
	{
		if(pos <= tree[v*2+1].l + tree[v*2+1].lx -1)
			return tree[v*2].rx+tree[v*2+1].lx;
		else return query(v*2+1,pos);
	}
}

int main()
{
	int n,m,x;
	char s[2];
	stack <int> st;
	while(!st.empty()) st.pop();
	scanf("%d %d",&n,&m);
	build(1,1,n);

	while(m--)
	{
		scanf("%s",s);
		if(s[0] == 'D')
		{
			scanf("%d",&x);
			st.push(x);
			update(1,x,0);//把X节点的状态更新为0.
		}
		else if(s[0] == 'R')
		{
			x = st.top();
			st.pop();
			update(1,x,1);//把X节点的状态更新为1.
		}
		else
		{
			scanf("%d",&x);
			int ans = query(1,x);//询问X节点所在区间的满足题意的最长连续区间长度
			printf("%d\n",ans);
		}
	}
	return 0;
}