离线，多次查询序列或区间第 k 大数（含区间修改）
需要满足：修改对判定答案的贡献互相独立
基础：查询数列中第 k 小数。
对于当前的所有询问，可以去猜测所有询问的答案都是 mid，然后去依次验证每个询问的答案应该是小于等于 mid 的还是大于 mid 的，并将询问分为两个部分（不大于/大于），对于每个部分继续二分
如果当前数列中小于等于 mid 的数有 t 个，则将询问划分后实际是在右区间询问第 k-t 小数
c++
struct Query {
int id, k; // 这个询问的编号, 这个询问的k
};
int ans[N]; // ans[i] 表示编号为i的询问的答案
int check(int x); // 返回原数列中小于等于x的数的个数
void solve(int l, int r, vector<Query> q)
// 请补全这个函数
{
int m = (l + r) / 2;
vector<Query> q1, q2; // 将被划到左侧的询问和右侧的询问
if (l == r) {
// ...
for (unsigned i = 0; i < q.size(); i++) ans[q[i].id] = l;
return;
}
// ...
for (unsigned i = 0; i < q.size(); i++)
if (q[i].k <= check(m))
q1.push_back(q[i]);
else
q[i].k -= check(m), q2.push_back(q[i]);
solve(l, m, q1), solve(m + 1, r, q2);
return;
}如果查询区间第 k 小数呢
若询问区间内小于等于 m 的数有 t 个，询问的是区间内的 k 小数，则当 k≤t 时，答案应小于等于 m；否则，答案应大于 m
此处需记录一个区间小于等于指定数的数的数量，即单点加，求区间和，可用树状数组快速处理
在进一步递归之前，不仅将询问划分，将当前处理的数按值域范围划为两半
c++
struct Num {
int p, x;
}; // 位于数列中第 p 项的数的值为 x
struct Query {
int l, r, k, id;
}; // 一个编号为 id, 询问 [l,r] 中第 k 小数的询问
int ans[N];
void add(int p, int x); // 树状数组, 在 p 位置加上 x
int query(int p); // 树状数组, 求 [1,p] 的和
void clear(); // 树状数组, 清空
void solve(int l, int r, vector<Num> a, vector<Query> q)
// a中为给定数列中值在值域区间 [l,r] 中的数
{
int m = (l + r) / 2;
if (l == r) {
for (unsigned i = 0; i < q.size(); i++) ans[q[i].id] = l;
return;
}
vector<Num> a1, a2;
vector<Query> q1, q2;
for (unsigned i = 0; i < a.size(); i++)
if (a[i].x <= m)
a1.push_back(a[i]), add(a[i].p, 1);
else
a2.push_back(a[i]);
for (unsigned i = 0; i < q.size(); i++) {
int t = query(q[i].r) - query(q[i].l - 1);
if (q[i].k <= t)
q1.push_back(q[i]);
else
q[i].k -= t, q2.push_back(q[i]);
}
clear();
solve(l, m, a1, q1), solve(m + 1, r, a2, q2);
return;
}进阶：给定一个数列，要支持单点修改，区间查第 k 小。
修改操作可以直接理解为从原数列中删去一个数再添加一个数
可将所有操作存于一个数组，用标识区分类型，依次处理每个操作
c++
struct Opt {
int x, y, k, type, id;
// 对于询问, type = 1, x, y 表示区间左右边界, k 表示询问第 k 小
// 对于修改, type = 0, x 表示修改位置, y 表示修改后的值,
// k 表示当前操作是插入(1)还是擦除(-1), 更新树状数组时使用.
// id 记录每个操作原先的编号, 因二分过程中操作顺序会被打散
};
Opt q[N], q1[N], q2[N];
// q 为所有操作,
// 二分过程中, 分到左边的操作存到 q1 中, 分到右边的操作存到 q2 中.
int ans[N];
void add(int p, int x);
int query(int p); // 树状数组函数, 含义见题3
void solve(int l, int r, int L, int R)
// 当前的值域范围为 [l,r], 处理的操作的区间为 [L,R]
{
if (l > r || L > R) return;
int cnt1 = 0, cnt2 = 0, m = (l + r) / 2;
// cnt1, cnt2 分别为分到左边, 分到右边的操作数
if (l == r) {
for (int i = L; i <= R; i++)
if (q[i].type == 1) ans[q[i].id] = l;
return;
}
for (int i = L; i <= R; i++)
if (q[i].type == 1) { // 是询问: 进行分类
int t = query(q[i].y) - query(q[i].x - 1);
if (q[i].k <= t)
q1[++cnt1] = q[i];
else
q[i].k -= t, q2[++cnt2] = q[i];
} else
// 是修改: 更新树状数组 & 分类
if (q[i].y <= m)
add(q[i].x, q[i].k), q1[++cnt1] = q[i];
else
q2[++cnt2] = q[i];
for (int i = 1; i <= cnt1; i++)
if (q1[i].type == 0) add(q1[i].x, -q1[i].k); // 清空树状数组
for (int i = 1; i <= cnt1; i++) q[L + i - 1] = q1[i];
for (int i = 1; i <= cnt2; i++)
q[L + cnt1 + i - 1] = q2[i]; // 将临时数组中的元素合并回原数组
solve(l, m, L, L + cnt1 - 1), solve(m + 1, r, L + cnt1, R);
return;
}补充 main 函数，能过 P2617 Dynamic Rankings
c++
int n, m, cnt;
int main()
{
cin >> n >> m;
int l, r, k, x, y;
char op;
int cnt = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
q[cnt ++] = {i, a[i], 1, 0, 0};
}
for (int i = 1; i <= m; i++)
{
cin >> op;
if (op == 'Q')
{
cin >> l >> r >> k;
q[cnt ++] = {l, r, k, 1, i};
}
else
{
cin >> x >> y;
q[cnt ++] = {x, a[x], -1, 0, 0};
a[x] = y;
q[cnt ++] = {x, y, 1, 0, 0};
}
}
for (int i = 1; i <= m; i++) ans[i] = -1;
solve(0, 1e9, 0, cnt - 1);
for (int i = 1; i <= m; i++)
if (ans[i] > -1) cout << ans[i] << endl;
return 0;
}区间修改的题：P3332 [ZJOI2013] K大数查询
1 l r c：表示将 c 加入到编号在 [l,r] 内的集合中2 l r c：表示查询编号在 [l,r] 内的集合的并集中，第 c 大的数是多少。
因为是区间插入，所以把树状数组换成线段树，然后把第 c 大变成第 c 小，套用模板就行
c++
void solve(int l, int r, int L, int R)
// 当前的值域范围为 [l,r], 处理的操作的区间为 [L,R]
{
if (l > r || L > R) return;
int cnt1 = 0, cnt2 = 0, m = (l + r) / 2;
// cnt1, cnt2 分别为分到左边, 分到右边的操作数
if (l == r) {
for (int i = L; i <= R; i++)
if (q[i].type == 2) ans[q[i].id] = l;
return;
}
for (int i = L; i <= R; i++)
if (q[i].type == 2) { // 是询问: 进行分类
LL t = query(1, q[i].l, q[i].r); // 线段树的查询
if (q[i].c <= t)
q1[++cnt1] = q[i];
else
q[i].c -= t, q2[++cnt2] = q[i];
} else
// 是修改: 更新线段树 & 分类
if (q[i].c <= m)
update(1, q[i].l, q[i].r, 1), q1[++cnt1] = q[i];
else
q2[++cnt2] = q[i];
for (int i = 1; i <= cnt1; i++)
if (q1[i].type == 1) update(1, q1[i].l, q1[i].r, -1); // 清空线段树
for (int i = 1; i <= cnt1; i++) q[L + i - 1] = q1[i];
for (int i = 1; i <= cnt2; i++)
q[L + cnt1 + i - 1] = q2[i]; // 将临时数组中的元素合并回原数组
solve(l, m, L, L + cnt1 - 1), solve(m + 1, r, L + cnt1, R);
return;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d%lld", &q[i].type, &q[i].l, &q[i].r, &q[i].c);
q[i].id = i;
if (q[i].type == 1) num[++ cnt] = q[i].c;
ans[i] = -1;
}
sort(num + 1, num + 1 + cnt);
cnt = unique(num + 1, num + 1 + cnt) - num - 1;
for (int i = 1; i <= m; i++)
if (q[i].type == 1)
{
q[i].c = lower_bound(num + 1, num + 1 + cnt, q[i].c) - num; // 离散化
q[i].c = cnt - q[i].c + 1; //这里将第k大转化为第k小，在最后输出中再换回来
}
build(1, 1, n);
solve(1, cnt, 1, m);
for (int i = 1; i <= m; i++)
if (ans[i] != -1) printf("%lld\n", num[cnt - ans[i] + 1]);
return 0;
}