跳转至

平衡树模板

平衡树是一种数据结构,可以维护序列和集合。普通平衡树的空间复杂度为 \(O(n)\)。平衡树可以在 \(O(\log V)\) 的时间复杂度内实现各种操作:

  • 插入;
  • 单点删除(Treap);
  • 区间删除(Splay,FHQ);
  • 区间打 tag、区间翻转(Splay,FHQ);
  • 求排名、下标;
  • 求给定下标、排名位置的数字;

主流平衡树有 \(3\) 种:带旋 Treap、Splay、FHQ Treap。三者的实现方法不同,常数不同,额外的附加功能也不同。

FHQ Treap 可以可持久化,可以快速带交合并,而且码量小,但是常数稍大。

带旋 Treap 常数和码量都较小,但不能进行区间操作。

P6136 【模板】普通平衡树(数据加强版)

代码
#include<bits/stl_algobase.h>
#include<ctype.h>
#include<cstdio>
#include<random>
using namespace std;
const int N = 1.1e6 + 10;
const int INF = 0x7fffffff;

#define endl '\n'
namespace io {
    struct istream {
        char ch;
        inline istream &operator>>(int &x) {
            while(!isdigit(ch = getchar_unlocked()));
            x = ch - '0';
            while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - '0';
            return *this;
        }
    } cin;
    struct ostream {
        char buf[60], top;
        inline ostream() : top(0) {}
        inline ostream &operator<<(int x) {
            do buf[++top] = x % 10 + '0', x /= 10; while(x);
            while(top) putchar_unlocked(buf[top--]);
            return *this;
        }
        inline ostream &operator<<(char c) {
            putchar_unlocked(c);
            return *this;
        }
        inline ostream &operator<<(const char s[]) {
            for(int i = 0; s[i]; i++) putchar_unlocked(s[i]);
            return *this;
        }
    } cout;
}

using io::cin;
using io::cout;

namespace Treap {
    mt19937 rng((random_device){}());
    int val[N], pri[N], sz[N], chd[N][2], nn, rt;
    inline int addNode(int v) {
        val[++nn] = v;
        pri[nn] = rng();
        sz[nn] = 1; 
        return nn;
    }
    inline void push_up(int p) {
        sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
    }
    inline void rotate(int &x, int d) {
        int y = chd[x][d], z = chd[y][d ^ 1];
        chd[x][d] = z;
        chd[y][d ^ 1] = x;
        push_up(x);
        push_up(y);
        x = y;
    }
    void insert(int &p, int v) {
        if(!p) { p = addNode(v); return; }
        int d = v > val[p];
        insert(chd[p][d], v);
        if(pri[chd[p][d]] < pri[p]) rotate(p, d);
        else push_up(p);
    }
    void erase(int &p, int v) {
        if(val[p] == v) {
            if(!chd[p][0]) { p = chd[p][1]; return; }
            if(!chd[p][1]) { p = chd[p][0]; return; }
            if(pri[chd[p][0]] < pri[chd[p][1]]) { rotate(p, 0); erase(chd[p][1], v); }
            else { rotate(p, 1); erase(chd[p][0], v); }
        } else {
            erase(chd[p][v > val[p]], v);
        }
        push_up(p);
    }
    int queryRank(int &p, int v) {
        if(!p) return 0;
        if(val[p] < v) return sz[chd[p][0]] + 1 + queryRank(chd[p][1], v);
        else return queryRank(chd[p][0], v);
    }
    int queryKth(int &p, int k) {
        if(k == sz[chd[p][0]] + 1) return val[p];
        if(k <= sz[chd[p][0]]) return queryKth(chd[p][0], k);
        return queryKth(chd[p][1], k - sz[chd[p][0]] - 1);
    }
    int queryPre(int &p, int v) {
        if(!p) return -INF;
        if(val[p] < v) return max(val[p], queryPre(chd[p][1], v));
        return queryPre(chd[p][0], v);
    }
    int querySuc(int &p, int v) {
        if(!p) return INF;
        if(val[p] > v) return min(val[p], querySuc(chd[p][0], v));
        return querySuc(chd[p][1], v);
    }
    inline void insert(int v) { insert(rt, v); }
    inline void erase(int v) { erase(rt, v); }
    inline int queryRank(int v) { return queryRank(rt, v); }
    inline int queryKth(int k) { return queryKth(rt, k); }
    inline int queryPre(int v) { return queryPre(rt, v); }
    inline int querySuc(int v) { return querySuc(rt, v); }
}

