Splay维护序列个人模板

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
#include <queue>
#define rep(i) for (int i=0; i<n; i++)
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
const int N = 100005, inf = 0x3f3f3f3f;

typedef struct Splay* node;
struct Splay {
    node pre, ch[2];
    ll value, lazy, max, sum;
    int size, rev;
    void init(int _value) {
        pre = ch[0] = ch[1] = NULL;
        max = value = sum = _value;
        lazy = rev = 0;
        size = 1;
    }
}tr[N];
int idx,top;

node S[N];
node root;

inline int getsize(node &x) {
    return x ? x->size : 0;
}

void push_down(node &x) {
    if (!x) return;
    if (x->lazy) {
        ll w = x->lazy;
        x->value += w;
        if (x->ch[0]) {
            x->ch[0]->lazy += w;
            x->ch[0]->max += w;
            x->ch[0]->sum += w * getsize(x->ch[0]);
        }
        if (x->ch[1]) {
            x->ch[1]->lazy += w;
            x->ch[1]->max += w;
            x->ch[1]->sum += w * getsize(x->ch[1]);
        }
        x->lazy = 0;
    }
    if (x->rev) {
        node t = x->ch[0];
        x->ch[0] = x->ch[1];
        x->ch[1] = t;
        x->rev = 0;
        if (x->ch[0]) x->ch[0]->rev ^= 1;
        if (x->ch[1]) x->ch[1]->rev ^= 1;
    }
}

void pushup(node &x) {
    if (!x) return;
    x->size = 1;
    x->max = x->value;
    x->sum = x->value;
    if (x->ch[0]) {
        x->sum += x->ch[0]->sum;
        x->max = max(x->max, x->ch[0]->max);
        x->size += x->ch[0]->size;
    }
    if (x->ch[1]) {
        x->sum += x->ch[1]->sum;
        x->max = max(x->max, x->ch[1]->max);
        x->size += x->ch[1]->size;
    }
}

void rotate(node &x, int d) {
    node y = x->pre;
    push_down(y);
    push_down(x);
    push_down(x->ch[d]);
    y->ch[!d] = x->ch[d];
    if (x->ch[d] != NULL) x->ch[d]->pre = y;
    x->pre = y->pre;
    if (y->pre != NULL)
        if (y->pre->ch[0] == y) y->pre->ch[0] = x; else y->pre->ch[1] = x;
    x->ch[d] = y;
    y->pre = x;
    pushup(y);
    if (y == root) root = x;
}

void splay(node &src, node &dst) {
    push_down(src);
    while (src != dst) {
        if (src->pre == dst) {
            if (dst->ch[0] == src) rotate(src,1); else rotate(src,0);
            break;
        }
        else {
            node y = src->pre, z = y->pre;
            if (z->ch[0] == y) {
                if (y->ch[0] == src) {
                    rotate(y,1);
                    rotate(src,1);
                }else {
                    rotate(src,0);
                    rotate(src,1);
                }
            }
            else {
                if (y->ch[1] == src) {
                    rotate(y,0);
                    rotate(src,0);
                }else {
                    rotate(src,1);
                    rotate(src,0);
                }
            }
            if (z == dst) break;
        }
        pushup(src);
    }
    pushup(src);
}

void select(int k, node &f) {
    int tmp;
    node t = root;
    while (true) {
        push_down(t);
        tmp = getsize(t->ch[0]);
        if (k == tmp + 1) break;
        if (k <= tmp) t = t->ch[0];
        else {
            k -= tmp + 1;
            t = t->ch[1];
        }
    }
    push_down(t);
    splay(t, f);
}


inline void SelectSegment(int l, int r) {
    select(l,root);
    select(r + 2,root->ch[1]);
}

node Newnode(int value){
    node t;
    if (top){
        t = S[top--];
    }
    else t = &tr[idx++];
    t->init(value);
    return t;
}

node build(int l,int r,node fa,int *a){
    int mid = l + r >> 1;
    node t = Newnode(a[mid]);
    t->pre = fa;
    if (l < mid) t->ch[0] = build(l,mid - 1,t,a);
    if (r > mid) t->ch[1] = build(mid + 1,r,t,a);
    pushup(t);
    return t;
}

