| 记录编号 |
601943 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
2083.[SCOI2010]序列操作 |
最终得分 |
100 |
| 用户昵称 |
 LikableP |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.482 s |
| 提交时间 |
2025-06-29 17:56:06 |
内存使用 |
9.38 MiB |
显示代码纯文本
#include <algorithm>
#include <cstdio>
const int MAXN = 1e5 + 10;
struct NODE {
int prefixone, prefixzero;
int suffixone, suffixzero;
int maxsubone, maxsubzero;
int len;
int sum;
int set_tag, set_to;
int reverse_tag;
} node[MAXN << 2];
template <typename T> T read();
template <typename T> void write(T, char);
template <typename T> T max(T, T);
void Merge(NODE, NODE, NODE &);
void Build(int, int, int);
void PushDown(int, int, int);
void Set(int, int, int, int, int, int);
void Reverse(int, int, int, int, int);
NODE Ask(int, int, int, int, int);
void Print(int, int, int);
int n, m;
int a[MAXN];
int main() {
freopen("sequence.in", "r", stdin);
freopen("sequence.out", "w", stdout);
n = read<int>(), m = read<int>();
for (int i = 1; i <= n; ++i) {
a[i] = read<int>();
}
Build(1, 1, n);
while (m--) {
int op = read<int>(), l = read<int>(), r = read<int>();
l++, r++;
if (op == 0) Set(1, 1, n, l, r, 0);
else if (op == 1) Set(1, 1, n, l, r, 1);
else if (op == 2) Reverse(1, 1, n, l, r);
else if (op == 3) write(Ask(1, 1, n, l, r).sum, '\n');
else if (op == 4) write(Ask(1, 1, n, l, r).maxsubone, '\n');
// Print(1, 1, n);
// printf("\n");
}
return 0;
}
#define ls(root) root << 1
#define rs(root) root << 1 | 1
void Merge(NODE A, NODE B, NODE &C) {
C.sum = A.sum + B.sum;
C.len = A.len + B.len;
C.prefixone = A.prefixone;
if (A.prefixone == A.len) C.prefixone += B.prefixone;
C.suffixone = B.suffixone;
if (B.suffixone == B.len) C.suffixone += A.suffixone;
C.prefixzero = A.prefixzero;
if (A.prefixzero == A.len) C.prefixzero += B.prefixzero;
C.suffixzero = B.suffixzero;
if (B.suffixzero == B.len) C.suffixzero += A.suffixzero;
C.maxsubone = max(max(A.maxsubone, B.maxsubone), A.suffixone + B.prefixone);
C.maxsubzero = max(max(A.maxsubzero, B.maxsubzero), A.suffixzero + B.prefixzero);
}
void Build(int root, int lt, int rt) {
if (lt == rt) {
node[root].len = 1;
node[root].set_tag = node[root].reverse_tag = node[root].set_to = 0;
if (a[lt]) {
node[root].prefixone = node[root].suffixone = node[root].maxsubone = node[root].sum = 1;
} else {
node[root].prefixzero = node[root].suffixzero = node[root].maxsubzero = 1;
}
return;
}
int mid = lt + ((rt - lt) >> 1);
Build(ls(root), lt, mid);
Build(rs(root), mid + 1, rt);
Merge(node[ls(root)], node[rs(root)], node[root]);
}
void Print(int root, int lt, int rt) {
// printf("###{%d sum:%d prefixon:%d suffixone:%d maxsubone:%d prefixzero:%d suffixzero:%d maxsubzero:%d}\n", root, node[root].sum, node[root].prefixone, node[root].suffixone, node[root].maxsubone, node[root].prefixzero, node[root].suffixzero, node[root].maxsubzero);
if (lt == rt) return;
PushDown(root, lt, rt);
int mid = lt + ((rt - lt) >> 1);
Print(ls(root), lt, mid);
Print(rs(root), mid + 1, rt);
}
void PushDown(int root, int lt, int rt) {
int mid = lt + ((rt - lt) >> 1);
if (node[root].set_tag) {
Set(ls(root), lt, mid, lt, mid, node[root].set_to);
Set(rs(root), mid + 1, rt, mid + 1, rt, node[root].set_to);
node[root].set_tag = false;
}
if (node[root].reverse_tag) {
Reverse(ls(root), lt, mid, lt, mid);
Reverse(rs(root), mid + 1, rt, mid + 1, rt);
node[root].reverse_tag = false;
}
}
void Set(int root, int lt, int rt, int lq, int rq, int val) {
if (lt == lq && rt == rq) {
node[root].set_tag = true;
node[root].set_to = val;
node[root].reverse_tag = false;
if (val) {
node[root].prefixone = node[root].suffixone = node[root].maxsubone = node[root].sum = node[root].len;
node[root].prefixzero = node[root].suffixzero = node[root].maxsubzero = 0;
} else {
node[root].prefixzero = node[root].suffixzero = node[root].maxsubzero = node[root].len;
node[root].prefixone = node[root].suffixone = node[root].maxsubone = node[root].sum = 0;
}
return;
}
PushDown(root, lt, rt);
int mid = lt + ((rt - lt) >> 1);
if (rq <= mid) {
Set(ls(root), lt, mid, lq, rq, val);
} else if (lq > mid) {
Set(rs(root), mid + 1, rt, lq, rq, val);
} else {
Set(ls(root), lt, mid, lq, mid, val);
Set(rs(root), mid + 1, rt, mid + 1, rq, val);
}
Merge(node[ls(root)], node[rs(root)], node[root]);
}
void Reverse(int root, int lt, int rt, int lq, int rq) {
// printf("###[%d %d %d %d %d]\n", root, lt, rt, lq, rq);
// printf("###{sum:%d prefixon:%d suffixone:%d maxsubone:%d prefixzero:%d suffixzero:%d maxsubzero:%d}\n", node[root].sum, node[root].prefixone, node[root].suffixone, node[root].maxsubone, node[root].prefixzero, node[root].suffixzero, node[root].maxsubzero);
if (lt == lq && rt == rq) {
node[root].reverse_tag ^= 1;
::std::swap(node[root].prefixone, node[root].prefixzero);
::std::swap(node[root].suffixone, node[root].suffixzero);
::std::swap(node[root].maxsubone, node[root].maxsubzero);
node[root].sum = node[root].len - node[root].sum;
return;
}
PushDown(root, lt, rt);
int mid = lt + ((rt - lt) >> 1);
if (rq <= mid) {
Reverse(ls(root), lt, mid, lq, rq);
} else if (lq > mid) {
Reverse(rs(root), mid + 1, rt, lq, rq);
} else {
Reverse(ls(root), lt, mid, lq, mid);
Reverse(rs(root), mid + 1, rt, mid + 1, rq);
}
Merge(node[ls(root)], node[rs(root)], node[root]);
}
NODE Ask(int root, int lt, int rt, int lq, int rq) {
if (lt == lq && rt == rq) {
return node[root];
}
PushDown(root, lt, rt);
int mid = lt + ((rt - lt) >> 1);
if (rq <= mid) {
return Ask(ls(root), lt, mid, lq, rq);
} else if (lq > mid) {
return Ask(rs(root), mid + 1, rt, lq, rq);
} else {
NODE A = Ask(ls(root), lt, mid, lq, mid);
NODE B = Ask(rs(root), mid + 1, rt, mid + 1, rq);
NODE C;
Merge(A, B, C);
return C;
}
}
template <typename T> T max(T x, T y) {
return x > y ? x : y;
}
#define isdigit(ch) (ch >= '0' && ch <= '9')
template <typename T> T read() {
T res = 0, f = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
return res * f;
}
template <typename T> void write(T x, char ed) {
if (x < 0) x = -x, putchar('-');
static int sta[sizeof(T) << 2], top = 0;
do {
sta[++top] = x % 10;
x /= 10;
} while (x);
while (top) {
putchar(sta[top--] ^ 48);
}
putchar(ed);
}