using namespace Treap;

int n, m;
int lastans, ans;

inline void addAns(int res) {
    lastans = res;
    ans ^= res;
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        Treap::insert(x);
    }

    while(m--) {
        int op, x;
        cin >> op >> x;
        x ^= lastans;
        if(op == 1) Treap::insert(x);
        else if(op == 2) Treap::erase(x);
        else if(op == 3) addAns(Treap::queryRank(x) + 1);
        else if(op == 4) addAns(Treap::queryKth(x));
        else if(op == 5) addAns(Treap::queryPre(x));
        else if(op == 6) addAns(Treap::querySuc(x));
    }

    cout << ans << '\n';

    return 0;
}
#include<bits/stl_algobase.h>
#include<ctype.h>
#include<cstdio>
#include<random>
#define int long long
using namespace std;
const int N = 1.1E6 + 10;

#define endl '\n'
namespace io {
    struct istream {
        char ch;
        inline istream &operator>>(int &x) {
            while(!isdigit(ch = getchar_unlocked()));
            x = ch - '0';
            while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - '0';
            return *this;
        }
    } cin;
    struct ostream {
        char buf[60], top;
        inline ostream() : top(0) {}
        inline ostream &operator<<(int x) {
            do buf[++top] = x % 10 + '0', x /= 10; while(x);
            while(top) putchar_unlocked(buf[top--]);
            return *this;
        }
        inline ostream &operator<<(char c) {
            putchar_unlocked(c);
            return *this;
        }
        inline ostream &operator<<(const char s[]) {
            for(int i = 0; s[i]; i++) putchar_unlocked(s[i]);
            return *this;
        }
    } cout;
}

using io::cin;
using io::cout;

int n, m, nn;
int val[N], son[N][2], pri[N], sz[N], a[N];

mt19937 rng((random_device){}());

int addNode(int v) {
    val[++nn] = v;
    pri[nn] = rng();
    sz[nn] = 1;
    return nn;
}

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

void split(int cur, int v, int &x, int &y) {
    if(cur == 0) {
        x = y = 0;
        return;
    }
    if(val[cur] <= v) {
        x = cur;
        split(son[cur][1], v, son[cur][1], y);
    } else {
        y = cur;
        split(son[cur][0], v, x, son[cur][0]);
    }
    push_up(cur);
}

int merge(int x, int y) {
    if(x == 0 || y == 0) {
        return x | y;
    }
    if(pri[x] > pri[y]) {
        son[x][1] = merge(son[x][1], y);
        push_up(x);
        return x;
    } else {
        son[y][0] = merge(x, son[y][0]);
        push_up(y);
        return y;
    }
}

int root = 0;
int insert(int v) {
    int x, y, z;
    y = addNode(v);
    split(root, v, x, z);
    return root = merge(merge(x, y), z);
}

int del(int v) {
    int x, y, z, w;
    split(root, v - 1, x, z);
    split(z, v, w, y);
    return root = merge(x, merge(merge(son[w][0], son[w][1]), y));
}

int queryRank(int v) {
    int x, y;
    split(root, v - 1, x, y);
    int res = sz[x] + 1;
    root = merge(x, y);
    return res;
}

int queryKth(int u, int x) {
    int cur = u;
    while(cur) {
        if(sz[son[cur][0]] + 1 == x) {
            return val[cur];
        } else if(x <= sz[son[cur][0]]) {
            cur = son[cur][0];
        } else {
            x -= sz[son[cur][0]] + 1;
            cur = son[cur][1];
        }
    }
    return -1;
}

int queryPre(int v) {
    int x, y;
    split(root, v - 1, x, y);
    int res = queryKth(x, sz[x]);
    root = merge(x, y);
    return res;
}

int querySuc(int v) {
    int x, y;
    split(root, v, x, y);
    int res = queryKth(y, 1);
    root = merge(x, y);
    return res;
}

signed main() {

    cin >> n >> m;
    for(int i = 1, ai; i <= n; i++) {
        cin >> ai;
        insert(ai);
    }

    int last = 0, ans = 0;
    while(m--) {
        int op, x;
        cin >> op >> x;
        x ^= last;
        if(op == 1) insert(x);
        else if(op == 2) del(x);
        else if(op == 3) ans ^= (last = queryRank(x));
        else if(op == 4) ans ^= (last = queryKth(root, x));
        else if(op == 5) ans ^= (last = queryPre(x));
        else ans ^= (last = querySuc(x));
    }

    cout << ans << endl;

    return 0;
}

