《P2572 [SCOI2010] 序列操作》
题目描述
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≤n,m≤1000；
对于100% 的数据，1≤n,m≤105。
代码实现：
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 1e5 + 5;
// 线段树节点结构
struct Node {
int l, r; // 区间左右端点
int sum; // 区间内1的个数
int max_len; // 区间内最长连续1长度
int l_max; // 从左端点开始的最长连续1长度
int r_max; // 从右端点开始的最长连续1长度
int tag0, tag1; // 置0、置1标记
int tag2; // 取反标记
} tree[MAXN << 2]; // 线段树数组，大小通常为4*MAXN
int arr[MAXN]; // 原始数组
// 向上合并信息
void push_up(int p) {
// 合并左右子节点信息
tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
// 计算最长连续1长度
tree[p].l_max = tree[p<<1].l_max;
if (tree[p<<1].l_max == tree[p<<1].r - tree[p<<1].l + 1) {
tree[p].l_max += tree[p<<1|1].l_max;
}
tree[p].r_max = tree[p<<1|1].r_max;
if (tree[p<<1|1].r_max == tree[p<<1|1].r - tree[p<<1|1].l + 1) {
tree[p].r_max += tree[p<<1].r_max;
}
tree[p].max_len = max(max(tree[p<<1].max_len, tree[p<<1|1].max_len),
tree[p<<1].r_max + tree[p<<1|1].l_max);
}
// 向下传递标记
void push_down(int p) {
int l = p << 1, r = p << 1 | 1;
int mid = (tree[p].l + tree[p].r) >> 1;
// 处理置0标记
if (tree[p].tag0) {
tree[l].sum = 0;
tree[l].max_len = tree[l].l_max = tree[l].r_max = 0;
tree[l].tag0 = 1;
tree[l].tag1 = tree[l].tag2 = 0;
tree[r].sum = 0;
tree[r].max_len = tree[r].l_max = tree[r].r_max = 0;
tree[r].tag0 = 1;
tree[r].tag1 = tree[r].tag2 = 0;
tree[p].tag0 = 0;
}
// 处理置1标记
if (tree[p].tag1) {
tree[l].sum = mid - tree[l].l + 1;
tree[l].max_len = tree[l].l_max = tree[l].r_max = mid - tree[l].l + 1;
tree[l].tag1 = 1;
tree[l].tag0 = tree[l].tag2 = 0;
tree[r].sum = tree[r].r - mid;
tree[r].max_len = tree[r].l_max = tree[r].r_max = tree[r].r - mid;
tree[r].tag1 = 1;
tree[r].tag0 = tree[r].tag2 = 0;
tree[p].tag1 = 0;
}
// 处理取反标记
if (tree[p].tag2) {
// 交换0和1的数量
tree[l].sum = (mid - tree[l].l + 1) - tree[l].sum;
// 交换最长连续长度
int temp = tree[l].max_len;
tree[l].max_len = (mid - tree[l].l + 1) - temp;
temp = tree[l].l_max;
tree[l].l_max = (mid - tree[l].l + 1) - temp;
temp = tree[l].r_max;
tree[l].r_max = (mid - tree[l].l + 1) - temp;
// 取反标记取反
tree[l].tag2 ^= 1;
swap(tree[l].tag0, tree[l].tag1);
// 处理右子树
tree[r].sum = (tree[r].r - mid) - tree[r].sum;
temp = tree[r].max_len;
tree[r].max_len = (tree[r].r - mid) - temp;
temp = tree[r].l_max;
tree[r].l_max = (tree[r].r - mid) - temp;
temp = tree[r].r_max;
tree[r].r_max = (tree[r].r - mid) - temp;
tree[r].tag2 ^= 1;
swap(tree[r].tag0, tree[r].tag1);
tree[p].tag2 = 0;
}
}
// 构建线段树
void build(int p, int l, int r) {
tree[p].l = l;
tree[p].r = r;
tree[p].tag0 = tree[p].tag1 = tree[p].tag2 = 0;
if (l == r) {
tree[p].sum = arr[l];
tree[p].max_len = tree[p].l_max = tree[p].r_max = arr[l];
return;
}
int mid = (l + r) >> 1;
build(p<<1, l, mid);
build(p<<1|1, mid+1, r);
push_up(p);
}
// 区间置0操作
void update0(int p, int l, int r) {
if (tree[p].l >= l && tree[p].r <= r) {
tree[p].sum = 0;
tree[p].max_len = tree[p].l_max = tree[p].r_max = 0;
tree[p].tag0 = 1;
tree[p].tag1 = tree[p].tag2 = 0;
return;
}
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (l <= mid) update0(p<<1, l, r);
if (r > mid) update0(p<<1|1, l, r);
push_up(p);
}
// 区间置1操作
void update1(int p, int l, int r) {
if (tree[p].l >= l && tree[p].r <= r) {
tree[p].sum = tree[p].r - tree[p].l + 1;
tree[p].max_len = tree[p].l_max = tree[p].r_max = tree[p].r - tree[p].l + 1;
tree[p].tag1 = 1;
tree[p].tag0 = tree[p].tag2 = 0;
return;
}
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (l <= mid) update1(p<<1, l, r);
if (r > mid) update1(p<<1|1, l, r);
push_up(p);
}
// 区间取反操作
void update2(int p, int l, int r) {
if (tree[p].l >= l && tree[p].r <= r) {
// 交换0和1的数量
tree[p].sum = (tree[p].r - tree[p].l + 1) - tree[p].sum;
// 交换最长连续长度
int len = tree[p].r - tree[p].l + 1;
int temp = tree[p].max_len;
tree[p].max_len = len - temp;
temp = tree[p].l_max;
tree[p].l_max = len - temp;
temp = tree[p].r_max;
tree[p].r_max = len - temp;
// 取反标记取反
tree[p].tag2 ^= 1;
swap(tree[p].tag0, tree[p].tag1);
return;
}
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if (l <= mid) update2(p<<1, l, r);
if (r > mid) update2(p<<1|1, l, r);
push_up(p);
}
// 查询区间1的个数
int query3(int p, int l, int r) {
if (tree[p].l >= l && tree[p].r <= r) {
return tree[p].sum;
}
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
int res = 0;
if (l <= mid) res += query3(p<<1, l, r);
if (r > mid) res += query3(p<<1|1, l, r);
return res;
}
// 查询区间最长连续1长度
int query4(int p, int l, int r) {
if (tree[p].l >= l && tree[p].r <= r) {
return tree[p].max_len;
}
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
// 如果查询区间完全在左子树或右子树
if (r <= mid) return query4(p<<1, l, r);
if (l > mid) return query4(p<<1|1, l, r);
// 否则需要考虑跨越中点的情况
int left_res = query4(p<<1, l, mid);
int right_res = query4(p<<1|1, mid+1, r);
// 计算跨越中点的连续1长度
int cross_len = min(tree[p<<1].r_max, mid - l + 1) +
min(tree[p<<1|1].l_max, r - (mid+1) + 1);
return max(max(left_res, right_res), cross_len);
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
build(1, 0, n-1);
while (m--) {
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
if (op == 0) {
update0(1, l, r);
} else if (op == 1) {
update1(1, l, r);
} else if (op == 2) {
update2(1, l, r);
} else if (op == 3) {
printf("%d\n", query3(1, l, r));
} else if (op == 4) {
printf("%d\n", query4(1, l, r));
}
}
return 0;
}