第一次打Splay，样例能过，全T了，高手帮忙看看

• lt, rt分别记录左右子树
• fa记录父亲节点
• val记录值
• pos记录修改
• root记录根编号
• sze记录儿子数

#include <iostream>
#include <cstdio>
#include <cstring>
#define RI register int
#define MaxN 200005
#define Inf 0x3f3f3f3f

using namespace std;

int lt[MaxN], rt[MaxN], fa[MaxN], val[MaxN];
bool pos[MaxN];
int a[MaxN];
int sze[MaxN];
int root;
int tot = 0;

inline int getInt()
{
    int f(1), r(0);
    char ch;
    ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        r = (r << 1) + (r << 3) + ch ^ 48;
        ch = getchar();
    }
    return r * f;
}

inline void putInt(int x) {
    if (x < 0) {
        x = ~x + 1;
        putchar('-');
    }
    if (x > 9)
        putInt(x / 10);
    putchar((x % 10) ^ 48);
    return;
}

inline bool wrt(int x)
{
    return rt[fa[x]] == x;
}

inline void Down(int x)
{
    if (x && pos[x])
    {
        pos[lt[x]] ^= 1;
        pos[rt[x]] ^= 1;
        lt[x] ^= rt[x];
        rt[x] ^= lt[x];
        lt[x] ^= rt[x];
        pos[x] = 0;
    }
}

inline void Push(int x)
{
    sze[x] = sze[lt[x]] + sze[rt[x]] + 1;
}

inline void Rot(int x)
{
    int y = fa[x], z = fa[y];
    //Down(y);
    //Down(x);
    int b = (lt[y] == x) ? rt[x] : lt[x];
    fa[x] = z;
    fa[y] = x;
    if (b)
        fa[b] = y;
    if (z)
    {
        if (y == lt[z])
            lt[z] = x;
        else
            rt[z] = x;
    }
    if (x == lt[y])
    {
        rt[x] = y;
        lt[y] = b;
    }
    else
    {
        lt[x] = y;
        rt[y] = b;
    }
    Push(y);
    Push(x);
    return;
}

inline void Splay(int x, int tar)
{
    while (fa[x] != tar)
    {
        if (fa[fa[x]] != tar)
            wrt(x) == wrt(fa[x]) ? Rot(fa[x]) : Rot(x);
        Rot(x);
    }
    if (!tar)
        root = x;
}

inline int Build(int k, int l, int r)
{
    if (l > r)
        return 0;
    int mid = l + r >> 1;
    int x = ++tot;
    fa[x] = k;
    pos[x] = 0;
    val[x] = a[mid];
    lt[x] = Build(x, l, mid - 1);
    rt[x] = Build(x, mid + 1, r);
    Push(x);
    return x;
}

inline int Find(int k)
{
    int x = root;
    int y = k;
    while (x)
    {
        Down(x);
        if (y <= sze[lt[x]])
            x = lt[x];
        else
        {
            y -= sze[lt[x]] + 1;
            if (!y)
                return x;
            x = rt[x];
        }
    }
}

inline void Print(int x)
{
    Down(x);
    if (lt[x])
        Print(lt[x]);
    if (val[x] != Inf && val[x] != -Inf) {
        putInt(val[x]);
        putchar(' ');
    }
    if (rt[x])
        Print(rt[x]);
}

int main()
{
    int n, m;
    n = getInt();
    m = getInt();
    a[1] = -Inf;
    a[n + 2] = Inf;
    for (RI i = 1; i <= n; ++i)
        a[i + 1] = i;
    root = Build(0, 1, n + 2);
    while (m--)
    {
        int tx = Find(getInt());
        int ty = Find(getInt() + 2);
        Splay(tx, 0);
        Splay(ty, tx);
        pos[lt[rt[root]]] ^= 1;
    }
    Print(root);
    return 0;
}