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;
- }
来源: http://www.bubuko.com/infodetail-3149866.html