求助 Treap

RT

成功从 80 分变成了 90 分

呜呜呜大家能帮我看看卡卡常吗，含注释的哦-v-。

下面是代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib> 
using namespace std;
const int INF = 0x7fffffff, N = 1100050;
int siz[N], son[N][2], cnt[N], pri[N], val[N], num, Root, ans, lst, opt, x, n, m;//一堆乱七八糟不知所云的变量 
inline int new_node(int x){val[++num] = x; pri[num] = rand(); cnt[num] = siz[num] = 1; return num;}//新建节点 
inline void pushup(int x){siz[x] = siz[son[x][0]] + siz[son[x][1]] + cnt[x];}//维护子树大小 
inline void Rotate(int &x, int id){
    int y = son[x][id ^ 1];
    son[x][id ^ 1] = son[y][id];
    son[y][id] = x;
    x = y;
    pushup(son[x][id]);
    pushup(x);
}//旋转 
inline void Insert(int &x, int key){
    if(!x){x = new_node(key); return;}
    if(val[x] == key){cnt[x]++; siz[x]++; return;}
    int id = key < val[x] ? 0 : 1;
    Insert(son[x][id], key);
    if(pri[x] < pri[son[x][id]]) Rotate(x, id ^ 1);
    pushup(x);
    return;
}//插入 
inline void Delete(int &x, int key){
    if(!x) return;
    if(key == val[x]){
        if(cnt[x] > 1){
            cnt[x]--;
            pushup(x);
            return;
        }
        if(son[x][0] || son[x][1]){
            if(!son[x][1] && pri[son[x][0]] > pri[son[x][1]]){
                Rotate(x, 1);
                Delete(son[x][1], key);
            }
            else{
                Rotate(x, 0);
                Delete(son[x][0], key);
            }
            pushup(x);
        }
        else x = 0;
        return;
    }
    if(key < val[x]) Delete(son[x][0], key);
    else Delete(son[x][1], key);
    pushup(x);
    return;
}//删除 
inline int Pre(int key){
    int x = Root, ans = -INF;
    while(x){
        if(val[x] < key) ans = val[x], x = son[x][1];
        else x = son[x][0];
    }
    return ans;
}//前驱 
inline int Suf(int key){
    int x = Root, ans = INF;
    while(x){
        if(val[x] > key) ans = val[x], x = son[x][0];
        else x = son[x][1];
    }
    return ans;
}//后继 
inline int Find(int x, int key){
    if(!x) return 1;
    if(key == val[x]) return siz[son[x][0]] + 1;
    else if(key < val[x]) return Find(son[x][0], key);
    else return siz[son[x][0]] + cnt[x] + Find(son[x][1], key);
}//已知值求排名 
inline int Rank(int x, int k){
    if(!x) return 0;
    if(k <= siz[son[x][0]]) return Rank(son[x][0], k);
    else if(k <= siz[son[x][0]] + cnt[x]) return val[x];
    else return Rank(son[x][1], k - siz[son[x][0]] - cnt[x]);
}//已知排名求值 
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &x);
        Insert(Root, x);
    }
    for(int i = 1; i <= m; ++i){
        scanf("%d%d", &opt, &x);
        x ^= lst;
        if(opt == 1) Insert(Root, x);
        if(opt == 2) Delete(Root, x);
        if(opt == 3) lst = Find(Root, x), ans ^= lst;
        if(opt == 4) lst = Rank(Root, x), ans ^= lst;
        if(opt == 5) lst = Pre(x), ans ^= lst;
        if(opt == 6) lst = Suf(x), ans ^= lst;
    }
    printf("%d", ans);
    return 0;
} 

呜呜呜