P2042 [NOI2005] 维护数列

代码
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N = 5E5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;

int n, m;
int a[N];

int root, nn;
int val[N], chd[N][2], sz[N], sum[N], pri[N];
int lans[N], rans[N], ans[N], Max[N];;
int tag_rev[N], tag_mdf[N];

int pool[N], top;

void push_up(int p) {
    int lc = chd[p][0], rc = chd[p][1];
    sz[p] = sz[lc] + sz[rc] + 1;
    sum[p] = sum[lc] + sum[rc] + val[p];
    Max[p] = max(max(Max[chd[p][0]], Max[chd[p][1]]), val[p]);
    lans[p] = max(lans[lc], sum[lc] + val[p] + lans[rc]);
    rans[p] = max(rans[rc], sum[rc] + val[p] + rans[lc]);
    lans[p] = max(lans[p], 0ll);
    rans[p] = max(rans[p], 0ll);
    ans[p] = max(max(ans[lc], ans[rc]), max(lans[p], rans[p]));
    ans[p] = max(ans[p], sum[p]);
    ans[p] = max(ans[p], rans[lc] + lans[rc] + val[p]);
    ans[p] = max(ans[p], 0ll);
}

void move_tag_rev(int p) {
    swap(chd[p][0], chd[p][1]);
    swap(lans[p], rans[p]);
    tag_rev[p] ^= 1;
}

void move_tag_mdf(int p, int tg) {
    sum[p] = sz[p] * tg;
    Max[p] = tg;
    val[p] = tg;
    tag_mdf[p] = tg;
    lans[p] = rans[p] = ans[p] = (sum[p] > 0) ? sum[p] : 0;
}

void push_down(int p) {
    if(tag_rev[p] != 0) {
        move_tag_rev(chd[p][0]);
        move_tag_rev(chd[p][1]);
        tag_rev[p] = 0;
    }
    if(tag_mdf[p] != INF) {
        move_tag_mdf(chd[p][0], tag_mdf[p]);
        move_tag_mdf(chd[p][1], tag_mdf[p]);
        tag_mdf[p] = INF;
    }
}

int merge(int x, int y) {
    if(x == 0 || y == 0) {
        return x | y;
    }
    if(pri[x] > pri[y]) {
        push_down(x);
        chd[x][1] = merge(chd[x][1], y);
        push_up(x);
        return x;
    } else {
        push_down(y);
        chd[y][0] = merge(x, chd[y][0]);
        push_up(y);
        return y;
    }
}

void split(int cur, int v, int& x, int& y) {
    if(cur == 0) {
        x = y = 0;
        return;
    }
    push_down(cur);
    if(sz[chd[cur][0]] + 1 <= v) {
        x = cur;
        split(chd[x][1], v - (sz[chd[cur][0]] + 1), chd[x][1], y);
    } else {
        y = cur;
        split(chd[y][0], v, x, chd[y][0]);
    }
    push_up(cur);
}

int addNode(int v) {
    int pos;
    if(top != 0) {
        pos = pool[top--];
    } else {
        pos = ++nn;
    }
    val[pos] = sum[pos] = v;
    chd[pos][0] = chd[pos][1] = 0;
    Max[pos] = v;
    sz[pos] = 1;
    pri[pos] = rand();
    tag_rev[pos] = 0;
    lans[pos] = rans[pos] = ans[pos] = max(v, 0ll);
    return pos;
}

int makeTree(int l, int r, int* v) {
    if(l == r) {
        return addNode(v[l]);
    }
    int mid = (l + r) >> 1;
    return merge(makeTree(l, mid, v), makeTree(mid + 1, r, v));
}

