Author: lllyouo
Date: 20250923
tag: FHQ Treap
link: https://www.luogu.com.cn/problem/P3391

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
struct {
    int l, r;
    int val, key;
    int sz;
    int tag; // 延迟标记
} tr[N];
int tot, root, n, m;

int newNode(int v) {
    // 注意这里的 val 值是下标
    tr[++tot].val = v;
    // 注意这里的 key 值是权值，可传入具体值取代随机值
    tr[tot].key = rand();
    tr[tot].sz = 1;
    return tot;
}

void pushup(int p) {
    tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + 1;
}

void pushdown(int p) {
    if (tr[p].tag) {
        swap(tr[p].l, tr[p].r);
        tr[tr[p].l].tag ^= 1;
        tr[tr[p].r].tag ^= 1;
        tr[p].tag = 0;
    }
}

void split(int p, int k, int &x, int &y) {
    if (!p) {
        x = y = 0;
        return ;
    }

    pushdown(p);
    if (k > tr[tr[p].l].sz) {
        k -= tr[tr[p].l].sz + 1;
        x = p;
        split(tr[p].r, k, tr[p].r, y);
    } else {
        y = p;
        split(tr[p].l, k, x, tr[p].l);
    }
    pushup(p);
}

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr[x].key < tr[y].key) {
        pushdown(x); // pushdown 左子树
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    } else {
        pushdown(y); // pushdown 右子树
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

void reverse(int l, int r) {
    int x, y, z;
    split(root, r, x, z);
    split(x, l - 1, x, y);
    tr[y].tag ^= 1; //标记
    root = merge(merge(x, y), z);
}

void print(int p) {
    if (!p) return ;
    pushdown(p);
    print(tr[p].l);
    cout << tr[p].val << " ";
    print(tr[p].r);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        root = merge(root, newNode(i));
    }

    while (m--) {
        int l, r; cin >> l >> r;
        reverse(l, r);
    }

    print(root);

    return 0;
}