zxh_mc @ 2022-10-19 20:54:53
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N];
struct val {
int lm, rm, m, mk, l, r;
};
struct node {
int l, r, lmo, rmo, num, flag, mz, mo, lmz, rmz; //flag = 1: 全0 flag = 2: 全1 flag = 3:全反
}tree[N * 4];
inline void update (int p, int op) {
tree[p].flag = op;
if (op == 1) {
tree[p].num = tree[p].lmo = tree[p].rmo = tree[p].mo = 0;
tree[p].lmz = tree[p].rmz = tree[p].mz = tree[p].r - tree[p].l + 1;
}
else if (op == 2) {
tree[p].num = tree[p].lmo = tree[p].rmo = tree[p].mo = tree[p].r - tree[p].l + 1;
tree[p].lmz = tree[p].rmz = tree[p].mz = 0;
}
else if (op == 3) {
swap(tree[p].lmo, tree[p].lmz);
swap(tree[p].rmo, tree[p].rmz);
swap(tree[p].mo, tree[p].mz);
tree[p].num = tree[p].r - tree[p].l + 1 - tree[p].num;
}
}
inline void push_up(int p) {
tree[p].num = tree[p * 2].num + tree[p * 2 + 1].num;
tree[p].mo = max(max(tree[p * 2].mo, tree[p * 2 + 1].mo), tree[p * 2].lmo + tree[p * 2 + 1].rmo);
tree[p].mz = max(max(tree[p * 2].mz, tree[p * 2 + 1].mz), tree[p * 2].lmz + tree[p * 2 + 1].rmz);
if (tree[p * 2].rmo < tree[p * 2].r - tree[p * 2].l + 1) tree[p].rmo = tree[p * 2].rmo;
else tree[p].rmo = tree[p * 2].rmo + tree[p * 2 + 1].rmo;
if (tree[p * 2 + 1].lmo < tree[p * 2 + 1].r - tree[p * 2 + 1].l + 1) tree[p].lmo = tree[p * 2 + 1].lmo;
else tree[p].lmo = tree[p * 2 + 1].lmo + tree[p * 2].lmo;
if (tree[p * 2].rmz < tree[p * 2].r - tree[p * 2].l + 1) tree[p].rmz = tree[p * 2].rmz;
else tree[p].rmz = tree[p * 2].rmz + tree[p * 2 + 1].rmz;
if (tree[p * 2 + 1].lmz < tree[p * 2 + 1].r - tree[p * 2 + 1].l + 1) tree[p].lmz = tree[p * 2 + 1].lmz;
else tree[p].lmz = tree[p * 2 + 1].lmz + tree[p * 2].lmz;
}
inline void push_down(int p) {
update(p * 2, tree[p].flag); update(p * 2 + 1, tree[p].flag);
tree[p].flag = 0;
}
void build (int p, int l, int r) {
tree[p].l = l, tree[p].r = r;
if (l == r) {
if (a[l]) tree[p].lmo = tree[p].rmo = tree[p].mo = tree[p].num = 1;
else tree[p].lmz = tree[p].rmz = tree[p].mz = 1;
return;
}
int mid = (l + r) >> 1;
if (l <= mid) build(p * 2, l, mid);
if (r > mid) build(p * 2 + 1, mid + 1, r);
push_up(p);
}
void add (int p, int l, int r, int op) {
int tl = tree[p].l, tr = tree[p].r;
if (tree[p].flag) push_down(p);
if (tl >= l && tr <= r) {
update(p, op);
return;
}
int mid = (tl + tr) >> 1;
if (l <= mid) add(p * 2, l, r, op);
if (r > mid) add(p * 2 + 1, l, r, op);
push_up(p);
}
int qp4 (int p, int l, int r) {
int tl = tree[p].l, tr = tree[p].r;
if (tree[p].flag) push_down(p);
if (tl >= l && tr <= r) return tree[p].num;
int mid = (tl + tr) >> 1, res = 0;
if (l <= mid) res += qp4(p * 2, l, r);
if (r > mid) res += qp4(p * 2 + 1, l, r);
return res;
}
val qp5 (int p, int l, int r) {
int tl = tree[p].l, tr = tree[p].r, lm = tree[p].lmo, rm = tree[p].rmo, m = tree[p].mo;
if (tree[p].flag) push_down(p);
if (tl >= l && tr <= r) return (val){lm, rm, m, 1, tl, tr};
int mid = (tl + tr) >> 1;
val a, b, c;
a = b = c = (val){0, 0, 0, 0, 0, 0};
c.mk = 1;
if (l <= mid) a = qp5(p * 2, l, r);
if (r > mid) b = qp5(p * 2 + 1, l, r);
if (!b.mk) return a;
if (!a.mk) return b;
c.m = max(max(a.m, b.m), a.lm + b.rm);
if (a.rm < a.r - a.l + 1) c.rm = a.rm;
else c.rm = a.rm + b.rm;
if (b.lm < b.r - b.l + 1) c.lm = b.lm;
else c.lm = b.lm + a.lm;
c.l = a.l, c.r = b.r;
return c;
}
int main () {
scanf("%d%d", &n, &m);
for (int i = 1;i <= n;i++) scanf("%d", &a[i]);
build(1, 1, n);
while (m--) {
int op, l, r;
scanf("%d%d%d", &op, &l, &r);
l++;r++;
if (op <= 2) add(1, l, r, op + 1);
else if (op == 3) printf("%d\n", qp4(1, l, r));
else printf("%d\n", qp5(1, l, r).m);
}
return 0;
}
感觉思路没错,调出来几个bug还是不过
by xingke233 @ 2022-10-19 20:59:47
@zxh_minecraft
找不到bug,就重构
这题我之前调了一下午才调出来
by zxh_mc @ 2022-10-20 12:33:38
已经A力