题解 P2572 【[SCOI2010]序列操作】
天上一颗蛋
2018-10-20 23:42:12
很久没发题解了， 这题难调， 看看这篇题解能不能帮到大家
$debug$ 了一个下午， 发点东西说点要注意的地方
[从博客搬过来， 不知道格式会不会炸。。](https://www.cnblogs.com/Tony-Double-Sky/p/9823463.html)
首先说明， 线段树这种东西， 每个人写法差异较大， **题解嘛主要是看思路是否正确以及细节是否处理得当**
掌握这题， 将会对线段树有一个好的领悟
（前排求点赞~~硬币收藏素质三连 XD~~）
# 前文
这篇题解将着重对以下问题做一个（尽量详细）的说明， 不懂可以私信或QQ， 有空可以解答
1. 大体思路及维护元素
1. 上推（这两个大家都有讲， 看不懂就都看看没准就会了）
1. 着重讲 **$pushdown$ 下放懒标记操作 的细节处理问题**
很多得 $10$ 分的人都是懒标记下放细节处理不得当
诚然， 还请观摩这篇题解之前**自行仔细思考**， 能得到很多
另外， 此题码量较大。 如还有错误请告知。 谢谢
那么开始吧
# [正文](https://www.cnblogs.com/Tony-Double-Sky/p/9823463.html)
对自己 & $RNG$ ： 骄兵必败
$lpl$加油！
# P2572 [SCOI2010]序列操作
题目描述
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都需要给出回答，聪明的程序员们，你们能帮助他吗？
---
**错误日志： 内容较多且重要， 将写在下方加粗**
---
# Solution
线段树， 需要维护以下信息：
1. $sum$ 区间 $1$ 的个数
2. $max[0/1]$ 区间内 $0/1$ 最长连续子段
3. $lmax[0/1]$ 包含区间左端点最长 $0/1$ 子段
4. $rmax[0/1]$ 包含区间右端点最长 $0/1$ 子段
鉴于有区间操作， 这里还需要两个标记：
5. $lazy = {-1, 0, 1}$ 为 $-1$ 表示无状态， 为 $0/1$ 表示区间全部赋值为 $0/1$
6. $rev = {0, 1}$ 区间是否翻转
---
需要维护的元素较多， 先讲 $pushup$
区间和直接相加即可
包含左端点的连续子段有两种情况：
1. 直接继承左区间的 $lmax$
2. 当左区间全满 / 全空时， 左端点可以跨越， 加上右区间的部分
右区间更新同理
对于区间最长连续子段， 有以下三种情况
1. 直接继承左区间的较大值
2. 直接继承右区间的较大值
3. 左区间的含右端点最长子段 + 右区间含左端点最长子段， 即最长部分跨越区间分割线
以上需要分 $0/1$ 讨论， 程序中直接两层循环搞定
---
**然后到了难点 $pushdown$**
**~~我一个需要冲省队的选手竟然直到现在才注意到这点很惨啊~~**
在线段树 **$pushdown$** 操作中， 我们需要明确两件事：
1. 标记的优先级
**2. 下放某一标记是否会对子节点的其他类型标记有所影响**
这里重点讨论第二点（第一点区间全体赋值优先级肯定高于翻转， 所以优先拆区间赋值标记， 拆标记时需要将翻转标记清空）
在拆解一个标记时， 我们不仅需要明确将此标记下放到子节点， **同类型的标记**应该如何改变， 而更应明确拆解此标记会对 **不同类型的标记**有何种影响
明确同类型的影响是一般不会出问题的， 如将区间加标记下放时， 子节点的区间加标记累加上这个值
以本题为例：
**将区间赋值标记拆解时， 不仅需要将子区间赋值标记更新为此值， 还需要将子节点翻转标记清空**（不过这个貌似影响不大， 拆赋值标记时会将翻转标记清空的）
**将区间翻转标记拆解时， 需要分两种情况考虑此标记下推对子区间 赋值标记 和 翻转标记造成的影响**
考虑到赋值标记的优先级大于翻转标记， **在有赋值标记的情况下， 直接翻转赋值标记**
其余情况翻转标记异或等于1
---
其余见代码 虽然很长但用心弄懂会对线段树有一个很深刻的理解
这样**完备地**考虑所有情况是一个 $OI$ 选手的基本素养
---
嗯就这样， $RNG$ 别丧气， 你们是最棒的； $S8$ ，$lpl$ 加油！
# Code
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
#define LL long long
#define REP(i, x, y) for(int i = (x);i <= (y);i++)
using namespace std;
int RD(){
int out = 0,flag = 1;char c = getchar();
while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
return flag * out;
}
const int maxn = 200019;
int num, na;
int v[maxn];
#define lid (id << 1)
#define rid (id << 1) | 1
//int max(int a, int b){return a > b ? a : b;}//听说手写快？
struct seg_tree{
int l, r;
int sum;
int lazy;//-1.NULL 0.全为0 1.全为1
int rev;
int max[2], lmax[2], rmax[2];
}tree[maxn << 2];
void pushup(int id){
tree[id].sum = tree[lid].sum + tree[rid].sum;
REP(i, 0, 1){
tree[id].lmax[i] = tree[lid].lmax[i];
if(i == 1 && tree[lid].sum == tree[lid].r - tree[lid].l + 1)//左区间全满
tree[id].lmax[i] += tree[rid].lmax[i];//可以跨越
else if(i == 0 && tree[lid].sum == 0)//左区间全空
tree[id].lmax[i] += tree[rid].lmax[i];
tree[id].rmax[i] = tree[rid].rmax[i];
if(i == 1 && tree[rid].sum == tree[rid].r - tree[rid].l + 1)
tree[id].rmax[i] += tree[lid].rmax[i];
else if(i == 0 && tree[rid].sum == 0)
tree[id].rmax[i] += tree[lid].rmax[i];
tree[id].max[i] = tree[lid].rmax[i] + tree[rid].lmax[i];//中间
tree[id].max[i] = max(tree[id].max[i], tree[lid].max[i]);//继承子区间
tree[id].max[i] = max(tree[id].max[i], tree[rid].max[i]);
}
}
void build(int id, int l, int r){
tree[id].l = l, tree[id].r = r, tree[id].lazy = -1;
if(l == r){
tree[id].sum = v[l];
tree[id].max[0] = tree[id].lmax[0] = tree[id].rmax[0] = v[l] == 0;
tree[id].max[1] = tree[id].lmax[1] = tree[id].rmax[1] = v[l] == 1;
return ;
}
int mid = (l + r) >> 1;
build(lid, l, mid), build(rid, mid + 1, r);
pushup(id);
}
void pushdown(int id){
if(tree[id].lazy != -1){//优先级最高
tree[id].rev = 0;//清空标记
int val = tree[id].lazy;
tree[lid].sum = (tree[lid].r - tree[lid].l + 1) * val;
tree[rid].sum = (tree[rid].r - tree[rid].l + 1) * val;
tree[lid].lazy = tree[rid].lazy = val;
tree[lid].rev = tree[rid].rev = 0;
tree[lid].max[val]
= tree[lid].lmax[val]
= tree[lid].rmax[val]
= tree[lid].r - tree[lid].l + 1;
tree[lid].max[val ^ 1]
= tree[lid].lmax[val ^ 1]
= tree[lid].rmax[val ^ 1]
= 0;
tree[rid].max[val]
= tree[rid].lmax[val]
= tree[rid].rmax[val]
= tree[rid].r - tree[rid].l + 1;
tree[rid].max[val ^ 1]
= tree[rid].lmax[val ^ 1]
= tree[rid].rmax[val ^ 1]
= 0;
tree[id].lazy = -1;
}
if(tree[id].rev){
tree[lid].sum = (tree[lid].r - tree[lid].l + 1) - tree[lid].sum;
tree[rid].sum = (tree[rid].r - tree[rid].l + 1) - tree[rid].sum;
if(tree[lid].lazy != -1)tree[lid].lazy ^= 1;//综合考虑优先级， 对其他标记的影响
else tree[lid].rev ^= 1;
if(tree[rid].lazy != -1)tree[rid].lazy ^= 1;
else tree[rid].rev ^= 1;
swap(tree[lid].max[0], tree[lid].max[1]);
swap(tree[lid].lmax[0], tree[lid].lmax[1]);
swap(tree[lid].rmax[0], tree[lid].rmax[1]);
swap(tree[rid].max[0], tree[rid].max[1]);
swap(tree[rid].lmax[0], tree[rid].lmax[1]);
swap(tree[rid].rmax[0], tree[rid].rmax[1]);
tree[id].rev = 0;
}
}
void update(int id, int val, int l, int r){
pushdown(id);
if(tree[id].l == l && tree[id].r == r){
if(val == 0 || val == 1){
tree[id].sum = (tree[id].r - tree[id].l + 1) * val;
tree[id].lazy = val;
tree[id].max[val]
= tree[id].lmax[val]
= tree[id].rmax[val]
= tree[id].r - tree[id].l + 1;
tree[id].max[val ^ 1]
= tree[id].lmax[val ^ 1]
= tree[id].rmax[val ^ 1]
= 0;
}
else if(val == 2){
tree[id].sum = (tree[id].r - tree[id].l + 1) - tree[id].sum;
tree[id].rev ^= 1;
swap(tree[id].max[0], tree[id].max[1]);
swap(tree[id].lmax[0], tree[id].lmax[1]);
swap(tree[id].rmax[0], tree[id].rmax[1]);
}
return ;
}
int mid = (tree[id].l + tree[id].r) >> 1;
if(mid < l)update(rid, val, l, r);
else if(mid >= r)update(lid, val, l, r);
else update(lid, val, l, mid), update(rid, val, mid + 1, r);
pushup(id);
}
int query(int id, int l, int r){
pushdown(id);
if(tree[id].l == l && tree[id].r == r)return tree[id].sum;
int mid = (tree[id].l + tree[id].r) >> 1;
if(mid < l)return query(rid, l, r);
else if(mid >= r)return query(lid, l, r);
else return query(lid, l, mid) + query(rid, mid + 1, r);
}
seg_tree Q_max(int id, int l, int r){
pushdown(id);
if(tree[id].l == l && tree[id].r == r)return tree[id];
int mid = (tree[id].l + tree[id].r) >> 1;
if(mid < l)return Q_max(rid, l, r);
else if(mid >= r)return Q_max(lid, l, r);
else{
seg_tree ret, L = Q_max(lid, l, mid), R = Q_max(rid, mid + 1, r);
ret.sum = L.sum + R.sum;
REP(i, 0, 1){
ret.lmax[i] = L.lmax[i];
if(i == 1 && L.sum == L.r - L.l + 1)//左区间全满
ret.lmax[i] += R.lmax[i];//可以跨越
else if(i == 0 && L.sum == 0)//左区间全空
ret.lmax[i] += R.lmax[i];
ret.rmax[i] = R.rmax[i];
if(i == 1 && R.sum == R.r - R.l + 1)
ret.rmax[i] += L.rmax[i];
else if(i == 0 && R.sum == 0)
ret.rmax[i] += L.rmax[i];
ret.max[i] = L.rmax[i] + R.lmax[i];//中间
ret.max[i] = max(ret.max[i], L.max[i]);//继承子区间
ret.max[i] = max(ret.max[i], R.max[i]);
}
return ret;
}
}
int main(){
num = RD(), na = RD();
REP(i, 1, num)v[i] = RD();
build(1, 1, num);
while(na--){
int cmd = RD(), l = RD(), r = RD();l++, r++;
if(cmd == 0)update(1, 0, l, r);
else if(cmd == 1)update(1, 1, l, r);
else if(cmd == 2)update(1, 2, l, r);
else if(cmd == 3)printf("%d\n", query(1, l, r));
else printf("%d\n", Q_max(1, l, r).max[1]);
}
return 0;
}
```