标签：deque ver int root cf version 数据结构 杂题 op
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
```
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;
}
}
}
```,
ver,
int,
root,
cf,
version,
数据结构,
杂题,
op
From： https://www.cnblogs.com/JU5T4FUN/p/17366659.html