题意
有N个点，每两个点之间存在一条通路，D x代表摧毁x点，R代表修复最近摧毁的一个点。Q x代表查询x点能连接多少个村庄（包括自己）。
题解
比较复杂的线段树。状态需要用结构体保存。 l,r代表左边界和右边界，ls代表左连续区间长度，rs代表右连续区间长度。ms代表区间内最大连续长度。 初始化过程都初始化成1就可以了。 更新过程就比较复杂了，对于摧毁的点，更新成0就可以了。向上更新的过程需要做一些处理。 首先要判断左子区间的左连续区间长度==左子区间长度，如果相等的话，则代表左子区间连续，则当前区间的ls为左子区间的ls+右子区间的ls。否则当前区间的ls为左子区间的ls。 然后要判断右子区间的右连续区间长度==右子区间长度，如果相等的话，则代表右子区间连续，则当前区间的rs为右子区间的rs+左子区间的rs。否则当前区间的rs为右子区间的rs。 ms为左子区间ms，右子区间ms，左子区间rs+右子区间ls三者中的最大值。 查询的过程也需要做一定的处理。首先判断ms是否等于区间长度或者等于0。这两种情况代表区间内无连续区间和区间内为全连续，因此就不用再向下进行判断。l==r的时候也需要进行判断，这种情况连续长度就只可能为0或1。 如果不满足上述条件，就需要根据查询点的特征来进行查询了。如果查询点在左子区间，就在左子区间进行查询，这里要注意判断点在左子区间的右连续区间这一种特殊情况，在这种特殊情况下，连续区间的长度为左子区间rs+右子区间ls。对于右子区间的查询也同理，需要特殊判断在右子区间的ls中这一种情况。
注意事项
题目中需要考虑的特殊情况很多，稍有不慎就会WA。尤其是查询时的对查询点是否在边界区间的特殊判断一定要注意。
代码
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#define UP(i,l,h) for(int i=l;i<h;i++)
#define DOWN(i,h,l) for(int i=h-1;i>=l;i--)
#define W(a) while(a)
#define MEM(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
#define MAXN 400010
#define EPS 1e-10
#define MOD 100000000
using namespace std;
struct Node {
int l,r;
int ls,ms,rs;
};
Node nodes[
220000];
int p,lt,rt;
void build(
int o,
int l,
int r) {
if(l==r) {
nodes[o].l=l;
nodes[o].r=r;
nodes[o].ls=nodes[o].rs=nodes[o].ms=
1;
}
else {
nodes[o].l=l;
nodes[o].r=r;
nodes[o].ls=nodes[o].rs=nodes[o].ms=(r-l)+
1;
int m=l+(r-l)/
2;
build(o*
2,l,m);
build(o*
2+
1,m+
1,r);
}
}
void update(
int o,
int l,
int r,
bool des) {
if(l==r) {
if(des) {
nodes[o].ls=nodes[o].rs=nodes[o].ms=
0;
}
else {
nodes[o].ls=nodes[o].rs=nodes[o].ms=
1;
}
}
else {
int m=l+(r-l)/
2;
if(p<=m)
update(o*
2,l,m,des);
else
update(o*
2+
1,m+
1,r,des);
if(nodes[o*
2].ls==(nodes[o*
2].r-nodes[o*
2].l+
1))
nodes[o].ls=nodes[o*
2].ls+nodes[o*
2+
1].ls;
else
nodes[o].ls=nodes[o*
2].ls;
if(nodes[o*
2+
1].rs==(nodes[o*
2+
1].r-nodes[o*
2+
1].l+
1))
nodes[o].rs=nodes[o*
2].rs+nodes[o*
2+
1].rs;
else
nodes[o].rs=nodes[o*
2+
1].rs;
nodes[o].ms=max(max(nodes[o*
2].ms,nodes[o*
2+
1].ms),nodes[o*
2].rs+nodes[o*
2+
1].ls);
}
}
int query(
int o,
int l,
int r) {
if(l==r||nodes[o].ms==
0||nodes[o].ms==(nodes[o].r-nodes[o].l+
1)) {
return nodes[o].ms;
}
else {
int m=l+(r-l)/
2;
if(p<=m) {
if(p>=(nodes[o*
2].r-nodes[o*
2].rs+
1)) {
return nodes[o*
2].rs+nodes[o*
2+
1].ls;
}
else {
return query(o*
2,l,m);
}
}
else {
if(p<=(nodes[o*
2+
1].l+nodes[o*
2+
1].ls-
1)) {
return nodes[o*
2].rs+nodes[o*
2+
1].ls;
}
else {
return query(o*
2+
1,m+
1,r);
}
}
}
}
int main() {
int n,m;
W(~
scanf(
"%d%d",&n,&m)) {
MEM(nodes,
0);
build(
1,
1,n);
stack<int> st;
W(m--) {
getchar();
char c;
scanf(
"%c",&c);
if(c==
'D') {
scanf(
"%d",&p);
st.push(p);
update(
1,
1,n,
true);
}
else if(c==
'Q') {
scanf(
"%d",&p);
printf(
"%d\n",query(
1,
1,n));
}
else if(c==
'R') {
p=
0;
p=st.top();
st.pop();
update(
1,
1,n,
false);
}
}
}
}
