P3391文艺平衡树题解
洛谷P3391
我又来啦！
第一眼：哎！平衡树。
所以这次我们还是可以用无旋 Treap 来做。
和上次不一样，这道题增加了区间操作。 （而已）
对于普通平衡树（P3369）还没 AC 的朋友，可以先看这篇题解。
解法说明
一、不同点：
- 这道题涉及到子树操作，所以要 pushdown。
void pushdown(int x) { // 下传懒标记 if (node[x].tag) { node[node[x].l].tag ^= 1; // 一定要取反，否则后果自行脑补…… node[node[x].r].tag ^= 1; node[x].tag = 0; // 取消 } } - 这道题的区间翻转，要用到排名来进行分裂与合并。
void split(int u, int & l, int & r, int k) { // 分裂 if (!u) { // 分到底了 l = r = 0; return; } if (node[u].tag) { // 有懒标记才下传 pushdown(u); } int ln = node[node[u].l].sz; // 先取k个 if (ln < k) { l = u; split(node[u].r, node[l].r, r, k - ln - 1); } else { r = u; split(node[u].l, l, node[r].l, k); } pushup(u); // 上传 }
int merge(int l, int r) { // 合并 if (!l || !r) { return l + r; } if (node[l].pty <= node[r].pty) { // 按优先值合并 if (node[l].tag) pushdown(l); // 下传 node[l].r = merge(node[l].r, r); pushup(l); // 上传 return l; } else { if (node[r].tag) pushdown(r); node[r].l = merge(l, node[r].l); pushup(r); return r; } }
之后通过翻转就可以了。
### 预处理
来想想，如何取出 $[l,r]$？
利用差分的思想。
先从集合中取出 $[root,r]$。
再从 $[root,r]$ 中取出 $[root,l-1]$。
这样我们就得到了 $[l,r]$。
```cpp
void reverse(int tl, int tr) {
int p1, p2, p3, p4;
p1 = p2 = p3 = p4 = 0;
split(root, p1, p2, tr); // 取出[root,r]
split(p1, p3, p4, tl - 1); // 再取出[root,l-1]
node[p4].tag ^= 1; // 打标记
p1 = merge(p3, p4); // 合并（注意先后顺序，从后往前）
root = merge(p1, p2);
}二、区间翻转
实质上，区间翻转就是将子树进行交换。
WHY?
因为平衡树等于 BST 和堆。
Then?
它维护的是中序遍历序列。
So……
void pushdown(int x) {
if (node[x].tag) {
node[node[x].l].tag ^= 1;
node[node[x].r].tag ^= 1;
swap(node[x].l, node[x].r); // 交换子树
node[x].tag = 0;
}
}三、输出结果
输出因为 Treap 里存的是中序遍历，所以按中序遍历输出即可。
void print(int x) {
if (!x) { // 到底了
return;
}
if (node[x].tag) { // 注意要再检查一遍有没有遗漏的懒标记，有的话就下传
pushdown(x);
}
print(node[x].l); // 左
cout << node[x].val << " "; // 根
print(node[x].r); // 右
}四、完整代码,无注释：
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
struct tree {
int l, r, pty, tag, sz, val;
} node[N];
int dl, dr, n, m, root, num;
void pushup(int x) {
node[x].sz = node[node[x].l].sz + node[node[x].r].sz + 1;
}
void pushdown(int x) {
if (node[x].tag) {
node[node[x].l].tag ^= 1;
node[node[x].r].tag ^= 1;
swap(node[x].l, node[x].r);
node[x].tag = 0;
}
}
void split(int u, int & l, int & r, int k) {
if (!u) {
l = r = 0;
return;
}
if (node[u].tag) {
pushdown(u);
}
int ln = node[node[u].l].sz;
if (ln < k) {
l = u;
split(node[u].r, node[l].r, r, k - ln - 1);
} else {
r = u;
split(node[u].l, l, node[r].l, k);
}
pushup(u);
}
int merge(int l, int r) {
if (!l || !r) {
return l + r;
}
if (node[l].pty <= node[r].pty) {
if (node[l].tag) pushdown(l);
node[l].r = merge(node[l].r, r);
pushup(l);
return l;
} else {
if (node[r].tag) pushdown(r);
node[r].l = merge(l, node[r].l);
pushup(r);
return r;
}
}
void add(int val) {
num++;
node[num].val = val;
node[num].sz = 1;
node[num].pty = rand();
}
void reverse(int tl, int tr) {
int p1, p2, p3, p4;
p1 = p2 = p3 = p4 = 0;
split(root, p1, p2, tr);
split(p1, p3, p4, tl - 1);
node[p4].tag ^= 1;
p1 = merge(p3, p4);
root = merge(p1, p2);
}
void ins(int val) {
split(root, dl, dr, val - 1);
add(val);
root = merge(merge(dl, num), dr);
}
void print(int x) {
if (!x) {
return;
}
if (node[x].tag) {
pushdown(x);
}
print(node[x].l);
cout << node[x].val << " ";
print(node[x].r);
}
int main(void) {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
ins(i);
}
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
reverse(x, y);
}
print(root);
return 0;
}完结撒花~~~