洛谷 - P3391 【模板】文艺平衡树（Splay）

https://www.luogu.org/problem/P3391

使用无旋Treap维护序列，注意的是按顺序插入的序列，所以Insert实际上简化成直接root和Merge合并，但是假如要在序列中插入某个数，则要SplitRank到正确的位置。

注意SplitRank的写法以及Pushdown的东西。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define ls(p) ch[p][0]

#define rs(p) ch[p][1]

const int MAXN = 200000 + 5;

int val[MAXN], ch[MAXN][2], rnd[MAXN], siz[MAXN], tot, root;

bool rev[MAXN];

void Init() {

    root = 0, tot = 0;

}

inline void PushUp(int p) {

    siz[p] = siz[ls(p)] + siz[rs(p)] + 1;

}

inline void PushDown(int p) {

    if(rev[p]) {

        swap(ls(p), rs(p));

        if(ls(p))

            rev[ls(p)] ^= 1;

        if(rs(p))

            rev[rs(p)] ^= 1;

        rev[p] = 0;

    }

}

void SplitRank(int p, int rk, int &x, int &y) {

    if(!p) {

        x = y = 0;

        return;

    }

    PushDown(p);

    if(rk <= siz[ls(p)]) {

        y = p;

        SplitRank(ls(p), rk, x, ls(p));

        PushUp(y);

    } else {

        x = p;

        SplitRank(rs(p), rk - siz[ls(p)] - 1, rs(p), y);

        PushUp(x);

    }

}

int Merge(int x, int y) {

    if(!x || !y)

        return x | y;

    if(rnd[x] < rnd[y]) {

        PushDown(x);

        rs(x) = Merge(rs(x), y);

        PushUp(x);

        return x;

    } else {

        PushDown(y);

        ls(y) = Merge(x, ls(y));

        PushUp(y);

        return y;

    }

}

int NewNode(int v) {

    int p = ++tot;

    ch[p][0] = ch[p][1] = 0;

    val[p] = v, rnd[p] = rand();

    siz[p] = 1;

    return p;

}

void Insert(int &root, int v) {

    root = Merge(root, NewNode(v));

}

void Reverse(int &root, int l, int r) {

    int x = 0, y = 0, z = 0;

    SplitRank(root, l - 1, x, y);

    SplitRank(y, r + 1 - l, y, z);

    rev[y] ^= 1;

    root = Merge(Merge(x, y), z);

}

vector<int> ans;

void Show(int p) {

    PushDown(p);

    if(ls(p))

        Show(ls(p));

    ans.push_back(val[p]);

    if(rs(p))

        Show(rs(p));

}

int d[MAXN], f[MAXN], a[MAXN];

int u2topo[MAXN], cnttopo, topo2u[MAXN];

struct Query {

    int u, k, ans, id;

    bool operator<(const Query& q)const {

        return u2topo[u] < u2topo[q.u];

    }

} que[MAXN];

struct cmp {

    bool operator()(const Query& q1, const Query& q2)const {

        return q1.id < q2.id;

    }

};

int que2[MAXN];

int front, back;

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

#endif // Yinku

    int n, q;

    while(~scanf("%d%d", &n, &q)) {

        Init();

        for(int i = 1; i <= n; ++i) {

            Insert(root, i);

        }

        for(int i = 1; i <= q; ++i) {

            int l, r;

            scanf("%d%d", &l, &r);

            Reverse(root, l, r);

        }

        ans.clear();

        Show(root);

        for(int i = 0; i < ans.size(); ++i)

            printf("%d%c", ans[i], " \n"[i == ans.size() - 1]);

    }

    return 0;

}

巴特西

洛谷 - P3391 【模板】文艺平衡树（Splay） - 无旋Treap

最新文章

热门文章