P2572 [SCOI2010] 序列操作

题目描述
lxhgww 最近收到了一个?
01
01 序列，序列里面包含了?
�
n 个数，下标从?
0
0 开始。这些数要么是?
0
0，要么是?
1
1，现在对于这个序列有五种变换操作和询问操作：

0 l r 把?
[
�
,
�
]
[l,r] 区间内的所有数全变成?
0
0；
1 l r 把?
[
�
,
�
]
[l,r] 区间内的所有数全变成?
1
1；
2 l r 把?
[
�
,
�
]
[l,r] 区间内的所有数全部取反，也就是说把所有的?
0
0 变成?
1
1，把所有的?
1
1 变成?
0
0；
3 l r 询问?
[
�
,
�
]
[l,r] 区间内总共有多少个?
1
1；
4 l r 询问?
[
�
,
�
]
[l,r] 区间内最多有多少个连续的?
1
1。
对于每一种询问操作，lxhgww 都需要给出回答，聪明的程序员们，你们能帮助他吗？

输入格式
第一行两个正整数?
�
,
�
n,m，表示序列长度与操作个数。
第二行包括?
�
n 个数，表示序列的初始状态。
接下来?
�
m 行，每行三个整数，表示一次操作。

输出格式
对于每一个询问操作，输出一行一个数，表示其对应的答案。

输入输出样例
输入 #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
输出 #1复制
5
2
6
5
说明/提示
【数据范围】
对于?
30
%
30% 的数据，
1
≤
�
,
�
≤
1000
1≤n,m≤1000；
对于
100
%
100% 的数据，
1
≤
�
,
�
≤
1
0
5
1≤n,m≤10?
5
?。

更棒的线段树操作，尽在本题解中！

分析一波题意，显然的区间操作，而且信息都是线段树能维护的。

因为有区间取反操作，所以不仅要记录?
1
1 的信息，
0
0 的信息也要记录。

对于一个点，我们考虑维护?
8
8 个信息：

1
/
0
1/0 的个数，左/右边起?
1
/
0
1/0 的最长长度，整段区间中?
1
/
0
1/0 的连续最长长度。

只有维护至少?
8
8 个信息才能保证能够合并区间（想想为什么）。

使用结构体存储复杂信息是更好的方法：

struct d{
? ? // 分别表示上述的8个信息
? ? // w: 1(white) , b: 0(black)
? ? // l: 左边起 , r: 右边起
? ? // mw, mb 代表整段区间中1/0的最长长度
? ? int w,b,lw,lb,rw,rb,mw,mb;
? ? //构造函数，方便赋值
? ? 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):
? ? w(w),b(b),lw(lw),lb(lb),rw(rw),rb(rb),mw(mw),mb(mb){}
};
而合并两个子区间，需要考虑很多东西：

1
/
0
1/0 的个数直接相加，左右起的?
1
/
0
1/0 要考虑左/右的一整个区间是否是同一个数。

整段区间中的?
1
/
0
1/0 最长长度为以下两值的较大值

左、右区间的?
1
/
0
1/0 最长长度；
左边的右端、右边的左端的?
1
/
0
1/0 最长长度之和。
由此写出合并两个区间的函数：

inline d hb(d i,d j){
?? ?return d(
?? ?i.w+j.w, i.b+j.b,
?? ?(i.b?i.lw:i.w+j.lw), (i.w?i.lb:i.b+j.lb),
?? ?(j.b?j.rw:j.w+i.rw), (j.w?j.rb:j.b+i.rb),
?? ?max(max(i.mw,j.mw),i.rw+j.lw),
?? ?max(max(i.mb,j.mb),i.rb+j.lb));
}
这个函数在建树，修改和查询的时候都会用到，我写复杂的线段树都会定义这个函数。

然后是对一个区间整体修改，要注意?
3
3 种修改操作的优先顺序：先赋值后取反：

inline void P(int i,int typ){
? ? // tg1(标记1)是区间赋值,没有标记时为-1,有标记时为0或1
? ? // tg2(标记2)是区间取反,没有标记时为 0,有标记时为1
? ? // len表示一个区间的长度,在建树时处理
? ? d&t=dat[i];
? ? // 区间赋值为 0
? ? if(typ==0) tg2[i]= 0, tg1[i]=0, t=d(0,len[i],0,len[i],0,len[i],0,len[i]);
? ? // 区间赋值为 1
? ? if(typ==1) tg2[i]= 0, tg1[i]=1, t=d(len[i],0,len[i],0,len[i],0,len[i],0);
? ? // 区间取反
? ? 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);
}
这个函数会在修改和标记下传（pushdown）时用到。

接下来是标记下传（pushdown），注意顺序：

inline void pd(int i){
? ? // 对两个子区间修改
? ? if(~tg1[i]) P(i<<1,tg1[i]), P(i<<1|1,tg1[i]);
? ? if(tg2[i]) P(i<<1,2), P(i<<1|1,2);
? ? // 把标记清空
? ? tg1[i]=-1, tg2[i]=0;
}
最后是建树，修改和查询函数，有了上面的，这就很简单了：

