cf 数据结构杂题

JU5T4FUN / 2023-05-03 / 原文

rand 一些题目做一下，持续更新

平衡树

gym101261A Persistent Deque

You need to process the following queries:

B v x — Add x to the beginning of the deque with version v.

E v x — Add x to the end of the deque with version v.

< v — Remove the first element of the deque with version v.

> v — Remove the last element of the deque with version v.

Assume version 0 is an empty deque. Every query creates a new version of the deque.

All queries are online, that means you should flush the output before reading the input for the following query. Use fflush(stdout) for C/C++.

\(1\le Q\le 3e5\)

题意

让你实现一个可持久化的双端队列

solution

直接上可持久化平衡树；或者按照手写deque的方法（维护队首队尾指针），将数组改成可持久化数组

code

struct persistent_fhqTreap {
	static const int maxn = 3e5 + 5, MAXN = maxn * 40;
	int* a;
	int root[maxn], tot;
	int val[MAXN];
	int ch[MAXN][2], sz[MAXN], fix[MAXN];
	persistent_fhqTreap() { memset(root, 0, sizeof(root)); tot = 0; }
	void clear() { memset(root, 0, sizeof(root)); tot = 0; }
	inline int newNode() { return ++tot; }
	inline int rd() { static mt19937 mt(time(nullptr)); return mt() % 998244353; }
	//inline int rd() { return rand(); }
	inline void cpy(int a, int b) {//把a复制到b
		val[b] = val[a];
		fix[b] = fix[a];	sz[b] = sz[a];
		ch[b][0] = ch[a][0];	ch[b][1] = ch[a][1];
	}
	inline int Node(int v) {
		int id = newNode();
		sz[id] = 1;	ch[id][0] = ch[id][1] = 0;
		val[id] = v;
		fix[id] = rd();
		return id;
	}
	inline int Clone(int x) {
		int id = newNode();	cpy(x, id);
		return id;
	}
	inline void push_up(int x) {
		sz[x] = 1;
		if (ch[x][0]) { sz[x] += sz[ch[x][0]]; }
		if (ch[x][1]) { sz[x] += sz[ch[x][1]]; }
	}
	void split(int cur, int k, int& x, int& y) {
		if (!cur) {
			x = y = 0; return;
		}
		if (sz[ch[cur][0]] + 1 <= k) {
			x = newNode();	cpy(cur, x);
			split(ch[cur][1], k - (sz[ch[x][0]] + 1), ch[x][1], y);
			push_up(x);
		}
		else {
			y = newNode();	cpy(cur, y);
			split(ch[cur][0], k, x, ch[y][0]);
			push_up(y);
		}
	}
	int merge(int x, int y) {
		if (!x || !y) return x + y;
		if (fix[x] < fix[y]) {
			ch[x][1] = merge(ch[x][1], y);
			push_up(x);
			return x;
		}
		else {
			ch[y][0] = merge(x, ch[y][0]);
			push_up(y);
			return y;
		}
	}
	int build(int l, int r) {
		if (l > r)	return 0;
		int mid = l + r >> 1;
		int x = Node(a[mid]);
		//id[x] = mid;	//下标x的结点对应数组哪个点
		ch[x][0] = build(l, mid - 1);
		ch[x][1] = build(mid + 1, r);
		push_up(x);
		fix[x] = min(fix[ch[x][0]], fix[ch[x][1]]) - 1;
		return x;
	}
	int draw(int& rt, int l, int r, int& x, int& y) {
		int p;	split(rt, r, x, y);	split(x, l - 1, x, p);
		return p;
	}
	void ins(int& rt, int i, int v) {
		int x, y;
		split(rt, i - 1, x, y);
		rt = merge(merge(x, Node(v)), y);
	}
	int del(int& rt, int i) {
		int x, p, y;
		p = draw(rt, i, i, x, y);	//回收p
		rt = merge(x, y);
		return val[p];
	}
};
persistent_fhqTreap T;
void AC() {
#undef endl	//题目要求在线，每次输出刷新缓冲区
	int q;	cin >> q;
	char op;	int ver, p, x;
	for (int i = 1; i <= q; ++i) {
		cin >> op >> ver;
		T.root[i] = T.root[ver];
		int siz = T.sz[T.root[ver]];
		if (op == 'B') {
			cin >> x;
			T.ins(T.root[i], 1, x);
		}
		else if (op == 'E') {
			cin >> x;
			T.ins(T.root[i], siz + 1, x);
		}
		else if (op == '<') {
			cout << T.del(T.root[i], 1) << endl;
		}
		else {
			cout << T.del(T.root[i], siz) << endl;
		}
	}
}