记录一道大数据结构题
操作都是基本操作 pushup细节挺多
#include <iostream>
const int N = 100010;
using namespace std;
int n, m;
int tot, root;
struct Node {
int s[2], p, v;
int lc, rc, ls, rs, ms;
int size, sum;
int neg, rev, cov;
void init(int v, int p) {
this->v = v, this->p = p;
s[0] = s[1] = 0;
size = 1;
neg = rev = 0;
cov = -1;
ls = rs = ms = 1;
lc = rc = sum = v;
}
} tr[N];
string s;
void pushup(int x) {
auto &u = tr[x], &l = tr[u.s[0]], &r = tr[u.s[1]];
u.size = l.size + r.size + 1;
u.sum = l.sum + r.sum + u.v;
if (u.s[0] && u.s[1]) {
u.ms = max(l.ms, r.ms);
u.ls = l.ls, u.lc = l.lc;
u.rs = r.rs, u.rc = r.rc;
if (l.rc == r.lc && l.rc == u.v) {
u.ms = max(u.ms, l.rs + r.ls + 1);
if (l.ls == l.size) u.ls = l.ls + r.ls + 1;
if (r.rs == r.size) u.rs = r.rs + l.rs + 1;
}
else if (l.rc == u.v) {
if (l.ls == l.size) u.ls = l.ls + 1;
u.ms = max(u.ms, l.rs + 1);
}
else if (r.lc == u.v) {
if (r.rs == r.size) u.rs = r.rs + 1;
u.ms = max(u.ms, r.ls + 1);
}
}
else if (u.s[0]) {
u.lc = l.lc, u.rc = u.v;
u.ls = l.ls, u.ms = l.ms;
if (l.ls == l.size && l.rc == u.v) u.ls = l.ls + 1;
if (l.rc == u.v) u.ms = max(u.ms, l.rs + 1), u.rs = l.rs + 1;
else u.rs = 1;
}
else if (u.s[1]) {
u.rc = r.rc, u.lc = u.v;
u.rs = r.rs, u.ms = r.ms;
if (r.rs == r.size && r.lc == u.v) u.rs = r.rs + 1;
if (r.lc == u.v) u.ms = max(u.ms, r.ls + 1), u.ls = r.ls + 1;
else u.ls = 1;
}
else {
u.lc = u.rc = u.v;
u.ls = u.rs = u.ms = 1;
}
}
void pushcov(int x, int c) {
tr[x].cov = c;
tr[x].neg = tr[x].rev = 0;
tr[x].lc = tr[x].rc = tr[x].v = c;
tr[x].ls = tr[x].rs = tr[x].ms = tr[x].size;
tr[x].sum = c * tr[x].size;
}
void pushrev(int x) {
tr[x].rev ^= 1;
swap(tr[x].ls, tr[x].rs);
swap(tr[x].lc, tr[x].rc);
}
void pushneg(int x) {
tr[x].sum = tr[x].size - tr[x].sum;
tr[x].lc ^= 1, tr[x].rc ^= 1;
tr[x].v ^= 1, tr[x].neg ^= 1;
}
void pushdown(int x) {
auto &u = tr[x];
if (~u.cov) {
if (u.s[0]) pushcov(u.s[0], u.cov);
if (u.s[1]) pushcov(u.s[1], u.cov);
u.cov = -1;
}
if (u.rev) {
if (u.s[0]) pushrev(u.s[0]);
if (u.s[1]) pushrev(u.s[1]);
swap(u.s[0], u.s[1]);
u.rev = 0;
}
if (u.neg) {
if (u.s[0]) pushneg(u.s[0]);
if (u.s[1]) pushneg(u.s[1]);
u.neg = 0;
}
}
void rotate(int x) {
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y, tr[y].p = x;
pushup(y), pushup(x);
}
void splay(int x, int k) {
while (tr[x].p != k) {
int y = tr[x].p, z = tr[y].p;
if (z != k)
if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
else rotate(y);
rotate(x);
}
if (!k) root = x;
}
int get_k(int k) {
int u = root;
while (u) {
pushdown(u);
int s = tr[tr[u].s[0]].size;
if (s >= k) u = tr[u].s[0];
else if (s + 1 == k) return u;
else k -= s + 1, u = tr[u].s[1];
}
return -1;
}
int build(int l, int r, int p) {
int mid = l + r >> 1;
int u = ++tot;
tr[u].init(s[mid] - '0', p);
if (l < mid) tr[u].s[0] = build(l, mid - 1, u);
if (r > mid) tr[u].s[1] = build(mid + 1, r, u);
pushup(u);
return u;
}
int main() {
cin >> n >> m >> s;
s = ' ' + s;
s[0] = '2', s[n + 1] = '3';
root = build(0, n + 1, 0);
while (m--) {
int op, l, r;
cin >> op >> l >> r;
int L = get_k(l), R = get_k(r + 2);
splay(L, 0), splay(R, L);
int rt = tr[R].s[0];
if (op == 1) pushneg(rt), pushup(R), pushup(L);
if (op == 2) pushrev(rt), pushup(R), pushup(L);
if (op == 4) pushcov(rt, 0), pushup(R), pushup(L);
if (op == 5) pushcov(rt, 1), pushup(R), pushup(L);
if (op == 3) {
int len = r - l + 1;
int one = tr[rt].sum, zero = len - one;
if (zero) {
L = get_k(l), R = get_k(l + zero + 1);
splay(L, 0), splay(R, L);
pushcov(tr[R].s[0], 0);
pushup(R), pushup(L);
}
if (one) {
L = get_k(l + zero), R = get_k(r + 2);
splay(L, 0), splay(R, L);
pushcov(tr[R].s[0], 1);
pushup(R), pushup(L);
}
}
cout << tr[root].ms << '\n';
}
return 0;
}