这题的意思是现在有一些村庄成一条直线排列，现在有三个操作，D：摧毁一个指定的村庄，Q：询问与指定村庄相连的村庄个数，
就是这个村庄向左和向右数村庄数量，遇到尽头或损坏的村庄为止，这个就是与这个村庄相连的村庄数量，当然，如果指定村庄已经被摧毁，则数量为0。R：把最后摧毁的那一个村庄恢复。在这里D操作和R操作都可以看成对线段树的单点修改，只是执行的操作不同，
最主要的是如何找和指定村庄相连的村庄数量，刚刚做的时候我很纠结，看了别人博客后... 我们可以定义一个max1和一个min1，表示这个区间里的最大值和最小值（max1初始化为-1，min1初始化为无穷大），这样一开始就是没有左右边界，如果某个村庄被摧毁，则把他的max1和min1都变成他的节点值，（自己体会一下下）
如果我们想找a村庄的的相连村庄数目，惯性思维是想一次性就把左右两个边界求出来，后来才发现我们其实可以用两次区间查询来分别找到a的左边界和右边界，query1（1，a，1）和query2（a，n，1）就是找区间1到a的的最大值和区间a到n的最小值，然后存一下这两个边界，最后相减。
具体可以看看代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
using namespace std;
#define inf 0x3f3f3f
struct node{
int l,r,min1,max1;
}str[*+];
stack<int>s;
int n,m,k,t,a,b;
int start,end1;
char ss[];
void build(int l,int r,int k)
{
str[k].l=l;
str[k].r=r;
str[k].max1=-;
str[k].min1=inf;
if(l==r)
{
return;
}
int mid=(l+r)/;
build(l,mid,k*);
build(mid+,r,k*+);
str[k].max1=max(str[k*].max1,str[k*+].max1);
str[k].min1=min(str[k*].min1,str[k*+].min1);
}
void change_point1(int k)//摧毁a点
{
if(str[k].l==str[k].r&&str[k].l==a)
{
str[k].max1=str[k].l;
str[k].min1=str[k].l;
return;
}
int mid=(str[k].l+str[k].r)/;
if(a<=mid)
change_point1(k*);
else
change_point1(k*+);
str[k].max1=max(str[k*].max1,str[k*+].max1);
str[k].min1=min(str[k*].min1,str[k*+].min1);
}
void change_point2(int k)//恢复a点
{
if(str[k].l==str[k].r&&str[k].l==a)
{
str[k].max1=-;
str[k].min1=inf;
return;
}
int mid=(str[k].l+str[k].r)/;
if(a<=mid)
change_point2(k*);
else
change_point2(k*+);
str[k].max1=max(str[k*].max1,str[k*+].max1);
str[k].min1=min(str[k*].min1,str[k*+].min1);
}
void query1(int l,int r,int k)//找a点的左边界
{
if(str[k].l>=l&&str[k].r<=r)
{
start=max(str[k].max1,start);
return;
}
int mid=(str[k].l+str[k].r)/;
if(l<=mid)
query1(l,r,k*);
if(r>mid)
query1(l,r,k*+);
}
void query2(int l,int r,int k)//找a点的右边界
{
if(str[k].l>=l&&str[k].r<=r)
{
end1=min(end1,str[k].min1);
return;
}
int mid=(str[k].l+str[k].r)/;
if(l<=mid)
query2(l,r,k*);
if(r>mid)
query2(l,r,k*+);
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
build(,n,);
while(!s.empty())
s.pop();
for(int i=;i<m;i++)
{
scanf("%s",ss);
if(ss[]=='D')
{
scanf("%d",&a);
change_point1();
s.push(a);
}
else if(ss[]=='Q')
{
scanf("%d",&a);
start=-;
end1=inf;
query1(,a,);
query2(a,n,);
if(start==-)//特判一下
start=;
if(end1==inf)
end1=n+;
int ans=end1-start-; if(start==end1)
ans=;
printf("%d\n",ans);
}
else if(ss[]=='R')
{
if(!s.empty())
{
a=s.top();
change_point2();
s.pop();
}
}
}
}
return ;
}