SCOI2010 P2572 序列操作
\(SCOI2010\) \(P2572\) 序列操作
一、题目描述
\(lxhgww\) 最近收到了一个 \(01\) 序列，序列里面包含了 \(n\) 个数，下标从 \(0\) 开始。这些数要么是 \(0\)，要么是 \(1\)，现在对于这个序列有五种变换操作和询问操作：
-
0 l r把 \([l, r]\) 区间内的所有数全变成 \(0\) -
1 l r把 \([l, r]\) 区间内的所有数全变成 \(1\) -
2 l r把 \([l,r]\) 区间内的所有数全部取反，也就是说把所有的 \(0\) 变成 \(1\)，把所有的 \(1\) 变成 \(0\) -
3 l r询问 \([l, r]\) 区间内总共有多少个 \(1\) -
4 l r询问 \([l, r]\) 区间内最多有多少个连续的 \(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\%\) 的数据，\(1\le n,m \le 1000\)；
对于\(100\%\) 的数据，\(1\le n,m \le 10^5\)。
二、线段树解法
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50;
#define mid ((l + r) >> 1)
#define ls u << 1
#define rs u << 1 | 1
struct Node {
int l, r;
int len; // 区间长度
int fz; // 懒标记：区间是否整个被赋值
int qf; // 懒标记：区间是否被反转
int sum; // 区间1的个数
int mx[2]; // 区间最多的连续0/1个数
int lx[2]; // 区间从左端点开始最多的连续的0/1个数
int rx[2]; // 区间从右端点开始最多的连续的0/1个数
} tr[N << 2];
int n, m;
void pushup(int u) {
tr[u].sum = tr[ls].sum + tr[rs].sum; // 区间中1的个数为左右子树中1的个数和
for (int i = 0; i < 2; i++) { // 分别讨论区间中0 1的情况
// 区间从左端点开始最多的连续的0/1的个数
tr[u].lx[i] = tr[ls].lx[i];
if (tr[ls].sum == i * tr[ls].len) tr[u].lx[i] += tr[rs].lx[i];
// 区间从右端点开始最多的连续的0/1的个数
tr[u].rx[i] = tr[rs].rx[i];
if (tr[rs].sum == i * tr[rs].len) tr[u].rx[i] += tr[ls].rx[i];
// 区间最多的连续0/1个数
/*
① 左儿子的区间最多的连续个数
② 右儿子的区间最多的连续个数
③ 左儿子的右最长+右儿子的左最长
*/
tr[u].mx[i] = max({tr[ls].rx[i] + tr[rs].lx[i], tr[ls].mx[i], tr[rs].mx[i]});
}
}
void build(int u, int l, int r) {
tr[u].l = l, tr[u].r = r; // 管辖范围
tr[u].fz = -1; // 懒标记初值:是否被赋值
tr[u].qf = -1; // 懒标记初值:是否被覆盖
tr[u].len = r - l + 1; // 区间长度
if (l == r) { // 叶子节点
int v;
cin >> v;
tr[u].sum = v; // v=1:区间内1的个数为1；v=0:区间内0的个数为0；
tr[u].mx[v] = 1; // v=1:区间中连续为0的个数为1;v=0:区间内连续为0的个数为1；
tr[u].lx[v] = 1; // v=1:区间从左端点开始最多的连续的1的个数为1;v=0:区间从左端点开始最多的连续的0的个数为1;
tr[u].rx[v] = 1; // v=1:区间从右端点开始最多的连续的1的个数为1;v=0:区间从右端点开始最多的连续的0的个数为1;
return;
}
build(ls, l, mid); // 构建左子树
build(rs, mid + 1, r); // 构建右子树
pushup(u); // 向上汇总统计信息
}
void pushdown(int u) {
if (~tr[u].fz) { // 区间赋值懒标记不空
int v = tr[u].fz;
tr[ls].fz = tr[rs].fz = v; // 向左右儿子传递赋值懒标记
tr[ls].qf = tr[rs].qf = -1; // 清空左右儿子的取反懒标记
tr[ls].sum = v * tr[ls].len; // v=1:sum=区间长度；v=0:sum=0
tr[rs].sum = v * tr[rs].len;
tr[ls].mx[v] = tr[ls].lx[v] = tr[ls].rx[v] = tr[ls].len;
tr[ls].mx[v ^ 1] = tr[ls].lx[v ^ 1] = tr[ls].rx[v ^ 1] = 0;
tr[rs].mx[v] = tr[rs].lx[v] = tr[rs].rx[v] = tr[rs].len;
tr[rs].mx[v ^ 1] = tr[rs].lx[v ^ 1] = tr[rs].rx[v ^ 1] = 0;
// 下传懒标记完毕
tr[u].fz = -1;
tr[u].qf = -1;
return;
}
if (~tr[u].qf) { // 本次是取反懒标记下传
tr[ls].qf ^= 1; // 向左儿子传递取反懒标记
tr[rs].qf ^= 1; // 向右儿子传递取反懒标记
if (~tr[ls].fz) tr[ls].fz ^= 1; // 如果原来左儿子存在赋值懒标记，那么就整体赋反值吧
if (~tr[rs].fz) tr[rs].fz ^= 1; // 如果原来右儿子存在赋值懒标记，那么就整体赋反值吧
// 取反，需要处理左右儿子的数字1个数的统计属性
tr[ls].sum = tr[ls].len - tr[ls].sum; // 共10个长度，原来有3个数字1，取反后，就是有3个0，7个1
tr[rs].sum = tr[rs].len - tr[rs].sum;
// 取反，需要处理
swap(tr[ls].mx[0], tr[ls].mx[1]);
swap(tr[ls].lx[0], tr[ls].lx[1]);
swap(tr[ls].rx[0], tr[ls].rx[1]);
swap(tr[rs].mx[0], tr[rs].mx[1]);
swap(tr[rs].lx[0], tr[rs].lx[1]);
swap(tr[rs].rx[0], tr[rs].rx[1]);
// 清空取反懒标记
tr[u].qf = -1;
}
}
void modify(int u, int L, int R, int op) {
int l = tr[u].l, r = tr[u].r, len = r - l + 1; // 范围
if (r < L || l > R) return; // 当前区间与修改区间无交集时
if (l >= L && r <= R) {
if (op <= 1) { // 0: 区间内的所有数全变成 0; 1: 区间内的所有数全变成 1;
tr[u].fz = op; // 统一修改的懒标记
tr[u].qf = 0; // 既然都统一修改了，取反的懒标记就无效了，就听统一修改的了
tr[u].sum = op * len; // 如果op==1,那么就是整个区间都是1，区间长度就是区间和; 如果op==0,那么就是整个区间都是0
tr[u].mx[op] = tr[u].lx[op] = tr[u].rx[op] = len; // 区间连续，左起最长，右起最长都是区间长度
tr[u].mx[op ^ 1] = tr[u].lx[op ^ 1] = tr[u].rx[op ^ 1] = 0; // 异或取反的都设置为0
return;
} else { // op==2,区间内的所有数全部取反
tr[u].qf ^= 1; // 将整体区间取反，这里似乎有点问题，应该是初值是-1才对，为什么这里初始值是0
if (tr[u].fz != -1) tr[u].fz ^= 1; // fz: 整体变0/1; 如果懒标记不是初值，那么懒标记取反,就起到了反转的作用
tr[u].sum = len - tr[u].sum; // 区间长度为10，原来数字1个数为3，那么数字0个数为7。现在取反，则3=>7
swap(tr[u].mx[0], tr[u].mx[1]);
swap(tr[u].lx[0], tr[u].lx[1]);
swap(tr[u].rx[0], tr[u].rx[1]);
return;
}
}
// 分裂前pushdown下传懒标记
pushdown(u);
modify(ls, L, R, op), modify(rs, L, R, op);
pushup(u);
}
int query(int u, int L, int R, int op) {
int l = tr[u].l, r = tr[u].r;
if (r < L || l > R) return 0; // 当前区间与修改区间无交集时
if (L <= l && r <= R) {
if (op == 3) return tr[u].sum; // 区间中数字1的个数
if (op == 4) return tr[u].mx[1]; // 区间内最多有多少个连续的1,这是怎么汇总统计求出来的？没看懂！
}
pushdown(u);
// 区间内总共有多少个 1
if (op == 3) return query(ls, L, R, op) + query(rs, L, R, op);
// 区间内最多有多少个连续的 1
// 先来检查左儿子的最长连续1，再来检查右儿子的最长连续1
// 画图理解
if (op == 4) return max({query(ls, L, R, op), query(rs, L, R, op),
min(mid - L + 1, tr[ls].rx[1]) + min(R - mid, tr[rs].lx[1])});
}
int main() {
#ifndef ONLINE_JUDGE
freopen("P2572.in", "r", stdin);
#endif
// 加快读入
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
build(1, 0, n - 1); // 构建线段树,root=1,管辖范围 [0,n-1]
while (m--) {
int op, l, r;
cin >> op >> l >> r;
if (op < 3)
modify(1, l, r, op);
else
printf("%d\n", query(1, l, r, op));
}
return 0;
}
三、柯朵莉树解法
#include <bits/stdc++.h>
using namespace std;
// 11个测试点，只能通过3个测试点
// 柯朵莉树模板
struct Node {
int l, r; // l和r表示这一段的起点和终点
mutable int v; // v表示这一段上所有元素相同的值是多少,注意关键字 mutable,使得set中结构体属性可修改
bool operator<(const Node &b) const {
return l < b.l; // 规定按照每段的左端点排序
}
};
set<Node> s; // 柯朵莉树的区间集合
// 分裂:[l,x-1],[x,r]
set<Node>::iterator split(int x) {
auto it = s.lower_bound({x});
if (it != s.end() && it->l == x) return it; // 一击命中
it--; // 没有找到就减1个继续找
if (it->r < x) return s.end(); // 真的没找到,返回s.end()
int l = it->l, r = it->r, v = it->v; // 没有被返回，说明找到了,记录下来，防止后面删除时被破坏
s.erase(it); // 删除整个区间
s.insert({l, x - 1, v}); //[l,x-1]拆分
// insert函数返回pair，其中的first是新插入结点的迭代器
return s.insert({x, r, v}).first; //[x,r]拆分
}
// 区间加
void add(int l, int r, int v) {
// 必须先计算itr,后计算itl
auto R = split(r + 1), L = split(l);
for (auto it = L; it != R; it++) it->v += v;
}
// 区间赋值
void assign(int l, int r, int v) {
auto R = split(r + 1), L = split(l);
s.erase(L, R); // 删除旧区间
s.insert({l, r, v}); // 增加新区间
}
void change(int l, int r) {
auto R = split(r + 1), L = split(l);
for (auto it = L; it != R; it++) it->v = !it->v; // 取反,暴力
}
int count1(int l, int r) {
int res = 0;
auto R = split(r + 1), L = split(l);
for (auto it = L; it != R; it++)
res += (it->r - it->l + 1) * it->v;
return res;
}
// 多少个连续的1
int count2(int l, int r) {
int res = 0;
int t = 0;
auto R = split(r + 1), L = split(l);
for (auto it = L; it != R; it++)
if (it->v) {
t += it->r - it->l + 1;
res = max(res, t); // 一定要在t变大后马上取max,不能在下面else里取 max,那样最后的区间会无法得到，造成错误！
} else
t = 0;
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("P2572.in", "r", stdin);
#endif
// 加快读入
ios::sync_with_stdio(false), cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
// 下标从 0 开始
int x;
cin >> x;
s.insert({i, i, x}); // 初始化柯朵莉树
}
while (m--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 0) assign(l, r, 0);
if (op == 1) assign(l, r, 1);
if (op == 2) change(l, r);
if (op == 3) cout << count1(l, r) << endl;
if (op == 4) cout << count2(l, r) << endl;
}
return 0;
}