Splay
实际上每个结点的信息可以不用在标记的时候更新(既若结点存在标记则代表结点及其下方所有节点信息都未被更新)。
这样做在更新某个结点的信息时其儿子结点确实可能未被更新,不过我们可以在 push_up 中套嵌两个 push_down 操作即可,这样的代码省去了繁琐的更新操作。
由于这么做,所以每次进行修改类操作时,我们都应该对修改部分连接的父节点进行 Splay 操作,当然在父节点只包含两个点的情况下直接 push_up 那两个点也是一样的。(主要是说不能直接 Splay 或者 push_up 修改部分的根节点,因为这个时候根节点是带懒标记的,push_up 操作只能对不具有懒标记的节点进行(这一点不管用什么方法存储信息都是一样的),所以需要保证所有被 Splay 的节点都是通过 get_k 操作获得位置的(因为 get_k 操作会在沿途进行 push_down,而且也只有这个操作具有 push_down 的功能))
还需注意的一点就是不能对 0 节点进行 push_down,0 节点可以接收懒标记,但其作为一个哨兵不能修改其值,否则会导致答案错误。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
struct node {
int son[2], fa;
int size, sum, sm, sl, sr, val;
int rev, same, to; /// 标记未使用,所以带标记的点不能被 push_up
void init(int _v, int _f) {
son[0] = son[1] = 0; fa = _f;
size = 1; sm = sum = val = _v;
sl = sr = max(_v, 0);
rev = same = 0;
}
} te[500009]; int root;
int tot, ne[500009];
void push_down(int p) {
if(!p) return ; /// 0 点不能被修改值,否则会导致求解 max 和 sum 受到影响
int &l = te[p].son[0], &r = te[p].son[1];
if(te[p].same) {
te[l].same = te[r].same = 1; te[p].same = 0;
te[p].val = te[l].to = te[r].to = te[p].to;
te[p].sum = te[p].size * te[p].to;
te[p].sl = te[p].sr = max(te[p].sum, 0);
te[p].sm = max(te[p].sum, te[p].to);
}
if(te[p].rev) {
te[l].rev ^= 1, te[r].rev ^= 1; te[p].rev = 0;
swap(l, r); swap(te[p].sl, te[p].sr);
}
}
void push_up(int p) {
int l = te[p].son[0], r = te[p].son[1];
push_down(l), push_down(r); /// 需要儿子的真实信息,所以要对儿子 push_down
te[p].size = te[l].size + te[r].size + 1;
te[p].sum = te[l].sum + te[r].sum + te[p].val;
te[p].sm = max(te[l].sr + te[p].val + te[r].sl, max(te[l].sm, te[r].sm));
te[p].sl = max(te[l].sl, te[l].sum + te[p].val + te[r].sl);
te[p].sr = max(te[l].sr + te[p].val + te[r].sum, te[r].sr);
}
int get_k(int k) {
int p = root;
while(p) {
push_down(p);
if(te[te[p].son[0]].size + 1 == k) return p;
if(te[te[p].son[0]].size >= k) p = te[p].son[0];
else k -= te[te[p].son[0]].size + 1, p = te[p].son[1];
}
}
void rotate(int x) {
int y = te[x].fa, z = te[y].fa, c = te[y].son[0] == x;
te[y].son[!c] = te[x].son[c], te[te[x].son[c]].fa = y;
te[y].fa = x, te[x].son[c] = y;
if(z) te[z].son[te[z].son[1] == y] = x; te[x].fa = z;
push_up(y), push_up(x);
}
void splay(int x, int p) {
while(te[x].fa != p) {
int y = te[x].fa, z = te[y].fa;
if(z != p) te[y].son[1] == x ^ te[z].son[1] == y ? rotate(x) : rotate(y);
rotate(x);
}
if(!p) root = x;
}
int fx[500009];
int build(int p, int lx, int rx) {
int mid = lx + rx >> 1;
int u = ne[tot --];
te[u].init(fx[mid], p);
if(lx < mid) te[u].son[0] = build(u, lx, mid - 1);
if(rx > mid) te[u].son[1] = build(u, mid + 1, rx);
push_up(u);
return u;
}
char s[19];
int get_id() {
scanf("%s", s);
if(s[0] == 'I') return 1;
if(s[0] == 'D') return 2;
if(s[0] == 'R') return 4;
if(s[0] == 'G') return 5;
if(s[3] == 'E') return 3;
return 6;
}
void del(int p) {
if(te[p].son[0]) del(te[p].son[0]);
ne[++ tot] = p;
if(te[p].son[1]) del(te[p].son[1]);
}
int main() {
for(int i = 1; i < 500009; i ++) ne[++ tot] = i;
cin >> n >> m;
for(int i = 1; i <= n; i ++) scanf("%d", fx + i);
te[0].sm = -1e9; fx[0] = fx[n + 1] = -1e9;
root = build(0, 0, n + 1);
int pos, tsum, x, l, r;
for(int ttx = 1; ttx <= m; ttx ++) {
int p = get_id();
if(p == 1) {
scanf("%d%d", &pos, &tsum);
l = get_k(pos + 1), r = get_k(pos + 2);
for(int i = 1; i <= tsum; i ++) scanf("%d", fx + i);
splay(l, 0); splay(r, root);
int u = build(r, 1, tsum);
te[r].son[0] = u;
splay(r, 0);
// push_up(r), push_up(l);
} else if(p == 2) {
scanf("%d%d", &pos, &tsum);
l = get_k(pos), r = get_k(pos + tsum + 1);
splay(l, 0); splay(r, root);
del(te[r].son[0]); te[r].son[0] = 0;
splay(r, 0);
// push_up(r), push_up(l);
} else if(p == 3) {
scanf("%d%d%d", &pos, &tsum, &x);
l = get_k(pos), r = get_k(pos + tsum + 1);
splay(l, 0), splay(r, root);
int u = te[r].son[0];
te[u].same = 1, te[u].to = x;
splay(r, 0);
// push_up(r), push_up(l);
} else if(p == 4) {
scanf("%d%d", &pos, &tsum);
l = get_k(pos), r = get_k(pos + tsum + 1);
splay(l, 0), splay(r, root);
x = te[r].son[0];
te[x].rev ^= 1;
splay(r, 0);
// push_up(r), push_up(l);
} else if(p == 5) {
scanf("%d%d", &pos, &tsum);
l = get_k(pos), r = get_k(pos + tsum + 1);
splay(l, 0), splay(r, root);
x = te[r].son[0];
printf("%d\n", te[x].sum);
} else {
printf("%d\n", te[root].sm);
}
}
return 0;
}