平衡树合并
我们知道,FHQ 平衡树具有 merge
函数,可以在期望 \(O(\log n)\) 的时间内将两棵平衡树的中序遍历直接拼接起来,也就是常说的“无交合并”。
有时,平衡树的中序遍历具有确定的顺序(值域、下标),合并两棵平衡树的结果不一定是中序遍历的拼接,可能出现交叉的情况,即“带交合并”。
带交合并
我们提供一种高效的带交合并:
int merge(int x, int y) {
if(!x || !y) return x | y;
int p, q;
split(x, mn[y], p, q);
return merge0(p, merge(y, q));
}
时间复杂度分析
对于一棵平衡树 \(T\),记 \(x_i\) 表示排名第 \(i\) 小的元素的值。定义其势能函数 \(\Phi(T)\) 为
结论:
- 平衡树带交合并的均摊时间复杂度不超过 \(O\big(q\log V\log n+\sum \Phi(T_i)\log n\big)=O\big((n+q)\log n\log V\big)\);
split
操作不增加势能;
证明:
考虑两棵平衡树 \(T_1\) 和 \(T_2\),记它们合并之后的结果为 \(T_3\)。
对于 \(T_1\) 和 \(T_2\) 的重合部分(\(x\in T_1\text{ and } x\in T_2\)),容易发现每次 merge
都会使不同的数字数量减少。每遇到一个重复数字,都会花费 \(O(\log n)\) 的时间复杂度进行处理(split
和 merge0
各调用一次)。均摊时间复杂度 \(O(n\log n)\)。
现在我们去除了 \(T_1\) 和 \(T_2\) 的交集部分。考虑合并前后的势能变化:
图中的线段表示 \(T_1\) 或 \(T_2\) 独有的一段值域区间,不要求区间内部的元素连续。
由 \(\log x\) 的凸性:
即
因此
初始势能与势能增量的和为 \(O\big((n+q)\log V\big)\)。
由于,merge
会调用 \(k\) 次 split
和 merge0
,每次的时间复杂度都是 \(O(\log n)\)。因此每产生 \(O(k\log n)\) 的时间复杂度都会至少降低 \(k\) 的势能。总时间复杂度为 \(O\big((n+q)\log n\log V\big)\)。
split
操作显然不增加势能,因此这种合并方式可以适用于反复合并的情况。
P3224 [HNOI2012] 永无乡
使用并查集和 FHQ 维护即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
|
插入标记回收算法
P10284 [USACO24OPEN] Splitting Haybales P
题意
给定一个长为 \(n\) 的序列 \(a_{1\sim n}\),每个下标都对应一个分段函数:
有 \(m\) 次询问,每次询问给定 \([l,r]\) 和初始值 \(v\),你需要求出:依次遍历 \(i\in [l,r]\),执行 \(v\leftarrow f_i(v)\) 得到的最终结果。
\(n,m,a_i\le 2\times 10^5,\ v\le 10^9\)
先将所有询问离线,然后从左往右依次扫描下标 \(i\)。对于所有区间左端点 \(l=i\) 的询问 \((l,r,v)\),向 FHQ 中插入一个值为 \(v\) 的节点表示这个询问。
然后使用 split
,move_tag
和 megre
对整棵平衡树进行 \(f_i\) 的变换:\(T\leftarrow f_i(T)\)。
然后,对于所有区间右端点 \(r=i\) 的询问 \((l,r,v)\),取出 \(l\) 位置插入的节点,查询其现在的值作为答案。
由于需要反复 split
和 merge
,我们可以使用上面提到的均摊 \(O(n\log^2 n)\) 的带交合并。时间复杂度为 \(O(n\log^2 n)\)。
代码
#include<iostream>
#include<vector>
#include<random>
#include<ctime>
using namespace std;
const int N = 2e5 + 10;
int n, t;
int a[N], ans[N];
int b[N], pt[N];
vector<int> bg[N], ed[N];
namespace fhq {
mt19937 rng(clock());
int mn[2 * N], val[2 * N], tag[2 * N], chd[2 * N][2], pri[2 * N], fa[2 * N], rt, nn;
inline int addNode(int v) {
val[++nn] = v;
mn[nn] = v;
pri[nn] = rng();
return nn;
}
inline void push_up(int p) {
mn[p] = val[p];
if(chd[p][0]) { fa[chd[p][0]] = p; mn[p] = min(mn[p], mn[chd[p][0]]); }
if(chd[p][1]) { fa[chd[p][1]] = p; mn[p] = min(mn[p], mn[chd[p][1]]); }
}
inline void move_tag(int p, int tg) {
if(!p) return;
tag[p] += tg;
val[p] += tg;
mn[p] += tg;
}
inline void push_down(int p) {
if(!tag[p]) return;
move_tag(chd[p][0], tag[p]);
move_tag(chd[p][1], tag[p]);
tag[p] = 0;
}
void split(int p, int v, int &x, int &y) {
if(p == 0) {
x = y = 0;
return;
}
push_down(p);
if(val[p] <= v) {
x = p;
split(chd[x][1], v, chd[x][1], y);
} else {
y = p;
split(chd[y][0], v, x, chd[y][0]);
}
push_up(p);
}
int merge0(int x, int y) {
if(!x || !y) return x | y;
if(pri[x] > pri[y]) {
push_down(x);
chd[x][1] = merge0(chd[x][1], y);
push_up(x);
return x;
} else {
push_down(y);
chd[y][0] = merge0(x, chd[y][0]);
push_up(y);
return y;
}
}
int merge(int x, int y) {
if(!x || !y) return x | y;
int p, q;
split(x, mn[y], p, q);
return merge0(p, merge(y, q));
}
// push_down_to_rt
void pushrt(int p) {
if(p != rt) pushrt(fa[p]);
push_down(p);
}
}
using namespace fhq;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> t;
for(int i = 1; i <= t; i++) {
int l, r;
cin >> l >> r >> b[i];
bg[l].push_back(i);
ed[r].push_back(i);
}
for(int i = 1; i <= n; i++) {
for(int j : bg[i]) {
pt[j] = addNode(b[j]);
rt = merge(rt, pt[j]);
}
int x, y;
split(rt, 0, x, y);
move_tag(x, a[i]);
move_tag(y, -a[i]);
rt = merge(x, y);
for(int j : ed[i] ) {
pushrt(pt[j]);
ans[j] = val[pt[j]];
}
}
for(int i = 1; i <= t; i++) {
cout << ans[i] <<'\n';
}
return 0;
}
P8264 [Ynoi Easy Round 2020] TEST_100
题意
给定一个长为 \(n\) 的序列 \(a_{1\sim n}\),每个下标都对应一个分段函数:
有 \(m\) 次询问,每次询问给定 \([l,r]\) 和初始值 \(v\),你需要求出:依次遍历 \(i\in [l,r]\),执行 \(v\leftarrow f_i(v)\) 得到的最终结果。
询问强制在线。
\(n,m,a_i,v\le 10^5\)
由于存在 \(-x\) 的操作,我们需要额外给平衡树维护一个区间翻转、取相反数的 tag
。
考虑如何处理强制在线。考虑序列分块,块长为 \(b\)。我们为每个块维护一个 \(tsf[i]\) 数组,表示查询 \((bg[b],ed[b],i)\) 的答案。对于查询,我们将散块暴力模拟,整块使用 \(tsf\) 数组。
考虑平衡块长 \(b\)。查询的时间复杂度显然是 \(O(mb+\frac{nm}{b})\)。对于预处理,由于这里的平衡树结构比较特殊,完整连续地覆盖了整个 \([1,n]\) 的值域,因此不能使用上面的势能分析(势能一直为 \(0\),会存在过度放缩)。我们发现,每产生一个重叠的元素,就会花费 \(O(\log n)\) 的时间进行一次 split
和 merge
,并将不同数字数量减少 \(1\) 个。因此块内时间复杂度不超过 \(O(n\log n)\)。
这样,总复杂度就是 \(O(\frac{n^2\log n}{b}+mb)\),平衡得 \(b=n\sqrt{\frac{\log n}m}\),时间复杂度 \(O(n\sqrt{m\log n})\)。由于平衡树的常数比分块查询大很多,因此块长应该调大一点(\(2\) 倍即可)。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 |
|