RT，写的是无旋 Treap。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
const int N = 1e6 + 1, inf = 2e9 + ~-1;
struct Node{
    int son[2];
    int sz;
    int val, priority;
}treap[N];
int tot = 0, root = 0;
inline void push_up(int p){
    treap[p].sz = treap[treap[p].son[0]].sz + treap[treap[p].son[1]].sz + 1;
    return;
}
inline void split(int p, int k, int &l, int &r){
    if(p == 0) return l = r = 0, void();
    if(treap[p].val <= k){
        l = p;
        split(treap[p].son[1], k, treap[p].son[1], r);
    }else{
        r = p;
        split(treap[p].son[0], k, l, treap[p].son[0]);
    }
    push_up(p);
    return;
}
inline int merge(int l, int r){
    if(l == 0) return r;
    if(r == 0) return l;
    if(treap[l].priority < treap[r].priority){
		treap[l].son[1] = merge(treap[l].son[1], r);
		push_up(l);
		return l;
	}else{
        treap[r].son[0] = merge(l, treap[l].son[0]);
		push_up(r);
		return r;
	}
    return -inf;
}
inline int add(int x){
    tot++;
    treap[tot].son[0] = treap[tot].son[1] = 0;
    treap[tot].sz = 1;
    treap[tot].val = x, treap[tot].priority = _____;
    return tot;
}
inline int kth_element(int p, int k){
    if(k <= treap[treap[p].son[0]].sz){
        return kth_element(treap[p].son[0], k);
    }else{
        if(k - 1 == treap[treap[p].son[0]].sz){
            return treap[p].val;
        }else{
            return kth_element(treap[p].son[1], k-treap[treap[p].son[0]].sz-1);
        }
    }
    return -inf;
}
signed main(){
    srand(time(0));
    int T = read();
    while(T--){
        int opt, x;
        opt = read(); x = read();
        if(opt == 1){
            int l, r; split(root, x, l, r);
            root = merge(merge(l, add(x)), r);
        }else if(opt == 2){
            int l, r, R;
            split(root, x, l, R), split(l, x-1, l, r);
            int newr = merge(treap[r].son[0], treap[r].son[1]);
			root = merge(merge(l, newr), R);
        }else if(opt == 3){
            int l, r; split(root, x-1, l, r);
            printf("%d\n", treap[l].sz + 1);
            root = merge(l, r);
        }else if(opt == 4){
            printf("%d\n", kth_element(root, x));
        }else if(opt == 5){
            int l, r; split(root, x-1, l, r);
            printf("%d\n", kth_element(l, treap[l].sz));
            root = merge(l, r);
        }else if(opt == 6){
            int l, r; split(root, x, l, r);
            printf("%d\n", kth_element(r, 1));
            root = merge(l, r);
        }
    }
    return 0;
}

代码中第 $57$ 行的 treap[tot].priority = _____ 为什么与答案正确性（与时空复杂度）有关系？

提交记录：

treap[tot].priority = 1：Record

treap[tot].priority = rand()：Record

treap[tot].priority = rand() * rand() 第一次：Record

treap[tot].priority = rand() * rand() 第二次：Record