蒟蒻求助 Splay TLE #18

不是常数的原因，本地运行了几十分钟都没出结果。

#include <bits/stdc++.h>
using namespace std;

namespace Read
{
    char ch;
    void read(unsigned &x)
    {
        x = 0u;
        do
            ch = getchar();
        while(isspace(ch));
        while(isdigit(ch))
        {
            x *= 10u;
            x += ch;
            x -= '0';
            ch = getchar();
        }
    }
    void write(const unsigned &x)
    {
        if(x > 9u)
            write(x / 10u);
        putchar(x % 10u + '0');
    }
}

unsigned n, Q, L, R, rt, N, u, v, w, up, vp, ans, rk, op, all, V, last, Ans;
bool is_new, flag;
array<unsigned, 1100001> pa, cnt, sz, a;
array<array<unsigned, 2>, 1100001> ch;

inline void pushup(const unsigned &u)
{
    sz[u] = sz[ch[u][0]] + sz[ch[u][1]] + cnt[u];
}
inline bool Get(const unsigned &u)
{
    return u == ch[pa[u]][1];
}
inline void Clear(const unsigned u)
{
    pa[u] = cnt[u] = sz[u] = ch[u][0] = ch[u][1] = 0u;
    a[u] = 0;
}
inline void Rotate(const unsigned u)
{
    v = pa[u];
    w = pa[v];
    up = Get(u);
    vp = Get(v);
    ch[v][up] = ch[u][up ^ 1u];
    pa[ch[u][up ^ 1u]] = v;
    ch[u][up ^ 1u] = v;
    pa[v] = u;
    ch[w][vp] = u;
    pa[u] = w;
    pushup(u);
    pushup(v);
}
inline void splay(const unsigned u)
{
    for(unsigned v; v = pa[u]; Rotate(u))
        if(pa[v])
            Rotate(Get(u) == Get(v) ? v : u);
    rt = u;
}
void Find(const unsigned u)
{
    if(a[u] == V)
    {
        is_new = false;
        splay(u);
        return;
    }
    unsigned to(V > a[u]);
    if(ch[u][to])
    {
        Find(ch[u][to]);
        return;
    }
    ch[u][to] = ++ N;
    a[N] = V;
    pa[N] = u;
    is_new = true;
    splay(N);
}
inline void Insert()
{
    if(! rt)
    {
        rt = ++ N;
        a[rt] = V;
        ++ cnt[rt];
        ++ sz[rt];
        return;
    }
    Find(rt);
    ++ cnt[rt];
    ++ sz[rt];
}
inline void query_pre();
void print(const unsigned &u);
inline void Del()
{
    if(sz[rt] == 1u)
    {
        rt = 0u;
        Clear(rt);
        return;
    }
    if(cnt[rt] > 1u)
    {
        -- cnt[rt];
        -- sz[rt];
        return;
    }
    u = rt;
    if(! ch[rt][0])
    {
        rt = ch[u][1];
        pa[rt] = 0u;
        Clear(u);
        return;
    }
    if(! ch[rt][1])
    {
        rt = ch[u][0];
        pa[rt] = 0u;
        Clear(u);
        return;
    }
    query_pre();
    pa[ch[u][1]] = rt;
    ch[rt][1] = ch[u][1];
    Clear(u);
    pushup(rt);
}
inline unsigned query_rank()
{
    Find(rt);
    ans = sz[ch[rt][0]];
    if(is_new)
        Del();
    return ans;
}
void query_val(const unsigned u)
{
    all = sz[ch[u][0]] + cnt[u];
    if(all < rk)
    {
        rk -= all;
        query_val(ch[u][1]);
        return;
    }
    if(sz[ch[u][0]] < rk)
    {
        splay(u);
        return;
    }
    query_val(ch[u][0]);
}
inline void query_pre()
{
    v = ch[rt][0];
    while(ch[v][1])
        v = ch[v][1];
    splay(v);
}
inline void query_sub()
{
    v = ch[rt][1];
    while(ch[v][0])
        v = ch[v][0];
    splay(v);
}

int main()
{
    using namespace Read;
    read(n);
    read(Q);
    for(unsigned i(0u); i != n; ++ i)
    {
        read(V);
        Insert();
    }
    do
    {
        read(op);
        switch(op)
        {
        case 1u:
            read(V);
            V ^= last;
            Insert();
            break;
        case 2u:
            read(V);
            V ^= last;
            Find(rt);
            Del();
            break;
        case 3u:
            read(V);
            V ^= last;
            last = query_rank() + 1u;
            Ans ^= last;
            break;
        case 4u:
            read(rk);
            rk ^= last;
            query_val(rt);
            last = a[rt];
            Ans ^= last;
            break;
        case 5u:
            read(V);
            V ^= last;
            Find(rt);
            query_pre();
            last = a[rt];
            Ans ^= last;
            flag = is_new;
            Find(rt);
            if(flag)
                Del();
            break;
        case 6u:
            read(V);
            V ^= last;
            Find(rt);
            query_sub();
            last = a[rt];
            Ans ^= last;
            flag = is_new;
            Find(rt);
            if(flag)
                Del();
            break;
        }
    } while(-- Q);
    write(Ans);
    return 0;
}