有旋(划重点)treap可持久化
惊了，寒假的时候我还以为这题本来就是拿
有旋treap
写的？
今天发现其实(题解)没人这么干过？
具体来说为什么treap可以可持久化
（以下说法属于信口开河，不保证完全不正确）
，由于treap认子不认父（即不需要记录父节点），
而且所有操作都是自上而下（或者任意方向的单向？），
这种性质决定了一些节点能够方便地同时被两个版本共用
也就是决定了这种树可以方便地可持久化
有人说splay不能可持久化是因为它需要旋转、它的形态不停地在发生改变
其实决定性原因是在于它的操作既有从上往下，又有从下往上的（splay操作）
作个比方，你现在有这样的一条路，从左往右走
（象征可持久化树上自上而下的操作）
版本①__
↘
共用部分———> 你可以很方便地从两条分路合并到中间的主路上
版本②__↗
但是如果你从右往左走
①__
↖
？<————— 你就不知道应该走哪条路了
②__↙
其实，并不是说双向的树就不能可持久化，只是代码复杂，时间效益太低
（另外容易爆空间）
而可持久化线段树、可持久化treap一般只需要多加几行代码就够了
其实寒假的时候根本没考虑这么多，看见题就莽着写
以下是我的可持久化有旋treap代码，用于可持久化的新增代码（相对于原版treap）用注释做了标记
提交记录
#include <cstdio>
#include <cstdlib>
#include <iostream>
const int INF = 0x7FFFFFFF, MAXN = 5e5+1, MPR = 100;//MPR是空间多开倍数，别问我为什么用这个奇怪的缩写
int val[MAXN*MPR], left[MAXN*MPR], right[MAXN*MPR], size[MAXN*MPR], cnt[MAXN*MPR], pri[MAXN*MPR];
int id = 1;
void refresh(int &i){//复制节点，并返回新的节点，注意此处加引用'&'的意义
if(!i) return;
val[id] = val[i], left[id] = left[i], right[id] = right[i], pri[id] = pri[i], size[id] = size[i], cnt[id] = cnt[i];
i = id++;
}
void pull(int i){
size[i] = size[left[i]] + size[right[i]] + cnt[i];
}
void r_rotate(int &i){
refresh(left[i]);//****//
int lnode = left[i];
left[i] = right[lnode];
right[lnode] = i;
size[lnode] = size[i];
pull(i);
i = lnode;
}
void l_rotate(int &i){
refresh(right[i]);//****//
int rnode = right[i];
right[i] = left[rnode];
left[rnode] = i;
size[rnode] = size[i];
pull(i);
i = rnode;
}
int push_root(int i){//以节点i为模板创建新的根节点
refresh(i);
return i;
}
void insert(int &i, int k){
if(!i){
i = id++;
val[i] = k;
size[i] = cnt[i] = 1;
pri[i] = rand();
return;
}
size[i]++;
if(k < val[i]){
refresh(left[i]);//****//
insert(left[i], k);
if(pri[left[i]] < pri[i]) r_rotate(i);
}else if(k > val[i]){
refresh(right[i]);//****//
insert(right[i], k);
if(pri[right[i]] < pri[i]) l_rotate(i);
}else cnt[i]++;
}
bool check(int i, int k){
if(!i) return false;
if(k < val[i]) return check(left[i], k);
if(k > val[i]) return check(right[i], k);
return true;
}
void remove(int &i, int k){
if(k < val[i]) refresh(left[i]), remove(left[i], k);//****//
else if(k > val[i]) refresh(right[i]), remove(right[i], k);
else{
if(cnt[i] > 1) cnt[i]--, size[i]--;
else if(left[i] && right[i]){
if(pri[left[i]] < pri[right[i]]) r_rotate(i);
else l_rotate(i);
remove(i, k);
}else i = left[i] | right[i];
return;
}
size[i]--;
}
int rank(int i, int k){
if(!i) return 0;
if(k <= val[i]) return rank(left[i], k);
return size[left[i]] + cnt[i] + rank(right[i], k);
}
int at(int i, int k){
if(size[left[i]] >= k) return at(left[i], k);
if(size[left[i]] + cnt[i] >= k) return val[i];
return at(right[i], k - size[left[i]] - cnt[i]);
}
int prev(int i, int k){
if(!i) return -INF;
if(k <= val[i]) return prev(left[i], k);
return std::max(val[i], prev(right[i], k));
}
int nxt(int i, int k){
if(!i) return INF;
if(k >= val[i]) return nxt(right[i], k);
return std::min(val[i], nxt(left[i], k));
}
int i, root[MAXN];
using namespace std;
int main(){
int n, v, opt, x;
scanf("%d", &n);
for(i = 1; i <= n; i++){
scanf("%d%d%d", &v, &opt, &x);
switch(opt){//看不懂switch语句请不要找我
case 1:{
root[i] = push_root(root[v]);
insert(root[i], x);
break;
}
case 2:{
if(check(root[v], x)){
root[i] = push_root(root[v]);
remove(root[i], x);
}else root[i] = root[v];
break;
}
case 3:{
root[i] = root[v];
printf("%d\n", rank(root[i], x) + 1);
break;
}
case 4:{
root[i] = root[v];
printf("%d\n", at(root[i], x));
break;
}
case 5:{
root[i] = root[v];
printf("%d\n", prev(root[i], x));
break;
}
case 6:{
root[i] = root[v];
printf("%d\n", nxt(root[i], x));
break;
}
}
}
return 0;
}(欢迎hack！)