void delTree(int p) {
    if(p == 0) return;
    delTree(chd[p][0]);
    delTree(chd[p][1]);
    pool[++top] = p;
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(tag_mdf, 0x3f, sizeof(tag_mdf));
    memset(Max, -0x3f, sizeof(Max));

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    root = makeTree(1, n, a);

    while(m--) {
        string op;
        cin >> op;
        if(op == "INSERT") {
            int pos, tot;
            cin >> pos >> tot;
            int c[tot + 10];
            for(int i = 1; i <= tot; i++) {
                cin >> c[i];
            }
            int y = makeTree(1, tot, c);
            int x, z;
            split(root, pos, x, z);
            root = merge(merge(x, y), z);
        } else if(op == "DELETE") {
            int pos, tot;
            cin >> pos >> tot;
            int x, y, z, w;
            split(root, pos - 1, x, w);
            split(w, tot, y, z);
            delTree(y);
            root = merge(x, z);
        } else if(op == "MAKE-SAME") {
            int pos, tot, c;
            cin >> pos >> tot >> c;
            int x, y, z, w;
            split(root, pos - 1, x, w);
            split(w, tot, y, z);
            move_tag_mdf(y, c);
            root = merge(merge(x, y), z);
        } else if(op == "REVERSE") {
            int pos, tot;
            cin >> pos >> tot;
            int x, y, z, w;
            split(root, pos - 1, x, w);
            split(w, tot, y, z);
            move_tag_rev(y);
            root = merge(merge(x, y), z);
        } else if(op == "GET-SUM") {
            int pos, tot;
            cin >> pos >> tot;
            int x, y, z, w;
            split(root, pos - 1, x, w);
            split(w, tot, y, z);
            cout << sum[y] << endl;
            root = merge(merge(x, y), z);
        } else if(op == "MAX-SUM") {
            if(ans[root] == 0) {
                cout << Max[root] << endl;
            } else cout << ans[root] << endl;
        }
    }

    return 0;
}
#include<iostream>
#define int long long
using namespace std;
const int INF = (int)0x3f3f3f3f3f3f3f3f;
const int N = 5E5 + 10;

struct Node {
    int lans, rans, ans, sum, mx;
};

int n, q;

int nn, root;
int val[N], sz[N], chd[N][2], fa[N];
int tag_inv[N], tag_mdf[N];
Node tr[N];

inline void push_up(int p) {
    sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
    Node &cur = tr[p];
    const Node &l = tr[chd[p][0]], &r = tr[chd[p][1]];
    cur.sum = l.sum + r.sum + val[p];
    cur.lans = max(l.lans, l.sum + val[p] + r.lans);
    cur.rans = max(r.rans, r.sum + val[p] + l.rans);
    cur.ans = max(max(l.ans, r.ans), l.rans + val[p] + r.lans);
    cur.mx = max(max(l.mx, r.mx), val[p]);
}

int sta[N], top;

inline int addNode(int v) {
    int nw;
    if(top) nw = sta[top--];
    else nw = ++nn;
    sz[nw] = 1;
    chd[nw][0] = chd[nw][1] = 0;
    val[nw] = v;
    fa[nw] = tag_inv[nw] = 0;
    tag_mdf[nw] = -INF;
    tr[nw] = {max(v, 0ll), max(v, 0ll), max(v, 0ll), v, v};
    return nw;
}

inline void move_tag_inv(int p) {
    tag_inv[p] ^= 1;
    swap(chd[p][0], chd[p][1]);
    swap(tr[p].lans, tr[p].rans);
}

inline void move_tag_mdf(int p, int tg) {
    tag_mdf[p] = tg;
    val[p] = tg;
    tr[p] = {max(tg, 0ll) * sz[p], max(tg, 0ll) * sz[p], max(tg, 0ll) * sz[p], tg * sz[p], tg};
}

inline void push_down(int p) {
    if(tag_mdf[p] != -INF) {
        move_tag_mdf(chd[p][0], tag_mdf[p]);
        move_tag_mdf(chd[p][1], tag_mdf[p]);
        tag_mdf[p] = -INF;
    }
    if(tag_inv[p]) {
        move_tag_inv(chd[p][0]);
        move_tag_inv(chd[p][1]); 
        tag_inv[p] = 0;
    }
}

inline bool get(int x) {
    return chd[fa[x]][1] == x;
}

inline void rotate(int x) {
    int y = fa[x], z = fa[y], d = get(x), w = chd[x][d ^ 1];
    fa[w] = y;
    chd[y][d] = w;
    fa[x] = z;
    if(z) chd[z][get(y)] = x;
    fa[y] = x;
    chd[x][d ^ 1] = y;
    push_up(y);
    push_up(x); 
} 

