http://acm.hdu.edu.cn/showproblem.php?pid=1540
题目大意：抗日战争期间进行地道战，存在n个村庄用地道连接，输入D表示破坏某个村庄（摧毁与其相连的地道， 包括其本身），输入R表示重建最后被破坏的那个村庄。
输入Q表示查询某村庄可通过地道到达多少个村庄（包含本身）。
将题目理想化，即为找与某点直接或间接相连的有多少个点。即通过此点的线段的最大长度。当此点时破坏时默认为0.抽象为此过程后发现即为在线段上执行的操作，即线
段树知识点。分析：此点可能为孤立（0）， 可能位于某线段左区间的线段，可能位于某线段右区间的线段，可能为左右区间都经过的线段。故在线段树种定义lsum表示此
区间左端向右可到达的极限长度，rsum表示此区间从右端向左可达到的极限长度， sum表示此区间内的最大长度。分析更新，注意细节即可。
#include <stdio.h>
#include <stack>
#include <algorithm>
using namespace std;
#define lson rt<<1
#define rson rt<<1|1
#define N 100005
struct tree
{
int l, r, lsum, rsum, sum;
int mid()
{
return (l+r)/2;
}
int len()
{
return (r-l+1);
}
}a[N<<2];
void build(int rt, int l, int r)
{
a[rt].l = l;
a[rt].r = r;
a[rt].lsum = a[rt].rsum = a[rt].sum = a[rt].len();
if(l==r)return ;
build(lson, l, a[rt].mid());
build(rson, a[rt].mid()+1, r);
}
void Combine(int rt)
{
a[rt].lsum = a[lson].lsum;
a[rt].rsum = a[rson].rsum;
if(a[lson].lsum == a[lson].len())///左儿子的左极限为全区间，则说明可以与右区间合并
a[rt].lsum += a[rson].lsum;
if(a[rson].rsum == a[rson].len())
a[rt].rsum += a[lson].rsum;
a[rt].sum = max(max(a[rt].lsum, a[rt].rsum), a[lson].rsum+a[rson].lsum);
}
void Destroy(int rt, int k, int e)
{
if(a[rt].l==a[rt].r)
{
a[rt].lsum = a[rt].rsum = a[rt].sum = e;
return ;
}
if(a[rt].mid()>=k)Destroy(lson, k, e);
else Destroy(rson, k, e);
Combine(rt);
}
int Query(int rt, int k)
{
if(a[rt].sum == 0)return 0;///在点上
if(k<a[rt].l+a[rt].lsum)return a[rt].lsum;///在线段中；
if(k>a[rt].r-a[rt].rsum)return a[rt].rsum;
if(k>a[lson].r-a[lson].rsum && k<a[rson].lsum+a[rson].l)
return a[lson].rsum + a[rson].lsum;
if(a[rt].mid()>=k)return Query(lson, k);
else return Query(rson, k);
}
int main()
{
int m, n;
while(scanf("%d %d", &n, &m)!=EOF)
{
build(1, 1, n);
char order[10];
int x;
stack<int>Q;
while(m--)
{
scanf("%s", order);
if(order[0]=='D')
{
scanf("%d", &x);
Q.push(x);
Destroy(1, x, 0);
}
else if(order[0]=='R' && Q.size())
{
x = Q.top();
Q.pop();
Destroy(1, x, 1);
}
else
{
scanf("%d", &x);
printf("%d
", Query(1, x));
}
}
}
return 0;
}