由于我之前写有旋Treap写多了，所以我Splay的旋转也是按照有旋Treap的方式写的。

但是它 $10^5$ 都要跑 150ms，$10^6$ 就超过 1s了，正常吗？

struct Node{
    int ch[2];
    int fa;
    int val;
    int cnt;
    int sz;
};
Node T[MAXN];

// ...

inline int dir(int x){return x == T[T[x].fa].ch[1];}

inline void pushup(int x){
    T[x].sz = T[T[x].ch[0]].sz + T[T[x].ch[1]].sz + T[x].cnt;
}

inline void setch(int x,int ch,int y){
    T[x].ch[ch] = y;
    T[y].fa = x;
    pushup(y),pushup(x);
}

inline void lrot(int x){
    assert(x);
    int y = T[x].ch[1];
    T[y].fa = T[x].fa;
    if (T[x].fa)
        T[T[x].fa].ch[dir(x)] = y;
    setch(x,1,T[y].ch[0]);
    setch(y,0,x);
    pushup(x),pushup(y);
}

inline void rrot(int x){
    assert(x);
    int y = T[x].ch[0];
    T[y].fa = T[x].fa;
    if (T[x].fa)
        T[T[x].fa].ch[dir(x)] = y;
    setch(x,0,T[y].ch[1]);
    setch(y,1,x);
    pushup(x),pushup(y);
}

inline void rotate(int x){
    assert(x);
    if (dir(x))lrot(T[x].fa);
    else rrot(T[x].fa);
}

void splay(int x){
    assert(x);
    while (1){
        int fa = T[x].fa;
        if (!fa)
            break;
        if (!T[fa].fa){
            rotate(x);
            break;
        }
        if (dir(x) == dir(fa))rotate(fa);
        else rotate(x);
        rotate(x);
    }
    rt = x;
}