为什么我的Splay无论怎么改加了回收之后都是40啊?请问有路过的dalao来看看吗?感觉和题解差不多。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x = 0, f = 1;
char op = getchar();
while(op < '0' || op > '9') {
if(op == '-') f = -1;
op = getchar();
}
while(op >= '0' && op <= '9'){
x = x * 10 + (op - '0');
op = getchar();
}
return x * f;
}
struct Splay{
int ch[2], fa, val, sz, taga, tagb, lsum, rsum, sum, ans;
}tree[1000005];
char op[15];
int n, m, treaprt, tot = 500005, a[4000005];
int q[5000005], L = 1, R = 500004;
int get_ch(int x){
return (x == tree[tree[x].fa].ch[1]);
}
void clear(int u){
tree[u].ch[0] = tree[u].ch[1] = 0;
tree[u].fa = tree[u].val = tree[u].sz = 0;
tree[u].tagb = -114514;
tree[u].lsum = tree[u].rsum = tree[u].sum = 0;
tree[u].ans = -2147364847;
}
void Suana(int u){
swap(tree[u].ch[0], tree[u].ch[1]);
swap(tree[u].lsum, tree[u].rsum);
tree[u].taga ^= 1;
}
void Suanb(int u, int col){
tree[u].taga = 0;
tree[u].val = col;
tree[u].sum = tree[u].sz * col;
tree[u].lsum = max(col, tree[u].sum);
tree[u].rsum = max(col, tree[u].sum);
tree[u].ans = tree[u].lsum;
tree[u].tagb = col;
}
void push_up(int u){
int lson = tree[u].ch[0], rson = tree[u].ch[1];
tree[u].sum = tree[lson].sum + tree[rson].sum + tree[u].val;
tree[u].lsum = max({tree[lson].lsum, tree[lson].sum + tree[u].val, tree[lson].sum + tree[u].val + tree[rson].lsum});
tree[u].rsum = max({tree[rson].rsum, tree[rson].sum + tree[u].val, tree[rson].sum + tree[u].val + tree[lson].rsum});
tree[u].sz = tree[lson].sz + tree[rson].sz + 1;
tree[u].ans = max({tree[lson].ans, tree[lson].rsum + tree[u].val, tree[lson].rsum + tree[u].val + tree[rson].lsum});
tree[u].ans = max({tree[u].ans, tree[rson].ans, tree[rson].lsum + tree[u].val, tree[u].val});
return ;
}
void push_down(int u){
if(tree[u].tagb != -114514){
if(tree[u].ch[0]) Suanb(tree[u].ch[0], tree[u].tagb);
if(tree[u].ch[1]) Suanb(tree[u].ch[1], tree[u].tagb);
tree[u].tagb = -114514;
tree[u].taga = 0;
}
if(tree[u].taga){
if(tree[u].ch[0]) Suana(tree[u].ch[0]);
if(tree[u].ch[1]) Suana(tree[u].ch[1]);
tree[u].taga = 0;
}
}
void zigzag(int x){
int y = tree[x].fa, z = tree[y].fa;
int chk = get_ch(x);
push_down(z);
push_down(y);
push_down(x);
tree[y].ch[chk] = tree[x].ch[chk ^ 1];
if(tree[x].ch[chk ^ 1]) tree[tree[x].ch[chk ^ 1]].fa = y;
tree[x].ch[chk ^ 1] = y;
tree[x].fa = z;
tree[y].fa = x;
if(z) tree[z].ch[y == tree[z].ch[1]] = x;
push_up(y);
push_up(x);
}
void splaying(int u, int lst){
for(int x = tree[u].fa; x = tree[u].fa, x != lst; zigzag(u)){
if(tree[x].fa != lst){
zigzag((get_ch(u) == get_ch(x)) ? x : u);
}
push_up(u);
}
if(lst == 0) treaprt = u;
}
int get_suf(){
push_down(treaprt);
int u = tree[treaprt].ch[1];
if(!u) return u;
while(tree[u].ch[0]) push_down(u), u = tree[u].ch[0];
splaying(u, treaprt);
return u;
}
int get_num(int pos, int lst){
int u = treaprt;
while(u) {
push_down(u);
if(tree[tree[u].ch[0]].sz + 1 == pos){
splaying(u, lst);
return u;
}
if(tree[tree[u].ch[0]].sz >= pos){
u = tree[u].ch[0];
} else {
pos -= tree[tree[u].ch[0]].sz + 1;
u = tree[u].ch[1];
}
}
return u;
}
void Insert(int pos, int id){
if(!treaprt){
treaprt = id;
return ;
}
int u = get_num(pos, 0);
int suf = get_suf();
if(!suf){
tree[treaprt].ch[1] = id;
push_up(treaprt);
splaying(id, 0);
return ;
}
tree[suf].ch[0] = id;
tree[id].fa = suf;
push_up(suf);
splaying(id, 0);
}
int build(int fa, int l, int r){
if(l > r) return 0;
int mid = (l + r) / 2;
int u;
if(L <= R){
u = q[L++];
} else {
u = ++tot;
}
tree[u].tagb = -114514;
tree[u].fa = fa;
tree[u].val = a[mid];
tree[u].ch[0] = build(u, l, mid - 1);
tree[u].ch[1] = build(u, mid + 1, r);
push_up(u);
return u;
}
void dfs(int u){
if(!u) return ;
dfs(tree[u].ch[0]);
dfs(tree[u].ch[1]);
q[++R] = u;
clear(u);
}
void solve_insert(int pos, int len){
for(int i = 1; i <= len; i++) a[i] = read();
int rt = build(0, 1, len);
Insert(pos, rt);
}
void solve_erase(int pos, int len){
int l = pos, r = pos + len + 1;
get_num(l, 0);
int num = get_num(r, treaprt);
dfs(tree[num].ch[0]);
tree[num].ch[0] = 0;
push_up(num);
splaying(num, 0);
}
void solve_same(int pos, int len, int col){
int l = pos, r = pos + len + 1;
get_num(l, 0);
int num = get_num(r, treaprt);
if(tree[num].ch[0]) Suanb(tree[num].ch[0], col);
splaying(num, 0);
}
void solve_reverse(int pos, int len){
int l = pos, r = pos + len + 1;
get_num(l, 0);
int num = get_num(r, treaprt);
if(tree[num].ch[0]) Suana(tree[num].ch[0]);
splaying(num, 0);
}
int solve_getsum(int pos, int len){
int l = pos, r = pos + len + 1;
get_num(l, 0);
int num = get_num(r, treaprt);
return tree[tree[num].ch[0]].sum;
}
signed main(){
n = read(); m = read();
tree[0].ans = -2147364847;
for(int i = 1; i <= 500004; i++) q[i] = i;
a[0] = -600000000;
for(int i = 1; i <= n; i++) a[i] = read();
a[n + 1] = -600000000;
treaprt = build(0, 0, n + 1);
while(m--){
scanf("%s", op + 1);
int len, pos, col;
if(op[3] == 'S'){
pos = read(); len = read();
if(len == 0) continue;
solve_insert(pos + 1, len);
} else if(op[3] == 'L'){
pos = read(); len = read();
if(len == 0) continue;
solve_erase(pos, len);
} else if(op[3] == 'K'){
pos = read(); len = read(); col = read();
if(len == 0) continue;
solve_same(pos, len, col);
} else if(op[3] == 'V'){
pos = read(); len = read();
if(len == 0) continue;
solve_reverse(pos, len);
} else if(op[3] == 'T'){
pos = read(); len = read();
if(len == 0) puts("0");
else printf("%lld\n", solve_getsum(pos, len));
} else {
printf("%lld\n", tree[treaprt].ans);
}
}
return 0;
}