- 题目链接：SCOI2010_序列操作
写在前面的话：这道题真毒！！！- 题目标签：线段树
- 题目大意：给定一个序列，支持5种操作，全变0，全变1，区间取反，查询1的总数，查询连续1的总数。
- 题目思路：一个线段树维护7个量+2种标记。即 _1的总数（sum）、连续1的数目（l1）、连续0的数目（l0）、从左端点开始连续1的数目（ll1）、从左端点开始连续0的数目（ll0）、从右端点开始连续1的数目（rl1）、从右端点开始连续0的数目（rl0）;整体取反标记（all）、单个取反标记（sin）_ 。
- 建树：略
- 上传标记：sum直接左右儿子求和，ll0、ll1、rl0、rl1、l1、l0的维护详见另一篇题解。
- 下传标记：先处理全部取反的标记，再处理单个取反，详见代码pushdown函数。
- 3种修改：请读者自行理解。
- 2种查询：
- 对于查询1的总数：略
- 查询连续1的总数：和上传标记的思路基本一样，请读者自行理解。
- 代码
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
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;
}
struct lst {
int sum,l1,l0,ll1,ll0,rl1,rl0,all,sin;
}T[Maxn*4];
int n,m;
int a[Maxn];
namespace DY {
void pushup(int k,int l,int r) {
int mid=l+r>>1;
int L1=mid-l+1,L2=r-mid;
T[k].sum=T[k<<1].sum+T[k<<1|1].sum;
T[k].ll0=T[k<<1].ll0;
T[k].ll1=T[k<<1].ll1;
if(T[k].ll0==L1)
T[k].ll0+=T[k<<1|1].ll0;
if(T[k].ll1==L1)
T[k].ll1+=T[k<<1|1].ll1;
T[k].rl0=T[k<<1|1].rl0;
T[k].rl1=T[k<<1|1].rl1;
if(T[k].rl0==L2)
T[k].rl0+=T[k<<1].rl0;
if(T[k].rl1==L2)
T[k].rl1+=T[k<<1].rl1;
T[k].l0=max(T[k<<1].l0, T[k<<1|1].l0);
T[k].l0=max(T[k].l0, T[k<<1].rl0+T[k<<1|1].ll0);
T[k].l1=max(T[k<<1].l1, T[k<<1|1].l1);
T[k].l1=max(T[k].l1, T[k<<1].rl1+T[k<<1|1].ll1);
}
void pushdown(int k,int l,int r) {
int mid=l+r>>1;
int L1=mid-l+1,L2=r-mid;
if(T[k].all==1) { //首先处理整体取反 （这一部分感觉很好理解）
T[k<<1]=(lst){L1,L1,0,L1,0,L1,0,1,0}; //整体变1
T[k<<1|1]=(lst){L2,L2,0,L2,0,L2,0,1,0};
}
else if(T[k].all==0) {
T[k<<1]=(lst){0,0,L1,0,L1,0,L1,0,0}; //整体变0
T[k<<1|1]=(lst){0,0,L2,0,L2,0,L2,0,0};
}
T[k].all=-1;
if(T[k].sin==1) { //单个取反
T[k].sin=0;
T[k<<1].sum=L1-T[k<<1].sum; //新的sum相当于区间长度-原来1的数目
swap(T[k<<1].l0,T[k<<1].l1); //剩下的内容交换 具体解释[请自行copy该链接](https://www.luogu.org/blog/RIsingSunlight43383/dui-yu-wei-hu-xian-duan-shu-di-xie-shi-xu-lie-wei-hu-di-dan-ge-qu-fan)
swap(T[k<<1].ll0,T[k<<1].ll1);
swap(T[k<<1].rl0,T[k<<1].rl1);
T[k<<1].sin^=1;
T[k<<1|1].sum=L2-T[k<<1|1].sum;
swap(T[k<<1|1].l0,T[k<<1|1].l1);
swap(T[k<<1|1].ll0,T[k<<1|1].ll1);
swap(T[k<<1|1].rl0,T[k<<1|1].rl1);
T[k<<1|1].sin^=1;
}
}
void build(int k,int l,int r) {
T[k].all=-1;
if(l==r) {
T[k]=(lst){a[l],a[l],a[l]^1,a[l],a[l]^1,a[l],a[l]^1,-1,0};
return ;
}
int mid=l+r>>1;
build(k<<1, l, mid);
build(k<<1|1, mid+1, r);
pushup(k,l,r);
}
void modify0(int k,int l,int r,int x,int y) {
// if(l<x|| r>y) return ;
int mid=l+r>>1;
if(l>=x&& r<=y) {
int L=r-l+1;
T[k]=(lst){0,0,L,0,L,0,L,0,0}; //0,0,L,0,0,L,L,0,0
return ;
}
if(l>y|| r<x) return ;
pushdown(k,l,r);
if(x<=mid) modify0(k<<1, l, mid, x, y);
if(y>mid) modify0(k<<1|1, mid+1, r, x, y);
pushup(k,l,r);
}
void modify1(int k,int l,int r,int x,int y) {
// if(l<x|| r>y) return ;
int mid=l+r>>1;
if(l>=x&& r<=y) {
int L=r-l+1;
T[k]=(lst){L,L,0,L,0,L,0,1,0}; //L,L,0,L,L,0,0,1,0
return ;
}
if(l>y|| r<x) return ;
pushdown(k,l,r);
if(x<=mid) modify1(k<<1, l, mid, x, y);
if(y>mid) modify1(k<<1|1, mid+1, r, x, y);
pushup(k,l,r);
}
void modify2(int k,int l,int r,int x,int y) {
// if(l<x|| r>y) return ;
int mid=l+r>>1;
if(l>=x&& r<=y) {
int L=r-l+1;
T[k].sum=L-T[k].sum;
swap(T[k].l0,T[k].l1);
swap(T[k].ll0,T[k].ll1);
swap(T[k].rl0,T[k].rl1);
T[k].sin^=1;
return ;
}
if(l>y|| r<x) return ;
pushdown(k,l,r);
if(x<=mid) modify2(k<<1, l, mid, x, y);
if(y>mid) modify2(k<<1|1, mid+1, r, x, y);
pushup(k,l,r);
}
int query1(int k,int l,int r,int x,int y) {
// if(l<x|| r>y) return 0;
if(l>=x&& r<=y) return T[k].sum;
if(l>y|| r<x) return 0;
int mid=l+r>>1,res=0;
pushdown(k,l,r);
if(x<=mid) res+=query1(k<<1, l, mid, x, y);
if(y>mid) res+=query1(k<<1|1, mid+1, r, x, y);
return res;
}
lst query2(int k,int l,int r,int x,int y) {
// if(l<x|| r>y) return (lst){0};
if(l>=x&& r<=y) return T[k];
if(l>y|| r<x) return (lst){0};
pushdown(k,l,r);
int mid=l+r>>1;
int L1=mid-l+1,L2=r-mid;
lst LL=query2(k<<1, l, mid, x, y);
lst RR=query2(k<<1|1, mid+1, r, x, y);
lst ans;
ans.sum=LL.sum+RR.sum;
ans.ll0=LL.ll0;
ans.ll1=LL.ll1;
if(ans.ll0==L1)
ans.ll0+=RR.ll0;
if(ans.ll1==L1)
ans.ll1+=RR.ll1;
ans.rl0=RR.rl0;
ans.rl1=RR.rl1;
if(ans.rl0==L2)
ans.rl0+=LL.rl0;
if(ans.rl1==L2)
ans.rl1+=LL.rl1;
ans.l0=max(LL.l0, RR.l0);
ans.l0=max(ans.l0, LL.rl0+RR.ll0);
ans.l1=max(LL.l1, RR.l1);
ans.l1=max(ans.l1, LL.rl1+RR.ll1);
return ans;
}
void main() {
n=sc(); m=sc();
for(int i=1; i<=n; i++)
a[i]=sc();
build(1,1,n);
while(m--) {
int flag=sc(),u=sc(),v=sc();
u++,v++;
if(!flag) {
modify0(1,1,n,u,v);
}
else if(flag==1) {
modify1(1,1,n,u,v);
}
else if(flag==2) {
modify2(1,1,n,u,v);
}
else if(flag==3) {
printf("%d\n",query1(1,1,n,u,v));
}
else {
printf("%d\n",query2(1,1,n,u,v).l1);
}
}
}
};
int main() {
DY::main();
return 0;
}