Splay过样例 WA 0pts 求助

调了一下午 + 一晚上，人麻了。

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

const int N = 1e5 + 10;
const int INF = 1e9 + 42;
int n, m, a[N];
int tot, rt, fa[N], tag[N], son[N][2], sz[N], val[N], rev[N];

int newnode(int v, int p){
    ++tot;
    val[tot] = v, sz[tot] = 1, fa[tot] = p;
    return tot;
}

bool side(int u, int p){
    return (son[p][1] == u);
}

void pushup(int u){
    sz[u] = sz[son[u][0]] + sz[son[u][1]] + 1;
}

void pushdown(int u){
    if(tag[u]){
        tag[son[u][0]] ^= 1, tag[son[u][1]] ^= 1;
        swap(son[u][0], son[u][1]);
        tag[u] = 0;
    }
}

void rotate(int u){
    int p = fa[u], g = fa[p];
    int d = side(u, p);
//  pushdown(g), pushdown(p), pushdown(u); 
    son[p][d] = son[u][!d], fa[son[u][!d]] = p;
    fa[u] = g;
    if(g)
        son[g][side(p, g)] = u;
    son[u][!d] = p, fa[p] = u;
    pushup(p), pushup(u);
}

void splay(int x, int y){
    while(fa[x] != y){
        int p = fa[x], g = fa[p];
        if(g != y && side(x, p) == side(p, g))
            rotate(p);
        rotate(x);
    }
    if(!y)
        rt = x;
}

void insert(int &u, int v, int p){
    if(!u){
        u = newnode(v, p);
        splay(u, 0);
        return ;
    }
    if(v < val[u])
        insert(son[u][0], v, u);
    if(v > val[u])
        insert(son[u][1], v, u);
    pushup(u);
}

int kth(int u, int k){
    if(sz[son[u][0]] + 1 == k)
        return u;
    if(k <= sz[son[u][0]])
        return kth(son[u][0], k);
    return kth(son[u][1], k - sz[son[u][0]] - 1);
}

void reverse(int l, int r){
    l = kth(rt, l), r = kth(rt, r + 2);
    splay(l, 0);
    splay(r, l);
    int u = son[son[rt][1]][0];//根的左儿子的右儿子的子树就是 [l, r] 
    tag[u] ^= 1;
}

void dfs(int u){
    pushdown(u);
    if(son[u][0])
        dfs(son[u][0]);
    if(val[u] > 1 && val[u] < n + 2)
        printf("%d ", val[u] - 1);
    if(son[u][1])
        dfs(son[u][1]);
}

int main(){
    scanf("%d%d", &n, &m);
    rt = 0;
//  insert(rt, -INF, 0);
    for(int i=1;i<=n+2;i++)
        insert(rt, i, 0);
//  insert(rt, INF, 0);
    while(m--){
        int l, r;
        scanf("%d%d", &l, &r);
        reverse(l, r);
    }
    dfs(rt);
    return 0;
}