萌新刚学OI求助

#include <bits/stdc++.h>

using namespace std;

#define M 500005 

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x*10 + ch - '0'; ch = getchar(); }
    return x*f;
}

int n, m, t1, t2, root, cnt;
int f[M], ch[M][2], siz[M], val[M], mark[M];

int gett(int pos) { return ch[f[pos]][1] == pos; }

void upd(int pos) { siz[pos] = siz[ch[pos][0]] + siz[ch[pos][1]] + 1; }

void push_down(int pos)
{
    if (!mark[pos]) return;
    mark[ch[pos][0]] ^= 1, mark[ch[pos][1]] ^= 1;
    mark[pos] = 0; swap(ch[pos][0], ch[pos][1]);
}

inline void rotate(int pos)
{
    int old = f[pos], oldf = f[old], which = gett(pos);
    ch[old][which] = ch[pos][which^1], f[ch[pos][which^1]] = old;
    ch[oldf][ch[oldf][1] == old] = pos, f[pos] = oldf;
    ch[pos][which^1] = old, f[old] = pos;
    upd(old), upd(pos);
}

inline void splay(int pos, int goal = 0)
{
    while (f[pos] != goal)
    {
        int old = f[pos], oldf = f[old];
        if (oldf != goal)
        {
            if (gett(pos) == gett(old)) rotate(old);
            else rotate(pos);
        }
        rotate(pos);
    }
    if (!goal) root = pos;
}

inline void ins(int v)
{
    int cur = root, fa = 0;
    while (cur)
        fa = cur, cur = ch[cur][v > val[cur]];
    cur = ++cnt;
    if (fa) ch[fa][v > val[fa]] = cur;
    ch[cur][0] = ch[cur][1] = 0;
    val[cur] = v, f[cur] = fa;
    siz[cur] = 1;
    splay(cur, 0);
}

int kth(int k)
{
    int cur = root;
    while (true)
    {
        if (ch[cur][0] && k <= siz[ch[cur][0]])
            cur = ch[cur][0];
        else if (k > siz[ch[cur][0]] + 1)
            k -= siz[ch[cur][0]] + 1,
            cur = ch[cur][1];
        else
            return cur;
    }
}

void rever(int l, int r)
{
    l = kth(l), r = kth(r+2);
    splay(l, 0), splay(r, l);
    mark[ch[ch[root][1]][0]] ^= 1;
}

void pr(int pos)
{
    push_down(pos);
    if (ch[pos][0]) pr(ch[pos][0]);
    if (val[pos] > 1 && val[pos] < n+2) cout << val[pos]-1 << " ";
    if (ch[pos][1]) pr(ch[pos][1]);
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n+2; i++)
        ins(i);

    for (int i = 1; i <= m; i++)
        t1 = read(), t2 = read(),
        rever(t1, t2);

    for (int i = 1; i <= cnt; i++)
        cout << mark[i] << " ";
    cout << endl;

    pr(root);

    return 0;
}

和题解对拍发现只过了样例

救救孩子吧