inline void splay(int x, int lim = 0) {
    for( ; fa[x] != lim; rotate(x)) {
        if(fa[fa[x]] != lim) {
            if(get(x) == get(fa[x])) rotate(fa[x]);
            else rotate(x); 
        }
    }
    if(lim == 0) root = x;
}

inline void insert(int pos, int v) {
    int cur = root, old = 0, d = 0;
    while(cur != 0) {
        push_down(cur); 
        old = cur;
        if(pos <= sz[chd[cur][0]]) {
            cur = chd[cur][0];
            d = 0;
        } else {
            pos -= sz[chd[cur][0]] + 1;
            cur = chd[cur][1];
            d = 1;
        }
    }
    cur = addNode(v);
    fa[cur] = old;
    if(old) chd[old][d] = cur;
    splay(cur);
}

inline int queryKth(int k) {
    int cur = root;
    while(cur != 0) {
        push_down(cur); 
        if(k <= sz[chd[cur][0]]) {
            cur = chd[cur][0];
        } else if(k == sz[chd[cur][0]] + 1) {
            splay(cur);
            return cur;
        } else {
            k -= sz[chd[cur][0]] + 1;
            cur = chd[cur][1];
        }
    }
    throw -1;
    return -1;
}

void rm_pt(int &p) {
    if(p == 0) return;
    rm_pt(chd[p][0]);
    rm_pt(chd[p][1]);
    sta[++top] = p;
    p = 0;
}

inline void del(int l, int r) {
    int x = queryKth(l - 1);
    int y = queryKth(r + 1);
    splay(x);
    splay(y, x);
    rm_pt(chd[y][0]);
    push_up(y);
    splay(y);
} 

inline void make_same(int l, int r, int v) {
    int x = queryKth(l - 1);
    int y = queryKth(r + 1);
    splay(x);
    splay(y, x);
    move_tag_mdf(chd[y][0], v);
    push_up(y);
    push_up(x);
}

inline void make_inv(int l, int r) {
    int x = queryKth(l - 1);
    int y = queryKth(r + 1);
    splay(x);
    splay(y, x);
    move_tag_inv(chd[y][0]);
    push_up(y);
    push_up(x);
}

inline int query_sum(int l, int r) {
    int x = queryKth(l - 1);
    int y = queryKth(r + 1);
    splay(x);
    splay(y, x);
    int res = tr[chd[y][0]].sum;
    return res;
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    tr[0].mx = -INF;

    insert(0, -INF);

    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        insert(i, x);
    } 

    insert(n + 1, -INF);

    while(q--) {
        string op;
        cin >> op;
        if(op == "INSERT") {
            int l, r;
            cin >> l >> r;
            r = l + r - 1;
            for(int i = l; i <= r; i++) {
                int x;
                cin >> x;
                insert(i + 1, x);
            } 
        } else if(op == "DELETE") {
            int l, r;
            cin >> l >> r;
            r = l + r - 1;
            del(l + 1, r + 1);
        } else if(op == "MAKE-SAME") {
            int l, r, c;
            cin >> l >> r >> c;
            r = l + r - 1;
            make_same(l + 1, r + 1, c);
        } else if(op == "REVERSE") {
            int l, r;
            cin >> l >> r;
            r = l + r - 1;
            make_inv(l + 1, r + 1);
        } else if(op == "GET-SUM") {
            int l, r;
            cin >> l >> r;
            r = l + r - 1;
            cout << query_sum(l + 1, r + 1) << '\n'; 
        } else {
            if(tr[root].ans == 0) {
                cout << tr[root].mx << '\n';
            } else cout << tr[root].ans << '\n';
        }
    }

    return 0;
} 

P3391 【模板】文艺平衡树

代码
#include<iostream>
using namespace std;
const int N = 1E5 + 10;

int n, m, root, nn;
int val[N], chd[N][2], sz[N], tag[N], fa[N];

void push_up(int p){
    if(p != 0) sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
}

void push_down(int p){
    if(tag[p] == 0) return;
    swap(chd[p][0], chd[p][1]);
    if(chd[p][0]) tag[chd[p][0]] ^= 1;
    if(chd[p][1]) tag[chd[p][1]] ^= 1;
    tag[p] = 0;
}

