题意：给你n个数，m次操作：
Q x y z表示查询区间[x,y]中第z小的数是多少；
C x y 表示将第x个位置上的数替换成y；
题解：和http://blog.csdn.net/haut_ykc/article/details/77678882 一样，只是多了修改操作；
要知道每次修改某一个位置上的数都会影响后边的所有线段树，假如暴力更新的话必然会超时。
我们可以考虑用树状数组，因此可以考虑把主席树分成两部分，一部分表示原序列、另一部分表示修改过的即可。
#include<set> #include<map> #include<stack> #include<queue> #include<vector> #include<string> #include<math.h> #include<stdio.h> #include<iostream> #include<string.h> #include<stdlib.h> #include<algorithm> #include<functional> using namespace std; typedef long long ll; #define inf 1000000000 #define mod 1000000007 #define maxn 2600005 #define PI 3.1415926 #define lowbit(x) (x&-x) #define eps 1e-9 int a[60005], b[60005], rt[60005], num, f[60005], used[60005]; int cnt, sum[maxn], ls[maxn], rs[maxn], n, q[10005][4]; void build(int &id, int l, int r) { id = ++cnt; sum[id]=0; if (l == r) return; int mid = (l + r) / 2; build(ls[id], l, mid); build(rs[id], mid + 1, r); } void update(int &id, int l, int r, int last, int val, int k) { id = ++cnt; ls[id] = ls[last]; rs[id] = rs[last]; sum[id] = sum[last] + k; if (l == r) return; int mid = (l + r) / 2; if (val <= mid) update(ls[id], l, mid, ls[last], val, k); else update(rs[id], mid + 1, r, rs[last], val, k); } int sm(int x) { int ans = 0; while (x) { ans += sum[ls[used[x]]]; x -= lowbit(x); } return ans; } int query(int st, int ed, int val) { int i, les, res; int l = 1, r = num; les = rt[st];res = rt[ed]; for (i = st;i > 0;i -= lowbit(i)) used[i] = f[i]; for (i = ed;i > 0;i -= lowbit(i)) used[i] = f[i]; while (l < r) { int mid = (l + r) / 2; int tmp = sm(ed) - sm(st) + sum[ls[res]] - sum[ls[les]]; if (val <= tmp) { r = mid; for (i = st;i > 0;i -= lowbit(i)) used[i] = ls[used[i]]; for (i = ed;i > 0;i -= lowbit(i)) used[i] = ls[used[i]]; les = ls[les];res = ls[res]; } else { l = mid + 1;val -= tmp; for (i = st;i > 0;i -= lowbit(i)) used[i] = rs[used[i]]; for (i = ed;i > 0;i -= lowbit(i)) used[i] = rs[used[i]]; les = rs[les];res = rs[res]; } } return l; } void add(int x, int v, int k) { while (x <= n) { int tmp = f[x]; update(f[x], 1, num, tmp, v, k); x += lowbit(x); } } int main(void) { char c; int T, m, i, j; scanf("%d", &T); while (T--) { cnt = 0; memset(sum, 0, sizeof(sum)); scanf("%d%d", &n, &m); for (i = 1;i <= n;i++) scanf("%d", &a[i]), b[i] = a[i]; num = n; for (i = 1;i <= m;i++) { scanf(" %c", &c); if (c == 'Q') { scanf("%d%d%d", &q[i][1], &q[i][2], &q[i][3]); q[i][0] = 1; } else { scanf("%d%d", &q[i][1], &q[i][2]); b[++num] = q[i][2];q[i][0] = 0; } } sort(b + 1, b + num + 1); num = unique(b + 1, b + num + 1) - b - 1; for (i = 1;i <= num;i++) a[i] = lower_bound(b + 1, b + num + 1, a[i]) - b; build(rt[0], 1, num); for (i = 1;i <= n;i++) update(rt[i], 1, num, rt[i - 1], a[i], 1); for (i = 1;i <= n;i++) f[i] = rt[0]; for (i = 1;i <= m;i++) { if (q[i][0] == 1) { int ans = query(q[i][1]-1, q[i][2], q[i][3]); printf("%d\n", b[ans]); } else { int tmp; add(q[i][1], a[q[i][1]], -1); tmp = lower_bound(b + 1, b + num + 1, q[i][2]) - b; add(q[i][1], tmp, 1); a[q[i][1]] = tmp; } } } return 0; } /* 1000 5 5 1 2 3 4 5 Q 2 3 1 Q 1 5 5 C 3 1 Q 2 3 1 Q 2 3 2 5 4 -1 -2 -3 -4 -5 Q 1 3 2 Q 1 3 1 C 2 1 Q 1 5 4 */
