MrcFrst @ 2023-09-21 11:17:03
在 pushdown 翻转标记的时候，如果儿子的标记为覆盖，那么就把儿子的覆盖标记取反，就是如果儿子的标记是覆盖为 1，那就改成覆盖为 0。
否则，就把儿子的翻转标记 ^=1。
by Struct_Sec @ 2023-09-21 11:57:23
orzorzorzorz
by SunsetLake @ 2023-09-21 14:20:27
内卷线段树！！
by CWzwz @ 2023-09-21 15:32:35
sto路人缘orz！！！
by CWzwz @ 2023-09-21 16:09:07
@MrcFrst_LRY 大佬求调，还是wa的
//Problem: P2572
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define i32 INT_MAX
#define i64 LONG_LONG_MAX
#define pii pair<int, int>
#define pll pair<long long, long long>
#define push_back pb
#define mid (l + r >> 1)
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;}
void print(int x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}
int n, q;
int a[N];
struct segt {
struct node {
int l, r, l0, r0, mx, mx0, s, s0, tgc, tgr, havtgc;
} t[N << 2];
node unt = (node){0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int maxx(int a, int b, int c) {
return max(a, max(b, c));
}
void pushup(int u, int l, int r) {
t[u].l = t[u << 1].l + ((t[u << 1].l == mid - l + 1) ? t[u << 1 | 1].l : 0);
t[u].l0 = t[u << 1].l0 + ((t[u << 1].l0 == mid - l + 1) ? t[u << 1 | 1].l0 : 0);
t[u].r = t[u << 1 | 1].r + ((t[u << 1 | 1].r == r - mid) ? t[u << 1].r : 0);
t[u].r0 = t[u << 1 | 1].r0 + ((t[u << 1 | 1].r0 == r - mid) ? t[u << 1].r0 : 0);
t[u].mx = maxx(t[u << 1].mx, t[u << 1 | 1].mx, t[u << 1].r + t[u << 1 | 1].l);
t[u].mx0 = maxx(t[u << 1].mx0, t[u << 1 | 1].mx0, t[u << 1].r0 + t[u << 1 | 1].l0);
t[u].s = t[u << 1].s + t[u << 1 | 1].s;
t[u].s0 = t[u << 1].s0 + t[u << 1 | 1].s0;
}
void pushdown(int u, int l, int r) {
if(t[u].havtgc) {
t[u << 1].l = t[u << 1].r = t[u << 1].mx = t[u << 1].s = t[u].tgc ? (mid - l + 1) : 0;
t[u << 1 | 1].l = t[u << 1 | 1].r = t[u << 1 | 1].mx = t[u << 1 | 1].s = t[u].tgc ? (r - mid) : 0;
t[u << 1].l0 = t[u << 1].r0 = t[u << 1].mx0 = t[u << 1].s0 = (!t[u].tgc) ? (mid - l + 1) : 0;
t[u << 1 | 1].l0 = t[u << 1 | 1].r0 = t[u << 1 | 1].mx0 = t[u << 1 | 1].s0 = (!t[u].tgc) ? (r - mid) : 0;
t[u << 1].tgc = t[u << 1 | 1].tgc = t[u].tgc;
t[u << 1].havtgc = t[u << 1 | 1].havtgc = 1;
t[u].havtgc = 0;
}
if(t[u].tgr) {
if(t[u << 1].havtgc) t[u << 1].tgc ^= 1;
else t[u << 1].tgr ^= 1;
if(t[u << 1 | 1].havtgc) t[u << 1 | 1].tgc ^= 1;
else t[u << 1 | 1].tgr ^= 1;
swap(t[u << 1].l, t[u << 1].l0);
swap(t[u << 1].r, t[u << 1].r0);
swap(t[u << 1].mx, t[u << 1].mx0);
swap(t[u << 1].s, t[u << 1].s0);
swap(t[u << 1 | 1].l, t[u << 1 | 1].l0);
swap(t[u << 1 | 1].r, t[u << 1 | 1].r0);
swap(t[u << 1 | 1].mx, t[u << 1 | 1].mx0);
swap(t[u << 1 | 1].s, t[u << 1 | 1].s0);
t[u].tgr = 0;
}
}
void build(int u, int l, int r) {
if(l == r) {
t[u].l = t[u].r = t[u].mx = t[u].s = a[l];
t[u].l0 = t[u].r0 = t[u].mx0 = t[u].s0 = (!a[l]);
return;
}
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u, l, r);
}
void update(int u, int l, int r, int L, int R, int val) {
if(L <= l && r <= R) {
t[u].havtgc = 1;
t[u].tgc = val;
t[u].tgr = 0;
t[u].l = t[u].r = t[u].mx = t[u].s = val ? (r - l + 1) : 0;
t[u].l0 = t[u].r0 = t[u].mx0 = t[u].s0 = val ? 0 : (r - l + 1);
return;
}
pushdown(u, l, r);
if(L <= mid) update(u << 1, l, mid, L, R, val);
if(mid < R) update(u << 1 | 1, mid + 1, r, L, R, val);
pushup(u, l, r);
}
void reverse(int u, int l, int r, int L, int R) {
if(L <= l && r <= R) {
if(t[u].havtgc) t[u].tgc ^= 1;
else t[u].tgr ^= 1;
swap(t[u].l, t[u].l0);
swap(t[u].r, t[u].r0);
swap(t[u].s, t[u].s0);
swap(t[u].mx, t[u].mx0);
return;
}
pushdown(u, l, r);
if(L <= mid) reverse(u << 1, l, mid, L, R);
if(mid < R) reverse(u << 1 | 1, mid + 1, r, L, R);
pushup(u, l, r);
}
int query(int u, int l, int r, int L, int R) {
if(L <= l && r <= R) {
return t[u].s;
}
int res = 0;
pushdown(u, l, r);
if(L <= mid) res += query(u << 1, l, mid, L, R);
if(mid < R) res += query(u << 1 | 1, mid + 1, r, L, R);
return res;
}
node ask(int u, int l, int r, int L, int R) {
if(L <= l && r <= R) {
return t[u];
}
node res = unt;
pushdown(u, l, r);
if(L > mid) {
res = ask(u << 1 | 1, mid + 1, r, L, R);
} else if(mid >= R) {
res = ask(u << 1, l, mid, L, R);
} else {
node tmp1 = ask(u << 1, l, mid, L, R), tmp2 = ask(u << 1 | 1, mid + 1, r, L, R);
res.mx = maxx(tmp1.mx, tmp2.mx, tmp1.r + tmp2.l);
res.l = tmp1.l + ((tmp1.l == mid - l + 1) ? tmp2.l : 0);
res.r = tmp2.r + ((tmp2.r == r - mid) ? tmp1.r : 0);
}
return res;
}
} T;
int main() {
cin >> n >> q;
for(int i = 1; i <= n; i++) a[i] = read();
T.build(1, 1, n);
while(q--) {
int opt = read(), x = read() + 1, y = read() + 1;
if(opt == 0) {
T.update(1, 1, n, x, y, 0);
} else if(opt == 1) {
T.update(1, 1, n, x, y, 1);
} else if(opt == 2) {
T.reverse(1, 1, n, x, y);
} else if(opt == 3) {
print(T.query(1, 1, n, x, y));
puts("");
} else {
print(T.ask(1, 1, n, x, y).mx);
puts("");
}
}
return 0;
}
by MrcFrst @ 2023-09-27 18:19:59
@CWzwz QwQ
by CWzwz @ 2023-09-27 18:50:01
@MrcFrst_LRY 已A，此贴结（bushi
by Creeper_l @ 2023-12-15 21:14:10
感谢您嘞
by STUDENT00 @ 2024-01-16 17:36:07
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOrz
by zyl1543130456 @ 2024-02-19 08:16:02
神医Orz
by CLydq @ 2024-12-10 15:58:08
神医 Orz
但是我改完 0->10 pts