死循环，lz崩溃了，两个关注

_ERO_ @ 2023-03-05 09:18:15

by Killer_joke @ 2023-03-05 10:12:21

错了三个地方 看注释的地方吧。

#include<cstdio>
#include<algorithm>
#define INF 0x7fffffff
using namespace std;

const int MAXN = 100005;

int n, m;
int a[MAXN];

struct Splay_tree{
        int cnt, siz, val, tag;
}tr[MAXN]; int son[MAXN][2], fa[MAXN], idx, root;

inline int Get_which(int x) {return x == son[fa[x]][1];}

inline void push_up(int x)
{
        tr[x].siz = tr[son[x][0]].siz + tr[son[x][1]].siz + tr[x].cnt;
}

inline void push_down(int x)
{
        if (x && tr[x].tag) {
                swap(son[x][0], son[x][1]);
                tr[son[x][0]].tag ^= 1;
                tr[son[x][1]].tag ^= 1;
                tr[x].tag = 0;
        }
}

inline int Build(int l, int r, int fath)
{
        if (l > r) return 0;
        int u = ++ idx, mid = (l + r) >> 1;
        tr[u].val = a[mid], tr[u].cnt = 1, fa[u] = fath;
        son[u][0] = Build(l, mid - 1, u);
        son[u][1] = Build(mid + 1, r, u);
        push_up(u);
        return u;
}

inline void Rotate(int x)
{
        int fath = fa[x], g_fa = fa[fath], w_son = Get_which(x);
        push_down(fath), push_down(x);
        son[fath][w_son] = son[x][w_son^1], fa[son[x][w_son^1]] = fath;
        son[x][w_son^1] = fath, fa[fath] = x;
        fa[x] = g_fa; if (g_fa) son[g_fa][son[g_fa][1] == fath] = x;
        push_up(fath); push_up(x);
}

inline void Splay(int x, int goal)
{
        for (int fath; (fath = fa[x]) != goal; Rotate(x))
                if (fa[fath]!=goal/*fath != goal*/)
                        Rotate((Get_which(fath) == Get_which(x)) ? fath : x);
        if (goal == 0) root = x;
}

inline int Find(int x)
{
        int p = root;
        while (true) {
                push_down(p);
                if (x <= tr[son[p][0]].siz) p = son[p][0];
                else {
                        int tmp = tr[son[p][0]].siz + tr[p].cnt;/*int tmp = tr[son[p][0]].siz + tr[p].siz;*/
                        if (x <= tmp) return p;
                        x -= tmp, p = son[p][1];
                }
        }
}

inline void Reverse(int be, int ed)
{
        int l = be - 1, r = ed + 1;
        l = Find(l), r = Find(r);
        Splay(l, 0), Splay(r, l);
        tr[son[r][0]].tag ^= 1; 
}

inline void dfs(int p)
{
        if (!p) return;
        push_down(p);
        dfs(son[p][0]);
        if (tr[p].val != (~INF) && tr[p].val != INF) printf ("%d ", tr[p].val);
        dfs(son[p][1]);
}

int main()
{
        scanf ("%d%d", &n, &m);
        a[1] = ~INF, a[n + 2] = INF;
        for (int i = 1; i <= n; ++ i) a[i + 1] = i;
        root = Build(1, n + 2, 0);/*root = Build(1, n, 0);*/

        int be, nd;
        for (int i = 1; i <= m; ++ i) {
                scanf ("%d%d", &be, &nd);
                Reverse(be + 1, nd + 1);
        }

        dfs(root);

        return 0;
}

by _ERO_ @ 2023-03-05 10:33:24

@Killer_joke 已关注，万分感谢大佬

（怎么我老是有这么多sb的错误…