平衡结合
灵乌路空
2020-09-08 19:10:50
# 平衡结合
## 引入
[Luogu P3369 【模板】普通平衡树](https://www.luogu.com.cn/problem/P3369)
>您需要写一种数据结构来维护一些数。
>有 $n$ 次操作，每种操作是下列 6 种之一：
>1. 插入 $x$ 数。
>2. 删除 $x$ 数(若有多个相同的数，因只删除一个)。
>3. 查询 $x$ 数的排名（排名定义为比当前数小的数的个数 +$1$）。
>4. 查询排名为 $x$ 的数。
>5. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
>6. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。
>
>$1\le n\le 10^5$。
本题显然可使用平衡树，权值线段树等方法维护，它们查询修改的复杂度是平衡的，均为 $O(\log n)$ 级别。
可以在修改，查询次数同级时获得较优的时间复杂度。
但在某些情况下，修改与查询次数可能是不平衡的，这时可通过其他手段来处理该问题：
考虑分块解法，修改 $O(1)$，查询 $O(\sqrt{n})$ ，在修改数大于查询数时，可以获得更优的时间复杂度。
这就是一种平衡结合。
根据修改与查询次数的关系，通过调整维护的手段，使总的复杂度达到更低级别。
## 分块解法
操作数量较少，**先对出现的数离散化**，设离散化后值域为 $[1,n]$。
查询数的排名与某排名对应的数，考虑对值域分块，设块大小为 $T$。
维护每个数出现的次数，及值域分块后每块内所有数出现的个数。
操作 1，2，插入删除操作，$O(1)$ 单点修改即可。
操作 3，查询排名操作，即查询该数左侧所有数的出现次数。
整块直接查询，散块暴力，复杂度上界 $O(\frac{n}{T} + T)$。
操作 4，查询某排名对应的数，大力枚举即可。
从小到大枚举整块，累计维护值域内所有数出现次数之和。
当累计值 + 最后一个枚举到的整块 $\ge x$ 时，说明答案就在该块中。
再顺序枚举答案所在整块中的数，累计出现次数直至 $\ge x$ 即得。
复杂度上界 $O(\frac{n}{T} + T)$。
操作 5，查询前驱。
先枚举 $x$ 所在散块内 $< x$ 的数，检查是否存在。
再枚举 $x$ 之前的整块，直至找到一个内部有数的整块。
答案就在该整块中，降序枚举找到最大的存在的数即可。
复杂度上界 $O(\frac{n}{T} + T)$。
操作 6，查询后继，同操作 5 大力枚举，找到第一个存在的 $>x$ 的数，复杂度相同。
设块大小为 $\sqrt{n}$，操作 3 ~ 6 的复杂度均为 $O(\sqrt n)$，总复杂度上界 $O(n\sqrt{n})$。
当修改次数 > 查询次数时复杂度较优。
代码
```cpp
//知识点：分块
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#define ll long long
const int kMaxn = 1e5 + 10;
const int kMaxSqrtn = 320;
const int kInf = 1e9 + 2077;
//=============================================================
struct Operation {
int opt, x;
} q[kMaxn];
int n, block_size, block_num, L[kMaxSqrtn], R[kMaxSqrtn], bel[kMaxn];
int cnt[kMaxn], cntblock[kMaxSqrtn];
int data_num, max_data, data[kMaxn], map[kMaxn];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Prepare() { //离线操作，并离散化。
n = read();
for (int i = 1; i <= n; ++ i) {
q[i] = (Operation) {read(), read()};
if (q[i].opt != 4) data[++ data_num] = q[i].x; //注意操作 4 的参数不需要离散化。
}
data[0] = - kInf;
std :: sort(data + 1, data + data_num + 1);
for (int i = 1; i <= data_num; ++ i) {
if (data[i] != data[i - 1]) max_data ++;
data[max_data] = data[i];
}
for (int i = 1; i <= n; ++ i) {
if (q[i].opt == 4) continue;
int origin = q[i].x;
q[i].x = std :: lower_bound(data + 1, data + max_data + 1, q[i].x) - data;
map[q[i].x] = origin;
}
}
void PrepareBlock() {
block_size = (int) sqrt(max_data);
block_num = max_data / block_size;
for (int i = 1; i <= block_num; ++ i) {
L[i] = (i - 1) * block_size + 1;
R[i] = i * block_size;
}
if (R[block_num] < max_data) {
block_num ++;
L[block_num] = R[block_num - 1] + 1;
R[block_num] = max_data;
}
for (int i = 1; i <= block_num; ++ i) {
for (int j = L[i]; j <= R[i]; ++ j) {
bel[j] = i;
}
}
}
void Insert(int val_) { //O(1) 插入
cnt[val_] ++;
cntblock[bel[val_]] ++;
}
void Delete(int val_) { //O(1) 删除
cnt[val_] --;
cntblock[bel[val_]] --;
}
int QueryRank(int val_) { //查询给定数值的排名
int belval = bel[val_], ret = 0;
for (int i = L[belval]; i < val_; ++ i) ret += cnt[i]; //注意 <val_
for (int i = 1; i < belval; ++ i) ret += cntblock[i];
return ret + 1;
}
int QueryVal(int rank_) { //查询给定排名对应的数
int size = 0, ret, belval;
for (belval = 1; belval <= block_num; ++ belval) {
if (size + cntblock[belval] >= rank_) break;
size += cntblock[belval];
}
for (ret = L[belval]; ret <= R[belval]; ++ ret) {
if (size + cnt[ret] >= rank_) break;
size += cnt[ret];
}
return ret;
}
int QueryAhead(int val_) { //查询前驱
int belval = bel[val_];
for (int i = val_ - 1; i >= L[belval]; -- i) {
if (cnt[i]) return i;
}
for (int i = belval - 1; i; -- i) {
if (! cntblock[i]) continue;
for (int j = R[i]; j >= L[i]; -- j) {
if (cnt[j]) return j;
}
}
}
int QueryBack(int val_) { //查询后继
int belval = bel[val_];
for (int i = val_ + 1; i <= R[belval]; ++ i) {
if (cnt[i]) return i;
}
for (int i = belval + 1; i <= block_num; ++ i) {
if (! cntblock[i]) continue;
for (int j = L[i]; j <= R[i]; ++ j) {
if (cnt[j]) return j;
}
}
}
void koishi() {
int satori;
}
//=============================================================
int main() {
Prepare();
PrepareBlock();
for (int i = 1; i <= n; ++ i) {
int opt = q[i].opt, x = q[i].x;
if(opt == 1) Insert(x);
if(opt == 2) Delete(x);
if(opt == 3) printf("%d\n", QueryRank(x));
if(opt == 4) printf("%d\n", map[QueryVal(x)]);
if(opt == 5) printf("%d\n", map[QueryAhead(x)]);
if(opt == 6) printf("%d\n", map[QueryBack(x)]);
}
return 0;
}
```
## 一个例子
[可能是集训题的无出处题](http://114514.cn)
>给定一长度为 $n$ 的数列 $a$，参数 $w$，$q$ 次询问。
>每次询问给定参数 $l,r$，求忽略出现次数 $>w$ 的数后，区间 $[l,r]$ 内第 $k$ 小值。
>$1\le n,q,a_i,w\le10^5$。
忽略出现次数 $>w$ 的数，没法上主席树。
但显然可以莫队套平衡树，当枚举的区间内某个数首次出现时插入，出现次数 $=0$ 或 $> w$ 时删除。
$n,a_i$ 同级，修改和查询的复杂度相同，均为 $O(\log n)$。
块大小为 $T$ 时，总复杂度为 $O((\frac{n^2}{T}+qT)\log n + q\log n)$。
块大小为 $\frac{n}{\sqrt{q}}$ 时最优，总复杂度为 $O(n\sqrt{q}\log n+ q\log n)$，过不了。
发现块大小为 $T$ 时，莫队中一共有 $\frac{n^2}{T}+qT$ 次修改操作，但只有 $q$ 次查询操作。
考虑平衡结合，按照上述方法，使用分块维护区间第 $k$ 小值。
单次修改复杂度变为 $O(1)$，查询变为 $O(\sqrt{n})$，总复杂度 $O(\frac{n^2}{T}+qT + q\sqrt{n})$。
块大小取 $\frac{n}{\sqrt{q}}$ 时最优，总复杂度为 $O(n\sqrt{q} + q\sqrt{n})$。
## 两个例子
[P4867 Gty的二逼妹子序列](https://www.luogu.com.cn/problem/P4867)
>给定一长度为 $n$ 的数列 $a$，$m$ 次询问。
>每次询问给定参数 $l,r,a,b$，求区间 $[l,r]$ 内权值 $\in [a,b]$ 的数的种类数。
>$1\le a_i\le n\le 10^5$，$1\le m\le 10^6$。
---
发现莫队比较便于维护种类数，套一个莫队消去区间的限制。
考虑值域的限制，权值线段树进行维护。
单次 修改/查询 复杂度均为 $O(\log n)$。
设块大小为 $\dfrac{n}{\sqrt{m}}$，总复杂度为 $O(n\sqrt{m}\log n + m\log n)$。
只有单点修改，考虑对值域分块，维护块内不同的数的个数，可在莫队左右端点移动顺便维护。
查询时，在查询值域内的完整块直接统计答案，不完整块暴力查询。
设块大小为 $\dfrac{n}{\sqrt{m}}$，单次修改复杂度 $O(1)$，查询复杂度 $\sqrt{n}$，总复杂度为 $O(n\sqrt{m} +m\sqrt{n})$。
代码详见：[我的 Blog](https://www.cnblogs.com/luckyblock/p/13611018.html)。