欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【luogu P5055】【模板】可持久化文艺平衡树

程序员文章站 2024-03-03 19:12:58
...

【模板】可持久化文艺平衡树

题目链接:luogu P5055

题目大意

要你维护插入,删除,区间翻转,区间求和。
但要求可持续化,即每次操作在一个历史版本上进行,且会产生一个新的历史版本

思路

看到题目都是可持续化平衡树了。

直接上 splay,这题要多搞一个 down。
down 交换左右儿子之前要复制左右儿子。

然后其他的就跟 可持久化平衡树 是差不多的了。

代码

#include<queue>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long

using namespace std;

int n, rt[200001], bb, op, x, y, tot;
int ls[200001 << 7], rs[200001 << 7], yj[200001 << 7], sz[200001 << 7];
bool turn[200001 << 7];
ll sum[200001 << 7], lastans, val[200001 << 7];

int newpoint(ll num) {
	int re = ++tot;
	ls[re] = rs[re] = turn[re] = 0;
	val[re] = num;
	sum[re] = num;
	yj[re] = rand();
	sz[re] = 1;
	return re;
}

int copypoint(int pl) {
	int re = ++tot;
	ls[re] = ls[pl];
	rs[re] = rs[pl];
	val[re] = val[pl];
	sum[re] = sum[pl];
	yj[re] = yj[pl];
	turn[re] = turn[pl];
	sz[re] = sz[pl];
	return re;
}

void up(int now) {
	sz[now] = sz[ls[now]] + sz[rs[now]] + 1;
	sum[now] = sum[ls[now]] + sum[rs[now]] + val[now];
}

void down(int now) {
	if (turn[now]) {
		if (ls[now]) ls[now] = copypoint(ls[now]);//记得翻转前左右儿子要复制
		if (rs[now]) rs[now] = copypoint(rs[now]);
		swap(ls[now], rs[now]);
		if (ls[now]) turn[ls[now]] ^= 1;
		if (rs[now]) turn[rs[now]] ^= 1;
		turn[now] ^= 1;
	}
} 

pair <int, int> split_rnk(int now, int rnk) {
	if (!now) return make_pair(0, 0);
	if (!rnk) return make_pair(0, copypoint(now));
	
	down(now);
	
	pair <int, int> re;
	if (rnk <= sz[ls[now]]) {
		int noww = copypoint(now);
		re = split_rnk(ls[noww], rnk);
		ls[noww] = re.second;
		up(noww);
		re.second = noww;
	}
	else {
		int noww = copypoint(now);
		re = split_rnk(rs[noww], rnk - sz[ls[now]] - 1);
		rs[noww] = re.first;
		up(noww);
		re.first = noww;
	}
	
	return re;
}

int merge(int x, int y) {
	if (x) down(x);
	if (y) down(y);
	if (!x) return y;
	if (!y) return x;
	
	if (yj[x] < yj[y]) {
		int xx = copypoint(x);
		rs[xx] = merge(rs[xx], y);
		up(xx);
		return xx;
	}
	else {
		int yy = copypoint(y);
		ls[yy] = merge(x, ls[yy]);
		up(yy);
		return yy;
	}
}

void insert(int bb, int pl, int num) {
	pair <int, int> x = split_rnk(rt[bb], pl);
	int y = newpoint(num);
	rt[bb] = merge(x.first, merge(y, x.second));
}

void delete_(int bb, int pl) {
	pair <int, int> x = split_rnk(rt[bb], pl - 1);
	pair <int, int> y = split_rnk(x.second, 1);
	rt[bb] = merge(x.first, y.second);
}

void turn_(int bb, int l, int r) {
	pair <int, int> x = split_rnk(rt[bb], l - 1);
	pair <int, int> y = split_rnk(x.second, r - l + 1);
	
	turn[y.first] ^= 1;
	
	rt[bb] = merge(merge(x.first, y.first), y.second);
}

ll get_sum(int bb, int l, int r) {
	pair <int, int> x = split_rnk(rt[bb], l - 1);
	pair <int, int> y = split_rnk(x.second, r - l + 1);
	return sum[y.first];
}

int main() {
	srand(19491001);
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &bb, &op);
		rt[i] = rt[bb];
		if (op == 1) {
			scanf("%d %d", &x, &y);
			x ^= lastans; y ^= lastans;
			insert(i, x, y); 
			continue;
		}
		if (op == 2) {
			scanf("%d", &x);
			x ^= lastans;
			delete_(i, x);
			continue;
		}
		if (op == 3) {
			scanf("%d %d", &x, &y);
			x ^= lastans;
			y ^= lastans;
			turn_(i, x, y);
			continue;
		}
		if (op == 4) {
			scanf("%d %d", &x, &y);
			x ^= lastans;
			y ^= lastans;
			lastans = get_sum(i, x, y);
			printf("%lld\n", lastans);
		}
	}
	
	return 0;
}