void build(int i,int l,int r){
? ? len[i]=r-l+1; tg1[i]=-1;
? ? if(l==r) {int t=a[l]; dat[i]=d(t,t^1,t,t^1,t,t^1,t,t^1); return;}
? ? build(i<<1,l,l+r>>1);
? ? build(i<<1|1,(l+r>>1)+1,r);
? ? dat[i]=hb(dat[i<<1],dat[i<<1|1]);
}
void Mdf(int i,int l,int r,int a,int b,int t){
? ? // 如果区间没有交集 或者 当前区间完全包含在修改区间内的情况
? ? if(b<l||r<a) return; if(a<=l&&r<=b) {P(i,t); return;}
? ? pd(i); Mdf(i<<1,l,l+r>>1,a,b,t), Mdf(i<<1|1,(l+r>>1)+1,r,a,b,t);
? ? dat[i]=hb(dat[i<<1],dat[i<<1|1]);
}
d Qur(int i,int l,int r,int a,int b){
? ? // 如果区间没有交集 或者 当前区间完全包含在查询区间内的情况
? ? if(b<l||r<a) return d(); if(a<=l&&r<=b) return dat[i];
? ? pd(i); return hb(Qur(i<<1,l,l+r>>1,a,b),Qur(i<<1|1,(l+r>>1)+1,r,a,b));
}
下面是完整代码：

#include<bits/stdc++.h>
using namespace std;
int n,q,a[100001];
struct d{
?? ?int w,b,lw,lb,rw,rb,mw,mb;
?? ?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):
? ? w(w),b(b),lw(lw),lb(lb),rw(rw),rb(rb),mw(mw),mb(mb){}
};
inline d hb(d i,d j){
?? ?return d(
?? ?i.w+j.w, i.b+j.b,
?? ?(i.b?i.lw:i.w+j.lw), (i.w?i.lb:i.b+j.lb),
?? ?(j.b?j.rw:j.w+i.rw), (j.w?j.rb:j.b+i.rb),
?? ?max(max(i.mw,j.mw),i.rw+j.lw),
?? ?max(max(i.mb,j.mb),i.rb+j.lb));
}
d dat[262144]; int len[262144],tg1[262144],tg2[262144];
inline void P(int i,int typ){
?? ?d&t=dat[i];
?? ?if(typ==0) tg2[i]= 0, tg1[i]=0, t=d(0,len[i],0,len[i],0,len[i],0,len[i]);
?? ?if(typ==1) tg2[i]= 0, tg1[i]=1, t=d(len[i],0,len[i],0,len[i],0,len[i],0);
?? ?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);
}
inline void pd(int i){
?? ?if(~tg1[i]) P(i<<1,tg1[i]), P(i<<1|1,tg1[i]);
?? ?if(tg2[i]) P(i<<1,2), P(i<<1|1,2);
?? ?tg1[i]=-1, tg2[i]=0;
}
void build(int i,int l,int r){
?? ?len[i]=r-l+1; tg1[i]=-1;
?? ?if(l==r) {int t=a[l]; dat[i]=d(t,t^1,t,t^1,t,t^1,t,t^1); return;}
?? ?build(i<<1,l,l+r>>1);
?? ?build(i<<1|1,(l+r>>1)+1,r);
?? ?dat[i]=hb(dat[i<<1],dat[i<<1|1]);
}
void Mdf(int i,int l,int r,int a,int b,int t){
?? ?if(b<l||r<a) return; if(a<=l&&r<=b) {P(i,t); return;}
?? ?pd(i); Mdf(i<<1,l,l+r>>1,a,b,t), Mdf(i<<1|1,(l+r>>1)+1,r,a,b,t);
?? ?dat[i]=hb(dat[i<<1],dat[i<<1|1]);
}
d Qur(int i,int l,int r,int a,int b){
?? ?if(b<l||r<a) return d(); if(a<=l&&r<=b) return dat[i];
?? ?pd(i); return hb(Qur(i<<1,l,l+r>>1,a,b),Qur(i<<1|1,(l+r>>1)+1,r,a,b));
}
int main(){
?? ?scanf("%d%d",&n,&q);
?? ?for(int i=1;i<=n;++i) scanf("%d",a+i);
?? ?build(1,1,n);
?? ?for(int i=1;i<=q;++i){
?? ??? ?int opt,l,r;
?? ??? ?scanf("%d%d%d",&opt,&l,&r); ++l, ++r;
?? ??? ?if(opt<3) Mdf(1,1,n,l,r,opt);
?? ??? ?else {d t=Qur(1,1,n,l,r); printf("%d\n",opt==3?t.w:t.mw);}
?? ?}
?? ?return 0;
}
以上就是我打较复杂线段树操作时的模板，大家可以借鉴一下，形成自己的风格。

?155