社区讨论
求助:问:queryl怎么写?
P2572[SCOI2010] 序列操作参与者 5已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mhjhz3u7
- 此快照首次捕获于
- 2025/11/04 02:52 4 个月前
- 此快照最后确认于
- 2025/11/04 02:52 4 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 110000;
struct TreeNode {
int q[2];
int h[2];
int num[2];
int maxn[2];
int sz;
int tag;
} seg[N * 4];
int n, m, a[N];
inline void settag(int id) {
swap(seg[id].q[0], seg[id].q[1]);
swap(seg[id].h[0], seg[id].h[1]);
swap(seg[id].num[0], seg[id].num[1]);
swap(seg[id].maxn[0], seg[id].maxn[1]);
}
inline void update(int id) {
seg[id].q[0] = seg[id * 2].q[0] + (seg[id * 2].sz == seg[id * 2].q[0] ? seg[id * 2 + 1].q[0] : 0);
seg[id].q[1] = seg[id * 2].q[1] + (seg[id * 2].sz == seg[id * 2].q[1] ? seg[id * 2 + 1].q[1] : 0);
seg[id].h[0] = seg[id * 2 + 1].h[0] + (seg[id * 2 + 1].sz == seg[id * 2 + 1].h[0] ? seg[id * 2].h[0] : 0);
seg[id].h[1] = seg[id * 2 + 1].h[1] + (seg[id * 2 + 1].sz == seg[id * 2 + 1].h[1] ? seg[id * 2].h[1] : 0);
seg[id].num[0] = seg[id * 2].num[0] + seg[id * 2 + 1].num[0];
seg[id].num[1] = seg[id * 2].num[1] + seg[id * 2 + 1].num[1];
seg[id].maxn[0] = max(seg[id * 2].h[0] + seg[id * 2 + 1].q[0], max(seg[id * 2].q[0], seg[id * 2 + 1].h[0]));
seg[id].maxn[1] = max(seg[id * 2].h[1] + seg[id * 2 + 1].q[1], max(seg[id * 2].q[1], seg[id * 2 + 1].h[1]));
}
inline void pushdown(int id) {
int tag = seg[id].tag;
if (tag) {
settag(id * 2);
settag(id * 2 + 1);
seg[id].tag = 0;
}
}
inline void build(int id, int l, int r) {
seg[id] = {{0, 0}, {0, 0}, {0, 0}, {0, 0}, r - l + 1, 0};
if (l == r) {
seg[id].q[0] = (a[l] == 0);
seg[id].q[1] = (a[l] == 1);
seg[id].h[0] = (a[l] == 0);
seg[id].h[1] = (a[l] == 1);
seg[id].num[0] = (a[l] == 0);
seg[id].num[1] = (a[l] == 1);
seg[id].maxn[0] = (a[l] == 0);
seg[id].maxn[1] = (a[l] == 1);
return;
}
int m = (l + r) / 2;
build(id * 2, l, m);
build(id * 2 + 1, m + 1, r);
update(id);
}
inline void modify(int id, int l, int r, int ql, int qr, int ty) {
if (l >= ql && r <= qr) {
if (ty == 0) {
seg[id].q[0] = seg[id].sz;
seg[id].q[1] = 0;
seg[id].h[0] = seg[id].sz;
seg[id].h[1] = 0;
seg[id].num[0] = seg[id].sz;
seg[id].num[1] = 0;
seg[id].maxn[0] = seg[id].sz;
seg[id].maxn[1] = 0;
seg[id].tag = 0;
}
else if (ty == 1) {
seg[id].q[0] = 0;
seg[id].q[1] = seg[id].sz;
seg[id].h[0] = 0;
seg[id].h[1] = seg[id].sz;
seg[id].num[0] = 0;
seg[id].num[1] = seg[id].sz;
seg[id].maxn[0] = 0;
seg[id].maxn[1] = seg[id].sz;
seg[id].tag = 0;
}
else {
swap(seg[id].q[0], seg[id].q[1]);
swap(seg[id].h[0], seg[id].h[1]);
swap(seg[id].num[0], seg[id].num[1]);
swap(seg[id].maxn[0], seg[id].maxn[1]);
seg[id].tag ^= 1;
}
return;
}
pushdown(id);
int m = (l + r) / 2;
if (ql <= m)
modify(id * 2, l, m, ql, qr, ty);
if (qr > m)
modify(id * 2 + 1, m + 1, r, ql, qr, ty);
update(id);
}
inline int queryt(int id, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr)
return seg[id].num[1];
pushdown(id);
int m = (l + r) / 2;
if (ql <= m && qr > m)
return queryt(id * 2, l, m, ql, qr) + queryt(id * 2 + 1, m + 1, r, ql, qr);
if (ql <= m)
return queryt(id * 2, l, m, ql, qr);
else
return queryt(id * 2 + 1, m + 1, r, ql, qr);
}
inline int queryl(int id, int l, int r, int ql, int qr) {
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, 1, n);
for (; m--; ) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
x++, y++;
if (op == 0)
modify(1, 1, n, x, y, 0);
else if (op == 1)
modify(1, 1, n, x, y, 1);
else if (op == 2)
modify(1, 1, n, x, y, 2);
else if (op == 3)
printf("%d\n", queryt(1, 1, n, x, y));
else
printf("%d\n", queryl(1, 1, n, x, y));
}
return 0;
}
有点屎山……
调出必关
回复
共 4 条回复,欢迎继续交流。
正在加载回复...