int build_tree(int l, int r, int f){
    if(l > r) return 0;
    int mid = (l + r) >> 1, p;
    val[++nn] = mid;
    p = nn;
    fa[p] = f;
    chd[p][0] = build_tree(l, mid - 1, p);
    chd[p][1] = build_tree(mid + 1, r, p);
    push_up(p);
    return p;
}

bool get(int x){
    return x == chd[fa[x]][1];
}

void rotate(int x){
    int y = fa[x], z = fa[y], d = get(x), w = chd[x][d ^ 1];
    fa[w] = y;
    chd[y][d] = w;
    fa[x] = z;
    if(z) chd[z][get(y)] = x;
    fa[y] = x;
    chd[x][d ^ 1] = y;
    push_up(y);
    push_up(x);
}

void splay(int x, int goal = 0){
    while(fa[x] != goal){
        int y = fa[x], z = fa[y];
        if(z != goal){
            if(get(x) == get(y)){
                rotate(y);
            } else{
                rotate(x);
            }
        }
        rotate(x);
    }
    if(goal == 0) root = x;
}

int kth(int x){
    int cur = root;
    while(1){
        push_down(cur);
        if(x <= sz[chd[cur][0]]){
            cur = chd[cur][0];
        } else if(x == sz[chd[cur][0]] + 1){
            splay(cur);
            return cur;
        } else{
            x -= sz[chd[cur][0]] + 1;
            cur = chd[cur][1];
        }
    }
    return 0;
}

void turn(int l, int r){
    int x = kth(l);
    int y = kth(r + 2);
    splay(x);
    splay(y, x);
    tag[chd[y][0]] ^= 1;
}

void inOrder(int x){
    push_down(x);
    if(chd[x][0]) inOrder(chd[x][0]);
    if(1 <= val[x] && val[x] <= n) cout << val[x] << ' ';
    if(chd[x][1]) inOrder(chd[x][1]);
}

int main(){

    cin >> n >> m;
    root = build_tree(0, n + 1, 0);
    while(m--){
        int l, r;
        cin >> l >> r;
        turn(l, r);
    }
    inOrder(root);
    cout << endl;

    return 0;
}
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
const int N = 1E5 + 10;

int n, m;

int root, nn;
int val[N], chd[N][2], pri[N], tag[N], sz[N];

int addNode(int v) {
    val[++nn] = v;
    pri[nn] = rand();
    sz[nn] = 1;
    return nn;
}

void push_up(int p) {
    sz[p] = sz[chd[p][0]] + sz[chd[p][1]] + 1;
}

void move_tag(int p) {
    tag[p] ^= 1;
    swap(chd[p][0], chd[p][1]);
}

void push_down(int p) {
    if(!tag[p]) return;
    move_tag(chd[p][0]);
    move_tag(chd[p][1]);
    tag[p] = 0;
}

void split(int cur, int v, int &x, int &y) {
    if(cur == 0) {
        x = y = 0;
        return;
    }
    push_down(cur);
    if(sz[chd[cur][0]] + 1 <= v) {
        x = cur;
        split(chd[x][1], v - (sz[chd[cur][0]] + 1), chd[x][1], y);
    } else {
        y = cur;
        split(chd[y][0], v, x, chd[y][0]);
    }
    push_up(cur);
}

int merge(int x, int y) {
    if(x == 0 || y == 0) {
        return x | y;
    }
    if(pri[x] > pri[y]) {
        push_down(x);
        chd[x][1] = merge(chd[x][1], y);
        push_up(x);
        return x;
    } else {
        push_down(y);
        chd[y][0] = merge(x, chd[y][0]);
        push_up(y);
        return y;
    }
}

int dfs(int l, int r) {
    if(l == r) {
        return addNode(l);
    }
    int mid = (l + r) >> 1;
    return merge(dfs(l, mid), dfs(mid + 1, r));
}

void rever(int l, int r) {
    int x, y, z, w;
    split(root, r, w, z);
    split(w, l - 1, x, y);
    tag[y] ^= 1;
    swap(chd[y][0], chd[y][1]);
    root = merge(merge(x, y), z);
}

void print(int cur) {
    if(cur == 0) {
        return;
    }
    push_down(cur);
    print(chd[cur][0]);
    cout << val[cur] << ' ';
    print(chd[cur][1]);
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    srand(time(NULL));

    cin >> n >> m;
    root = dfs(1, n);

    for(int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        rever(l, r);
    }

    print(root);

    cout << endl;

    return 0;
}