后3个点T了

提交记录

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
typedef long long ll;

#define $(i, a, n) for(int i = a; i <= n; ++i)

using namespace std;

inline ll read() {
    ll ans = 0;
    char ch = getchar(), last = ' ';
    while (ch < '0' || ch > '9') last = ch, ch = getchar();
    while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();
    if (last == '-') return -ans;
    return ans;
}

const int INF = 0x3f3f3f3f;

const int N = 5e5 + 5;
int root, pool;
struct node{
    int size, fa, son[2], col, data, cnt;
}t[N];
int n, m, l, r;
int which(int x) {
    return t[t[x].fa].son[1] == x;
}
void pushup(int x) {
    t[x].size = t[t[x].son[0]].size + t[t[x].son[1]].size + t[x].cnt;
}
void pushdown(int x) {
    if (t[x].col) {
        swap(t[x].son[1], t[x].son[0]);
        if (t[x].son[0]) t[t[x].son[0]].col ^= 1;
        if (t[x].son[1]) t[t[x].son[1]].col ^= 1;
        t[x].col = 0;
    }
}
void rotate(int x) {
    int y = t[x].fa, z = t[y].fa;
    int b = which(x), c = which(y);
    int a = t[x].son[!b];
    if (z) t[z].son[c] = x;
    else root = x;
    t[x].fa = z;
    if (a) t[a].fa = y;
    t[y].son[b] = a;
    t[y].fa = x;
    t[x].son[!b] = y;
    pushup(y);
    pushup(x);
}

void splay(int x, int i) {
    int y, z;
    while (t[x].fa != i) {
        y = t[x].fa, z = t[y].fa;
        if (z == i) {
            rotate(x);
            return;
        } else if (which(x) == which(y)) {
            rotate(y), rotate(x);
        } else rotate(x), rotate(x);
    }
}

void insert(int &x, int v) {
    if (!x) {
        x = ++pool;
        t[x].size = t[x].cnt = 1;
        t[x].data = v;
        t[x].col = 0;
        return;
    } 
    if (v == t[x].data) {
        t[x].cnt++, t[x].size++;
        return;
    }
    if (v < t[x].data) {
        insert(t[x].son[0], v);
        t[t[x].son[0]].fa = x;
    } else {
        insert(t[x].son[1], v);
        t[t[x].son[1]].fa = x;
    }
    pushup(x);
}

int kth(int x, int k) {
    pushdown(x);
    int l = t[x].son[0];
    if (t[l].size >= k) return kth(l, k);
    else if (k == t[l].size + 1) return x;
    else return kth(t[x].son[1], k - t[l].size - 1);
}
int kth(int k) {
    int now = root;
    while(true) {
        pushdown(now);
        if (t[t[now].son[0]].size >= k) {
            now = t[now].son[0];
        } else {
            k -= t[t[now].son[0]].size + 1;
            if (!k) return now;
            else now = t[now].son[1];
        }
    }
}
void resverse(int l, int r) {
    l = l - 1, r = r + 1;
    l = kth(l), r = kth(r);
    splay(l, 0);
    splay(r, l);
    int pos =  t[root].son[1];
    pos = t[pos].son[0];
    t[pos].col ^= 1;
}

void print(int x) {
    pushdown(x);
    if (t[x].son[0]) print(t[x].son[0]);
    if (t[x].data != -INF && t[x].data != INF) printf("%d ", t[x].data);
    if (t[x].son[1]) print(t[x].son[1]);
}
int a[N];
int main() {
    //freopen("testdata.in", "r", stdin);
    //freopen("ans.out", "w", stdout);
    n = read(), m = read();
    for (int i = 2; i <= n + 1; ++i) a[i] = i - 1;
    a[1] = -INF;
    a[n + 2] = INF;
    for (int i = 1; i <= n + 2; ++i) insert(root, a[i]);
    for (int i = 1; i <= m; ++i) {
        l = read(), r = read();
        resverse(l + 1, r + 1);
    } 
    print(root);
    return 0;
}