- 题目链接：好一个一中腰鼓！
- 题目标签：线段树
- 题意：给定一个01串，刚开始全为0（当然也可以为1，跟我所描述的相反即可），支持一种操作：将第u个数值反转。求每次反转之后，整个连续01串的最大值。
- 题目分析：这道题是关于线段树的应用问题，而不再是一些数值运算。现在线段树中一个节点要包含5个值：从左边开始连续01串的最大值，从右边开始连续01串的最大值，整个连续01串的最大值，01串左节点的值，01串右节点的值，区间长度。具体怎么更新不太好解释，详见代码注释吧！
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
using namespace std;
int sc() { //快读
int xx=0,ff=1; char cch;
while(cch<'0'|| cch>'9') {
if(cch=='-') ff=-ff; cch=gc;
}
while(cch>='0'&& cch<='9') {
xx=xx*10+(cch-48); cch=gc;
}
return xx*ff;
}
int n,m;
int L[Maxn*4],R[Maxn*4],data_l[Maxn*4],data_r[Maxn*4],Mid[Maxn*4],Len[Maxn*4];
//L为左端点开始最大值，R为右端点开始最大值，data_l为左端点值，data_r为右端点值，Mid为整个最大值，Len为区间长度。
namespace DY {
void Updata(int k) {
L[k]=L[k<<1];
R[k]=R[k<<1|1];
//当前节点的左端点开始最大值（以后简称左开最大值），和右开最大值即为左儿子的左开最大值和右儿子的右开最大值。
data_l[k]=data_l[k<<1];
data_r[k]=data_r[k<<1|1];
//当前节点的左端点值为左儿子的左端点值，右端点值为右儿子的右端点值。
Mid[k]=max(R[k<<1],Mid[k<<1]);
Mid[k]=max(Mid[k], max(L[k<<1|1], Mid[k<<1|1]));
//整个最大值为 max(左儿子的右开最大值，整个最大值) 和 max(右儿子的左开最大值，整个最大值) 的最大值
//注意：一定要左儿子和左儿子比，右儿子和右儿子比，否则会有问题。
if(data_r[k<<1]!= data_l[k<<1|1]) { //当左端点右值和右端点左值不相等时，即为合法的01串
Mid[k]=max(Mid[k], R[k<<1]+L[k<<1|1]); //更新整个最大值
if(L[k<<1]== Len[k<<1]) //如果左儿子 左开最大值等于 左区间长度，说明左右区间相连，因此，当前节点的左开最大值要加上右儿子的左开最大值 。
L[k]+=L[k<<1|1];
if(R[k<<1|1]== Len[k<<1|1]) //同上解释
R[k]+=R[k<<1];
}
}
void build(int k,int l,int r) { //建树
Len[k]=r-l+1; //计算区间长度 （为了方便以后判断）
if(l==r) {
L[k]=R[k]=Mid[k]=1; //长度初值为1（它自己的长度）
data_l[k]=data_r[k]=0; //数值初值为0
return ;
}
int mid=l+r>>1;
build(k<<1, l, mid);
build(k<<1|1, mid+1, r);
Updata(k); //更新数据
}
void modify(int k,int l,int r,int now) { //修改
if(l==r) {
data_l[k]=data_r[k]=~(data_r[k]); //0变1 1变0 即为取反（~）
return ;
}
int mid=l+r>>1;
if(now<=mid) modify(k<<1, l, mid, now);
if(now>mid) modify(k<<1|1, mid+1, r, now);
Updata(k); //更新数据
}
void main() {
n=sc(); m=sc();
build(1,1,n); //建树
while(m--) {
int u=sc();
modify(1,1,n,u); //修改
printf("%d\n",Mid[1]); //Mid[1]即为整个序列最大01串的长度
}
}
};
int main() {
DY::main();
return 0;
}总体来说，本题很好地加深了对线段树应用的理解，大家一定要弄明白（
可能本人解释的不太好，但已经尽力了）。