FHQ树求调（带注释）

输入一样的样例跑起来却有不一样的输出 （不过没有一个对的）

#include<bits/stdc++.h>
#define wk_is_handsome true
#define ll long long
using namespace std;
const int N = 1e5+5;

ll tre[N],ls[N],rs[N],fa[N];
ll siz[N],pos[N],val[N];
ll root,cnt;

ll last=0,sum = 0;
ll n,m;

void update(ll u){//更新这颗树的大小 
    siz[u] = siz[ls[u]]+siz[rs[u]]+1;
}

void split_by_val(ll u,ll k,ll &x,ll &y){
    //根据数值将这颗树分割成 <= k（后面叫小数） 和 > k（后面叫大树） 的二颗树 
    if(u == 0) {x = y = 0;return;}//如果不存在这个节点 

    if(val[u] <= k){
        //如果这个节点小于 k，那么这个节点的左子树都是小于 k的 
        //只用在这个节点的右子树中找大于 k的就好 
        x = u;//确定分割后小树的根节点 
        split_by_val(rs[u],k,rs[u],y);
    }
    else{
        //如果这个节点大于 k，那么这个节点的右子树都是大于 k的 
        //只用在这个节点的左子树中找小于 k的就好 
        y = u;
        split_by_val(ls[u],k,x,ls[u]);
    }
    update(u);
}

ll merge(ll x,ll y){
    if(x == 0 || y == 0) return x+y;//如果有一颗树是空的，返回那个不空的树

    if(pos[x]<pos[y]){
        //pos是优先级
        rs[x] = merge(rs[x],y);
        update(x);
        return x; 
    } 
    else{
        ls[y] = merge(x,ls[y]);
        update(y);
        return y;
    } 
    /*
    将split分开的两棵平衡树 treap 合并起来。
    因为第一个Treap(x)的权值都比较小，我们比较一下它的 pos (附加权值)，
    假如第一个(x)的 pos 小，我们就可以直接保留它的所有左子树，
    接着把第一个 Treap 变成它的右儿子。反之，
    我们可以保留第二棵的所有右子树，指针指向左儿子。
    你可以把这个过程形象的理解为在第一个Treap的左子树上插入第二个树，
    也可以理解为在第二个树的左子树上插入第一棵树。
    因为第一棵树都满足小于第二个树，所以就变成了比较pos来确定树的形态。
    */
}

//创建新节点 
ll new_point(ll x){
    siz[++cnt] = 1;
    val[cnt] = x;
    pos[cnt] = rand()%N+10;
    return cnt;
}

//查找排名为 k的节点 
ll Find(ll u,ll k){
    while(wk_is_handsome){
        if(k <= siz[ls[u]]) u = ls[u];
        else if( k == siz[ls[u]]+1) return u;
        else k-= (siz[ls[u]]+1),u = rs[u];
    }
}

int main(){
    srand(time(NULL));
    scanf("%lld %lld",&n,&m);

    for(ll i=1;i<=n;i++){
        ll v,x,y;
        scanf("%lld",&v);
        split_by_val(root,v,x,y); 
        root = merge((merge(x,new_point(v))),y);
    }

    for(ll i=1;i<=m;i++){
        ll v,opt;
        scanf("%lld %lld",&opt,&v);
        v ^= last;

        if(opt == 1){
            ll x,y;
            split_by_val(root,v,x,y); 
            root = merge((merge(x,new_point(v))),y);
        } 
        //插入一个权值为v的点，把树按照v的权值split成两个，再按照顺序合并回去。
        else if(opt == 2){
            ll a,b,c,d;
            split_by_val(root,v,a,b);
            split_by_val(a,v-1,c,d);
            d = merge(ls[d],rs[d]);
            root = merge(merge(c,d),b);
        }
        //删除权值为v的点，把树按照v分成两个a,b,再把a按照v-1分成c,d。
        //把 d的两个子儿子合并起来 (这时候那个点已经被删除了)，再merge(merge(c,d),b)
        //把分开的树合并回去。
        else if(opt == 3){
            ll x,y;
            split_by_val(root,v-1,x,y);
        //  printf("%d\n",siz[x]+1);
            root = merge(x,y);
            last = siz[x]+1;
        }
        //查找 v的排名
        //把root按 v-1 split_by_val 成 x,y。x 的 siz 大小+1
        else if(opt == 4){
            //查找排名为 v的数 
            //printf("%d\n",val[Find(root,v)]);
            last = val[Find(root,v)];
        }
        else if(opt == 5){
            ll x,y;
            split_by_val(root,v-1,x,y);
            //printf("%d\n",val[Find(x,siz[x])]);//1 ~ v-1 中最大的，就是第siz[x]个 
            root = merge(x,y);
            last = val[Find(x,siz[x])];
        }
        //查找 x的前驱：把root按 v-1 split_by_val成x,y，在x里面找最大值。
        else{
            ll x,y;
            split_by_val(root,v,x,y);
            //printf("%d\n",val[Find(y,1)]);
            root = merge(x,y);
            last = val[Find(y,1)];
        } 
        //查找 x的后继: 把root按 v split_by_val 成x,y，在y里面找最小值。 

        if(opt != 1 and opt != 2) sum ^= last;
        //printf("last = %lld,v = %lld\n",last,v);断点输出 
    }
    printf("%lld",sum);
    return 0;
}

附两次测试结果