cf 数据结构杂题()

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\)

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\)

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;
		}
	}
}
————————

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\)

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\)

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;
		}
	}
}