C++14又紫又红

C++17十分正常

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
struct Node{
    int prio, num, ls, rs, siz = 1;
    bool laz;
    Node(){}
    Node(int prio, int num, int ls, int rs, bool laz){
        this->prio = prio, this->num = num, this->ls = ls, this->rs = rs, this->laz = laz;
    }
    inline void print(){cerr << "Node{" << prio << ',' << num << ',' << ls << ',' << rs << ',' << laz << ',' << siz << '}' << endl;}
};
struct Treap{
    vector<Node>nodes;
    int mem = 0;
    int root = -1;
    inline int node(){
        this->nodes.push_back(Node());
        return mem++;
    }
    inline void check_laz(int cur){
        if(this->nodes[cur].laz){
            this->nodes[cur].laz = false;
            int ls = this->nodes[cur].ls, rs = this->nodes[cur].rs;
            swap(this->nodes[cur].ls, this->nodes[cur].rs);
            if(ls != -1)
                this->nodes[ls].laz ^= 1;
            if(rs != -1)
                this->nodes[rs].laz ^= 1;
        }
    }
    inline void upd_siz(int cur){
        this->nodes[cur].siz = 1;
        int ls = this->nodes[cur].ls, rs = this->nodes[cur].rs;
        if(ls != -1)
            this->nodes[cur].siz += this->nodes[ls].siz;
        if(rs != -1)
            this->nodes[cur].siz += this->nodes[rs].siz;
    }
    int build(int lt, int rt){
        if(lt == rt){
            int cur = this->node();
            this->nodes[cur] = Node(this->mem, lt, -1, -1, false);
            return cur;
        }
        int mid = (lt + rt) >> 1;
        int cur = this->node();
        this->nodes[cur] = Node(this->mem, mid, -1, -1, false);
        if(lt < mid)
            this->nodes[cur].ls = this->build(lt, mid - 1);
        this->nodes[cur].rs = this->build(mid + 1, rt);
        this->upd_siz(cur);
        return cur;
    }
    inline void build(int len){this->root = this->build(1, len);}
    pair<int, int>split(int cur, int lim){
        if(cur == -1)
            return make_pair(-1, -1);
        this->check_laz(cur);
        int lsz = 0;
        if(this->nodes[cur].ls != -1)
            lsz = this->nodes[this->nodes[cur].ls].siz;
        if(lsz < lim){
            auto rt = this->split(this->nodes[cur].rs, lim - lsz - 1);
            this->nodes[cur].rs = rt.first;
            this->upd_siz(cur);
            return make_pair(cur, rt.second);
        }else{
            auto lt = this->split(this->nodes[cur].ls, lim);
            this->nodes[cur].ls = lt.second;
            this->upd_siz(cur);
            return make_pair(lt.first, cur);
        }
    }
    int merge(int a, int b){
        if(a == -1) return b;
        if(b == -1) return a;
        this->check_laz(a);
        this->check_laz(b);
        if(this->nodes[a].prio < this->nodes[b].prio){
            this->nodes[a].rs = this->merge(this->nodes[a].rs, b);
            this->upd_siz(a);
            return a;
        }else{
            this->nodes[b].ls = this->merge(a, this->nodes[b].ls);
            this->upd_siz(b);
            return b;
        }
    }
    inline void reverse(int lt, int rt){
        auto m = this->split(this->root, rt);
        auto lm = this->split(m.first, lt - 1);
        this->nodes[lm.second].laz ^= 1;
        this->merge(this->merge(lm.first, lm.second), m.second);
    }
    void print(int cur){
        if(cur == -1)
            return;
        this->check_laz(cur);
        this->print(this->nodes[cur].ls);
        cout << this->nodes[cur].num << ' ';
        this->print(this->nodes[cur].rs);
    }
    inline void print(){this->print(this->root); cout << endl;}
}treap;
int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    int n, m, l, r;
    cin >> n >> m;
    treap.build(n);
    // treap.print();
    while(m--){
        cin >> l >> r;
        treap.reverse(l, r);
        // treap.print();
    }
    treap.print();
    return 0;
}