FHQ treap 记录

· · 个人记录

参考资料：


// 2024-04-29 拼凑代码:P6136 【模板】普通平衡树（数据加强版）

#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 1100010;
int n,m,op,x,last, ans;

mt19937 rd(time(0));    //茅台随机数
struct node{
    int l,r;    //左右孩子
    int val,siz, dat;   //权值，子树大小，堆的权值
}t[N];  //插入元素为1e6 + 本身的1e5
int tot , root;
inline void pushup(int k) {
    t[k].siz = t[t[k].l].siz + t[t[k].r].siz + 1;
}
int newnode(int val) {
    t[++tot].val = val;
    t[tot].siz = 1;
    t[tot].dat = rd();
    return tot;
}
void split(int k, int key, int &x, int &y){ //分裂的时候保证x中所有数都小于y
    if(k==0){
        x=y=0;  return ;
    }
    if(t[k].val <= key) {
        x = k;
        split(t[k].r, key, t[k].r ,y);
    }
    else {
        y = k;
        split(t[k].l, key, x, t[k].l);
    }
    pushup(k);
}
int merge(int x, int y) {   //顺序不能反
    if(x==0 || y==0)    return x+y;
    if(t[x].dat > t[y].dat) {   //维护大根堆性质
        t[x].r = merge(t[x].r, y);
        pushup(x);
        return x;
    }
    else {
        t[y].l = merge(x, t[y].l);
        pushup(y);
        return y;
    }
}
void insert(int key){
    int x,y;
    split(root, key-1, x,y); // 把<=key-1都分给x，大于等于key的分给y
    int id = newnode(key);
    root = merge(merge(x, id), y);  
}
void remove(int key) {
    int x,y,z;
    split(root, key-1, x,y);
    split(y, key, y, z);
    if(y) y=merge(t[y].l, t[y].r);
    root = merge(merge(x,y),z);
}
int Rank(int key) {
    int x,y, ans;
    split(root, key-1, x,y);
    ans = t[x].siz + 1;
    root = merge(x,y);
    return ans;
}
int kth(int rnk) {
    int p = root;
    while(p) {
        if(t[t[p].l].siz+1 == rnk)  break;
        else if(t[t[p].l].siz + 1>rnk) p=t[p].l;
        else {
            rnk -= t[t[p].l].siz + 1;
            p = t[p].r;
        }
    }
    return t[p].val;
}
int get_pre(int key) {
    int x,y,p;
    split(root, key-1, x,y);
    p = x;
    while(t[p].r!=0) p = t[p].r;
    root = merge(x,y);
    return t[p].val;
}
int get_nxt(int key) {
    int x,y,p;
    split(root, key, x, y);
    p = y;
    while(t[p].l!=0) p = t[p].l;
    root = merge(x,y);
    return t[p].val;
}
int main() {
    ios::sync_with_stdio(0);    cin.tie(0);     cout.tie(0);
    cin>>n>>m;
    for(int i=1, x; i<=n; i++){
        cin>>x;
        insert(x);
    }
    while(m--){
        cin>>op>>x;
        //cerr<< op << " " <<(x^last)<<endl;
        if(op == 1) insert(x^last);
        else if(op == 2)    remove(x^last);
        else if(op == 3){last = Rank(x^last);   ans^=last; }    //查询整数x的排名
        else if(op == 4){last = kth(x^last);    ans^=last; }    //查询排名x的数
        else if(op == 5){last = get_pre(x^last);    ans^=last; }
        else if(op == 6){last = get_nxt(x^last);    ans^=last; }
    }
    cout<<ans;
    return 0;
}