lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？
输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目
第二行包括n个数，表示序列的初始状态
接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b<n）表示对于区间[a, b]执行标号为op的操作
输出格式：对于每一个询问操作，输出一行，包括1个数，表示其对应的答案
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
5
2
6
5
对于30%的数据，1<=n, m<=1000
对于100%的数据，1<=n, m<=100000
看完这个题，感觉对线段树的理解又加深了
根据题意和球最大字段和的经验，我们一个结点应该保存8个信息，才能进行合并
1的个数
区间最长连续1
区间从左边开始最长连续1
区间从右边开始最长连续1
行应的还有0的，一共是八个，因为交换的操作
注意的地方有两个，区间的合并方式和标记下方的优先级
具体看码：
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,q,a[100001];
4 struct d{
5 int w,b,lw,lb,rw,rb,mw,mb;
6 d(int w=0,int b=0,int lw=0,int lb=0,int rw=0,int rb=0,int mw=0,int mb=0):
7 w(w),b(b),lw(lw),lb(lb),rw(rw),rb(rb),mw(mw),mb(mb){}
// 当写复杂的线段树的时候，这种方式可以有效的减少代码量
8 };
9 inline d hb(d i,d j){
10 return d(
11 i.w+j.w, i.b+j.b,
12 (i.b?i.lw:i.w+j.lw), (i.w?i.lb:i.b+j.lb),
13 (j.b?j.rw:j.w+i.rw), (j.w?j.rb:j.b+i.rb),
14 max(max(i.mw,j.mw),i.rw+j.lw),
15 max(max(i.mb,j.mb),i.rb+j.lb));
16 }
17 d dat[262144]; int len[262144],tg1[262144],tg2[262144];
18 inline void P(int i,int typ){
19 d&t=dat[i];
20 if(typ==0) tg2[i]= 0, tg1[i]=0, t=d(0,len[i],0,len[i],0,len[i],0,len[i]);
21 if(typ==1) tg2[i]= 0, tg1[i]=1, t=d(len[i],0,len[i],0,len[i],0,len[i],0);
22 if(typ==2) tg2[i]^=1, swap(t.w,t.b), swap(t.lw,t.lb), swap(t.rw,t.rb), swap(t.mw,t.mb);
23 }
24 inline void pd(int i){
25 if(~tg1[i]) P(i<<1,tg1[i]), P(i<<1|1,tg1[i]);
26 if(tg2[i]) P(i<<1,2), P(i<<1|1,2);
27 tg1[i]=-1, tg2[i]=0;
28 }
29 void build(int i,int l,int r){
30 len[i]=r-l+1; tg1[i]=-1;
31 if(l==r) {int t=a[l]; dat[i]=d(t,t^1,t,t^1,t,t^1,t,t^1); return;}
32 build(i<<1,l,l+r>>1);
33 build(i<<1|1,(l+r>>1)+1,r);
34 dat[i]=hb(dat[i<<1],dat[i<<1|1]);
35 }
36 void Mdf(int i,int l,int r,int a,int b,int t){
37 if(b<l||r<a) return; if(a<=l&&r<=b) {P(i,t); return;}
38 pd(i); Mdf(i<<1,l,l+r>>1,a,b,t), Mdf(i<<1|1,(l+r>>1)+1,r,a,b,t);
39 dat[i]=hb(dat[i<<1],dat[i<<1|1]);
40 }
41 d Qur(int i,int l,int r,int a,int b){
42 if(b<l||r<a) return d(); if(a<=l&&r<=b) return dat[i];
43 pd(i); return hb(Qur(i<<1,l,l+r>>1,a,b),Qur(i<<1|1,(l+r>>1)+1,r,a,b));//查询的操作也是两个区间的合并
44 }
45 int main(){
46 scanf("%d%d",&n,&q);
47 for(int i=1;i<=n;++i) scanf("%d",a+i);
48 build(1,1,n);
49 for(int i=1;i<=q;++i){
50 int opt,l,r;
51 scanf("%d%d%d",&opt,&l,&r); ++l, ++r;
52 if(opt<3) Mdf(1,1,n,l,r,opt);
53 else {d t=Qur(1,1,n,l,r); printf("%d\n",opt==3?t.w:t.mw);}
54 }
55 return 0;
56 }
还有ODT，写起来超简单，以后在更，嘿嘿qwq
P2572 [SCOI2010]序列操作(神犇线段树 || ODT）
原文：https://www.cnblogs.com/zhangbuang/p/10533719.html