带修主席树的模板，因为状态不好所以敲了很长时间，不过写完感觉能更好地理解主席树了。
核心其实就是树状数组套主席树，维护方法不再是以前的那种一步一修改，而是对于树状数组上的每一个点建立一棵权值线段树，然后一点一点地维护。这样就从朴素修改后缀所需要的每次(O(NlogN))的复杂度，变成了修改(log)棵树所需要的(O(Nlog^2N))。
几个注意事项：
-
本题卡常。请使用离散化后的权值进行建树。
-
本题卡常。不要用(cin)。
-
因为是权值线段树，所以要先删除再添加。
-
二分的时候也要带上全家桶（(lowbit)对应位）一起修改鸭~
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int INF = 1000000010;
int tot, rt[N];
int n, m, arr[N];
#define mid ((l + r) >> 1)
#define lowbit(x) (x & -x)
struct Segment_Tree {
struct Segment_Node {
int ls, rs, sz;
}t[N << 9];
Segment_Tree () {t[0].sz = 0;}
void modify (int &v, int l, int r, int w, int del) {
if (v == 0) v = ++tot;
t[v].sz += del;
if (l != r) {
if (w <= mid) {
modify (t[v].ls, l, mid + 0, w, del);
} else {
modify (t[v].rs, mid + 1, r, w, del);
}
}
}
}seg;
int cnt, sep[N << 1];
int _sep (int w) {
return lower_bound (sep + 1, sep + 1 + cnt, w) - sep;
}
void change (int pos, int val) {
for (int i = pos; i <= n; i += lowbit (i)) {
seg.modify (rt[i], 0, INF, _sep (arr[pos]), -1);
}
arr[pos] = sep[val];
for (int i = pos; i <= n; i += lowbit (i)) {
seg.modify (rt[i], 0, INF, _sep (arr[pos]), +1);
}
}
int query (int u, int v, int k) {
static int _u[30], _v[30];
// u 到 v 区间第 k 小
int l = 0, r = INF;
_u[0] = _v[0] = 0;
for (int i = u; i != 0; i -= lowbit (i)) _u[++_u[0]] = rt[i];
for (int i = v; i != 0; i -= lowbit (i)) _v[++_v[0]] = rt[i];
while (l < r) {
int lch = 0;
for (int i = 1; i <= _u[0]; ++i) lch -= seg.t[seg.t[_u[i]].ls].sz;
for (int i = 1; i <= _v[0]; ++i) lch += seg.t[seg.t[_v[i]].ls].sz;
if (k <= lch) {
for (int i = 1; i <= _u[0]; ++i) _u[i] = seg.t[_u[i]].ls;
for (int i = 1; i <= _v[0]; ++i) _v[i] = seg.t[_v[i]].ls;
r = mid;
} else {
for (int i = 1; i <= _u[0]; ++i) _u[i] = seg.t[_u[i]].rs;
for (int i = 1; i <= _v[0]; ++i) _v[i] = seg.t[_v[i]].rs;
l = mid + 1;
k -= lch;
}
}
return r;
}
struct Query {
int type, l, r, k, p, w;
}q[N];
int main () {
// cin >> n >> m;
scanf ("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf ("%d", &arr[i]);
sep[++cnt] = arr[i];
}
for (int i = 1; i <= m; ++i) {
static char opt[10];
scanf ("%s", opt);
if (opt[0] == 'Q') {
q[i].type = 0;
scanf ("%d %d %d", &q[i].l, &q[i].r, &q[i].k);
} else {
q[i].type = 1;
scanf ("%d %d", &q[i].p, &q[i].w);
sep[++cnt] = q[i].w;
}
}
sort (sep + 1, sep + 1 + cnt);
cnt = unique (sep + 1, sep + 1 + cnt) - sep - 1; INF = cnt;
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; j += lowbit (j)) {
seg.modify (rt[j], 0, INF, _sep (arr[i]), +1);
}
}
for (int i = 1; i <= m; ++i) {
if (q[i].type == 0) {
printf ("%d
", sep[query (q[i].l - 1, q[i].r, q[i].k)]);
} else {
change (q[i].p, _sep (q[i].w));
}
}
}