Dynamic Rankings
注：这道题也有树套树和整体二分的做法，这里讲解的是主席树 + 树状数组思路优化。
尝试沿用上一题的思路，思考修改操作如何完成：
考虑到修改操作对每棵权值线段树的影响是：
设修改前的值为w，则[1,x](xi<=x<=n)的线段树都把值域为w的点−1
[1,x](xi<=x<=n)的线段树都把值域为vali的点+1
这样做的时间复杂度过高，我们可以考虑用树状数组的二进制思想进行优化：
T[i]这颗线段树代表[i−lowbit(x)+1,x]这段区间建成的线段树：
修改操作，最多修改log2n颗线段树即可。
查询操作，用不超过2∗log2n颗线段树就能拼（前缀和）出[li,ri]的线段树。
注意，在查询时的代码实现：
用X数组存储拼出[1,x−1]的所有点。
用Y数组存储拼出[1,y]的所有点。
然后用普通主席树的方法，让所有的跟着跳，对位相减即可。
时间复杂度O(nlog2n)O(nlog2n)， 空间复杂度O(2n+(n+m)log2n)
#include <bits/stdc++.h>
using namespace std;
const int maxn=250000;
const int M=250000*400;
int n,q,m,tot;
int a[maxn],t[maxn];
int T[maxn],lson[M],rson[M],c[M];
int S[maxn];
struct Query{
int kind;
int l,r,k;
}query[100100];
void init_hash(int k){
sort(t,t+k);
m=unique(t,t+k)-t;
}
int hash1(int x){
return lower_bound(t,t+m,x)-t;
}
int build(int l,int r) {
int root = tot++;
c[root] = 0;
if (l != r) {
int mid = (l + r) >> 1;
lson[root] = build(l, mid);
rson[root] = build(mid + 1, r);
}
return root;
}
int insert(int root,int pos,int val) {
int newroot = tot++, tmp = newroot;
int l = 0, r = m - 1;
c[newroot] = c[root] + val;
while (l < r) {
int mid = (l + r) >> 1;
if (pos <= mid) {
lson[newroot] = tot++;
rson[newroot] = rson[root];
newroot = lson[newroot];
root = lson[root];
r = mid;
} else {
rson[newroot] = tot++;
lson[newroot] = lson[root];
newroot = rson[newroot];
root = rson[root];
l = mid + 1;
}
c[newroot] = c[root] + val;
}
return tmp;
}
int lowbit(int x) {
return x & -x;
}
int use[maxn];
int sum(int x) {
int ret = 0;
while (x) {
ret += c[lson[use[x]]];
x -= lowbit(x);
}
return ret;
}
int Query(int left,int right,int k) {
int left_root = T[left - 1];
int right_root = T[right];
int l = 0, r = m - 1;
for (int i = left - 1; i; i -= lowbit(i)) use[i] = S[i];
for (int i = right; i; i -= lowbit(i)) use[i] = S[i];
while (l < r) {
int mid = (l + r) >> 1;
int tmp = sum(right) - sum(left - 1) + c[lson[right_root]] - c[lson[left_root]];
if (tmp >= k) {
r = mid;
for (int i = left - 1; i; i -= lowbit(i)) use[i] = lson[use[i]];
for (int i = right; i; i -= lowbit(i)) use[i] = lson[use[i]];
left_root = lson[left_root];
right_root = lson[right_root];
} else {
l = mid + 1;
k -= tmp;
for (int i = left - 1; i; i -= lowbit(i)) use[i] = rson[use[i]];
for (int i = right; i; i -= lowbit(i)) use[i] = rson[use[i]];
left_root = rson[left_root];
right_root = rson[right_root];
}
}
return l;
}
void Modify(int x,int p,int d) {
while (x <= n) {
S[x] = insert(S[x], p, d);
x += lowbit(x);
}
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
t[m++] = a[i];
}
char op[10];
for (int i = 0; i < q; i++) {
scanf("%s", op);
if (op[0] == 'Q') {
query[i].kind = 0;
scanf("%d%d%d", &query[i].l, &query[i].r, &query[i].k);
} else {
query[i].kind = 1;
scanf("%d%d", &query[i].l, &query[i].r);
t[m++] = query[i].r;
}
}
init_hash(m);
T[0] = build(0, m - 1);
for (int i = 1; i <= n; i++) {
T[i] = insert(T[i - 1], hash1(a[i]), 1);
}
for (int i = 1; i <= n; i++) {
S[i] = T[0];
}
for (int i = 0; i < q; i++) {
if (query[i].kind == 0) {
printf("%d
", t[Query(query[i].l, query[i].r, query[i].k)]);
} else {
Modify(query[i].l, hash1(a[query[i].l]), -1);
Modify(query[i].l, hash1(query[i].r), 1);
a[query[i].l] = query[i].r;
}
}
return 0;
}