Poj 2892 Tunnel Warfare(セグメントツリー単点更新区間マージ)

http://poj.org/problem?id=2892
題意:n個連続の村があり、番号1~n、3種類の操作がある.
D X:X村を破壊する;R:修復後に破壊された村(後に破壊された先修復);Q X:X村と直接または間接的につながっている村の数を尋ねる.
構想:poj 3667と同様に、条件を満たす連続最長区間を求め、区間合併問題に属する.しかし、これは比較的簡単です.これは単一の更新なので、遅延操作を考慮する必要はありません.最長連続区間長を求める場合,一般ノードは3つのドメイン,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
",ans);
		}
	}
	return 0;
}