void insert(int pos, int value) {  //在pos位置后面插入一个新值value
    SelectSegment(pos + 1, pos);
    node t;
    node x = root->ch[1];
    push_down(root);
    push_down(x);
    t = Newnode(value);
    t->ch[1] = x;
    x->pre = t;
    root->ch[1] = t;
    t->pre = root;
    splay(x, root);
}

void insert(int pos, int* a,int len) {  //在pos位置后面插入长度为len的数组
    SelectSegment(pos + 1, pos);
    node x = root->ch[1];
    push_down(root);
    push_down(x);
    root->ch[1]->ch[0] = build(1,len,root->ch[1],a);
    splay(x, root);
}

void add(int a,int b, int value) {  //区间[a,b]中的数都加上value
    SelectSegment(a, b);
    node x = root->ch[1]->ch[0];
    push_down(x);
    pushup(x);
    x->max += value;
    x->lazy += value;
    splay(x, root);
}

void reverse(int a, int b) {   //区间[a,b]中的数翻转
    SelectSegment(a, b);
    root->ch[1]->ch[0]->rev ^= 1;
    node x = root->ch[1]->ch[0];
    splay(x, root);
}

void revolve(int a, int b, int t) { //区间[a,b]中的数向后循环移t位
    node p1, p2;
    SelectSegment(a, b);
    select(b + 1 - t, root->ch[1]->ch[0]);
    p1 = root->ch[1]->ch[0];
    push_down(p1);
    p2 = p1->ch[1];
    p1->ch[1] = NULL;

    select(a + 1, root->ch[1]->ch[0]);
    p1 = root->ch[1]->ch[0];
    push_down(p1);
    p1->ch[0] = p2;
    p2->pre = p1;

    splay(p2, root);
}

ll getmax(int a, int b) {   //取[a,b]中最大的值
    SelectSegment(a, b);
    node x = root->ch[1];
    push_down(x);
    x = x->ch[0];
    push_down(x);
    pushup(x);
    return x->max;
}

ll getsum(int a, int b) {
    SelectSegment(a, b);
    node x = root->ch[1];
    push_down(x);
    x = x->ch[0];
    push_down(x);
    pushup(x);
    return x->sum;
}

void CutandMove(int a, int b, int c)//移动区间[l,r]到位置c后
{
    SelectSegment(a,b);
    node CutRoot = root->ch[1]->ch[0];
    CutRoot->pre = NULL;
    root->ch[1]->size -= CutRoot->size;
    root->ch[1]->ch[0] = NULL;

    SelectSegment(c + 1, c);

    CutRoot->pre = root->ch[1];
    root->ch[1]->ch[0] = CutRoot;
    root->ch[1]->size += CutRoot->size;
    //切树操作的话，就先选择要切的区间，然后断开根的右子结
    //点和其左子结点的联系，把要接上的节点旋转到根的右子结点出并清空其左子
    //结点，再把切下来的子树接上去即可。
}
void recycle(node x){
    S[++top] = x;
    if (x->ch[0]) recycle(x->ch[0]);
    if (x->ch[1]) recycle(x->ch[1]);
}
void cut(int a,int b)//删除区间[l.r]
{
    SelectSegment(a, b);
    node CutRoot = root->ch[1]->ch[0];
    CutRoot->pre = NULL;
    root->size -= CutRoot->size;
    root->ch[1]->size -= CutRoot->size;
    recycle(CutRoot);
    CutRoot = NULL;
}

vector<int> ans;
void get_ans(node x)
{
    if (!x) return;
    push_down(x);
    get_ans(x->ch[0]);
    if (x->value != -inf) ans.push_back(x->value);
    get_ans(x->ch[1]);
}

void InitSplay(int *a, int n) {
    idx = top = 0;
    root = Newnode(-inf);
    root->ch[1] = Newnode(-inf);
    root->ch[1]->pre = root;
    root->ch[1]->ch[0] = build(1,n,root->ch[1],a);
    pushup(root->ch[1]);
    pushup(root);
}


/*----------Splay Template Over----------*/
int a[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
//        cin >> a[i];
        a[i] = i;
    }
    InitSplay(a, n);
    while (m--) {
        int x,y;
        cin >> x >> y;
        reverse(x,y);
    }
    get_ans(root);
    for(auto k : ans) cout << k << ' ';
    return 0;
}