有个关于回收空间的问题
查看原帖
有个关于回收空间的问题
751855
zhongpeilin楼主2024/1/5 23:14

为什么我的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;
}
2024/1/5 23:14
加载中...