Splay 92pts求助

RT，TLE on #5#6 QAQ

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int n, m;
struct Splay {
    int fa[N], siz[N], ch[N][2], cnt[N], val[N], root, tot;
    inline void clear(int rt)
    {
        ch[rt][0] = ch[rt][1] = fa[rt] = cnt[rt] = val[rt] = siz[rt] = 0;
    }
    inline void pushup(int rt)
    {
        siz[rt] = siz[ch[rt][0]] + siz[ch[rt][1]] + cnt[rt];
    }
    inline bool lorr(int rt)
    {
        return rt == ch[fa[rt]][1];
    }
    inline void rorate(int rt)
    {
        int fath = fa[rt], gfath = fa[fath];
        bool pla = lorr(rt);
        ch[fath][pla] = ch[rt][pla ^ 1];
        fa[ch[fath][pla]] = fath;
        ch[rt][pla ^ 1] = fath;
        fa[fath] = rt;
        fa[rt] = gfath;
        if(gfath)
            ch[gfath][ch[gfath][1] == fath] = rt;
        pushup(fath);
        pushup(rt);
    }
    inline void splay(int rt)
    {
        for(int fath;fath = fa[rt];rorate(rt))
            if(fa[fath])
                rorate(lorr(rt) == lorr(fath) ? fath : rt);
        root = rt;
    }
    inline void insert(int k)
    {
        if(! root)
        {
            val[++ tot] = k;
            ch[tot][0] = ch[tot][1] = 0;
            siz[tot] = cnt[tot] ++;
            root = tot;
            return ;
        }
        int now = root, f = 0;
        while(1)
        {
            if(k == val[now])
            {
                cnt[now] ++;
                pushup(now);
                pushup(f);
                splay(now);
                return ;
            }
            f = now;
            now = ch[now][val[now] < k];
            if(! now)
            {
                tot ++;
                ch[tot][0] = ch[tot][1] = 0;
                fa[tot] = f;
                siz[tot] = cnt[tot] = 1;
                ch[f][val[f] < k] = tot;
                val[tot] = k;
                pushup(f);
                splay(tot);
                return ;
            }
        }
    }
    inline int find_by_order(int x) 
    {
        int now = root;
        while(1)
        {
            if(ch[now][0] && x <= siz[ch[now][0]])
                now = ch[now][0];
            else
            {
                int tmp = (ch[now][0] ? siz[ch[now][0]] : 0) + cnt[now];
                if(x <= tmp)
                {
                    splay(now);
                    return val[now];
                }
                x -= tmp;
                now = ch[now][1];
            }
        }
    }
    inline int rank(int x)
    {
        int now = root, ans = 0;
        while(1)
        {
            if(x < val[now])
                now = ch[now][0];
            else
            {
                ans += (ch[now][0] ? siz[ch[now][0]] : 0);
                if(x == val[now])
                {
                    splay(now);
                    return ans + 1;
                }
                ans += cnt[now];
                if(!ch[now][1])
                    return ans + 1;
                now = ch[now][1];
            }
        }
    }
    inline int pre()
    {
        int now = ch[root][0];
        while(ch[now][1])
            now = ch[now][1];
//      splay(now);
        return now;
    }
    inline int nxt()
    {
        int now = ch[root][1];
        while(ch[now][0])
            now = ch[now][0];
//      splay(now);
        return now;
    }
    inline void del(int x)
    {
        int now = rank(x);
//      splay(now);
        if(cnt[root] > 1)
        {
            cnt[root] --;
            pushup(root);
            return ;
        }
        if(! ch[root][0] && ! ch[root][1])
        {
            clear(root);
            root = 0;
            return ;
        }
        if(! ch[root][0])
        {
            int tmp = root;
            root = ch[root][1];
            fa[root] = 0;
            clear(tmp);
            return ;
        }
        if(! ch[root][1])
        {
            int tmp = root;
            root = ch[root][0];
            fa[root] = 0;
            clear(tmp);
            return ;
        }
        int ls = pre(), tmp = root;
        splay(ls);
        ch[root][1] = ch[tmp][1];
        fa[ch[tmp][1]] = root;
        clear(tmp);
        pushup(root);
    }
} t;

int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    while(n --)
    {
        int x;
        cin>>x;
        t.insert(x);
    }
    int las = 0, ans = 0;
    while(m --)
    {
        int opt, x;
        cin>>opt>>x;
        x ^= las;
        switch(opt)
        {
            case 1:
                t.insert(x);
                break;
            case 2:
                t.del(x);
                break;
            case 3:
                las = (t.rank(x));
                ans ^= las;
                break;
            case 4:
                las = (t.find_by_order(x));
                ans ^= las;
                break;
            case 5:
                t.insert(x);
                las = t.val[t.pre()];
                t.del(x);
                ans ^= las;
                break;
            case 6:
                t.insert(x);
                las = t.val[t.nxt()];
                t.del(x);
                ans ^= las;
                break;
        }
    }
    cout<<ans<<endl;
    return 0;
}