平衡结合
扯
发现没人写值域分块就水了篇题解，私信管理加上了。
经典的 Kth \(O(1)\sim O(\sqrt{n})\) 解法。
因为光写值域分块太水了，稍微扩充了一下内容，写的和习惯的题解格式不一样。
引入
您需要写一种数据结构来维护一些数。
有 \(n\) 次操作，每种操作是下列 6 种之一：
- 插入 \(x\) 数。
- 删除 \(x\) 数(若有多个相同的数，因只删除一个)。
- 查询 \(x\) 数的排名（排名定义为比当前数小的数的个数 +\(1\)）。
- 查询排名为 \(x\) 的数。
- 求 \(x\) 的前驱（前驱定义为小于 \(x\)，且最大的数）。
- 求 \(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})\)。
当修改次数 > 查询次数时复杂度较优。
代码
//知识点：分块
/*
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;
}
一个例子
给定一长度为 \(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})\)。
两个例子
给定一长度为 \(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。