The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], ..., a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.
Your task is to write a program for this computer, which
- Reads N numbers from the input (1 <= N <= 50,000)
- Processes M instructions of the input (1 <= M <= 10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change some a[i] to t.
Input
The first line of the input is a single number X (0 < X <= 4), the number of the test cases of the input. Then X blocks each represent a single test case.
The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format
Q i j k or
C i t
It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000.
There're NO breakline between two continuous test cases.
Output
For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],..., a[j])
There're NO breakline between two continuous test cases.
Sample Input
2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
3
6
参考了大佬的博客：https://www.cnblogs.com/Empress/p/4659824.html
题意就是求区间内的第 k 小的数，但是会改变区间里的数。
因为数很大，所以首先要把所有的 a[i] ，包括更新过程的 a[i]，然后拿去离散化。
对于求区间第 k 大，基本思想还是和静态区间求第 k 小一样，先求前缀和，然后相减。然后得到区间内的数量关系，就可以求区间内的第 k 小了。但是这里有更新操作，原本的求区间的 node[node[y].l].sum - node[node[x].l].sum 就不能直接用了。
这里我们维护两颗完全不同的树，对一开始的数列用普通的主席树来维护，对于更新操作，用一个树状数组来维护，树状数组的每个节点都是一颗树，因为是单点更新，每棵树都只要更新 log(n) 个节点，用主席树来更新。（一个只维护初始的样子，一个只维护更新的样子）
然后这样的话，我们只需要想办法求出在 R 树和 L 树在某个区间上的左边部分的差值，在加上 node[node[y].l].sum - node[node[x].l].sum，就可以确定第 k 小在这个区间的左边还是右边。然后就可以开始用主席树的套路了。
然后这里为了求 R 树和 L 树在某个区间内的差值，我们定义一个 use 表示树状数组的目前结点对应的树是哪一颗，use 的更新类似于主席树递归时候从x -> node[x].l 这样子的过程，都是为了把它往左整体往左更新。.......其实还是感觉很抽象的东西
/*
.
';;;;;.
'!;;;;;;!;`
'!;|&#@|;;;;!:
`;;!&####@|;;;;!:
.;;;!&@$$%|!;;;;;;!'.`:::::'.
'!;;;;;;;;!$@###&|;;|%!;!$|;;;;|&&;.
:!;;;;!$@&%|;;;;;;;;;|!::!!:::;!$%;!$%` '!%&#########@$!:.
;!;;!!;;;;;|$$&@##$;;;::'''''::;;;;|&|%@$|;;;;;;;;;;;;;;;;!$;
;|;;;;;;;;;;;;;;;;;;!%@#####&!:::;!;;;;;;;;;;!&####@%!;;;;$%`
`!!;;;;;;;;;;!|%%|!!;::;;|@##%|$|;;;;;;;;;;;;!|%$#####%;;;%&;
:@###&!:;;!!||%%%%%|!;;;;;||;;;;||!$&&@@%;;;;;;;|$$##$;;;%@|
;|::;;;;;;;;;;;;|&&$|;;!$@&$!;;;;!;;;;;;;;;;;;;;;;!%|;;;%@%.
`!!;;;;;;;!!!!;;;;;$@@@&&&&&@$!;!%|;;;;!||!;;;;;!|%%%!;;%@|.
%&&$!;;;;;!;;;;;;;;;;;|$&&&&&&&&&@@%!%%;!||!;;;;;;;;;;;;;$##!
!%;;;;;;!%!:;;;;;;;;;;!$&&&&&&&&&&@##&%|||;;;!!||!;;;;;;;$&:
':|@###%;:;;;;;;;;;;;;!%$&&&&&&@@$!;;;;;;;!!!;;;;;%&!;;|&%.
!@|;;;;;;;;;;;;;;;;;;|%|$&&$%&&|;;;;;;;;;;;;!;;;;;!&@@&'
.:%#&!;;;;;;;;;;;;;;!%|$$%%&@%;;;;;;;;;;;;;;;;;;;!&@:
.%$;;;;;;;;;;;;;;;;;;|$$$$@&|;;;;;;;;;;;;;;;;;;;;%@%.
!&!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;|@#;
`%$!;;;;;;;;;;;$@|;;;;;;;;;;;;;;;;;;;;;;;;!%$@#@|.
.|@%!;;;;;;;;;!$&%||;;;;;;;;;;;;;;;;;!%$$$$$@#|.
;&$!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;%#####|.
|##$|!;;;;;;::'':;;;;;;;;;;;;;!%$$$@#@;
;@&|;;;;;;;::'''''':;;;;;;;|$&@###@|`
.%##@|;;;;:::''''''''''::;!%&##$'
`$##@$$@@&|!!;;;:'''''::::;;;;;|&#%.
;&@##&$%!;;;;;;::''''''''::;!|%$@#@&@@:
.%@&$$|;;;;;;;;;;:'''':''''::;;;%@#@@#%.
:@##@###@$$$$$|;;:'''':;;!!;;;;;;!$#@@#$;`
`%@$$|;;;;;;;;:'''''''::;;;;|%$$|!!&###&'
|##&%!;;;;;::''''''''''''::;;;;;;;!$@&:`!'
:;!@$|;;;;;;;::''''''''''':;;;;;;;;!%&@$: !@#$'
|##@@&%;;;;;::''''''''':;;;;;;;!%&@#@$%: '%%!%&;
|&%!;;;;;;;%$!:''''''':|%!;;;;;;;;|&@%||` '%$|!%&;
|@%!;;!!;;;||;:'''''':;%$!;;;;!%%%&#&%$&: .|%;:!&%`
!@&%;;;;;;;||;;;:''::;;%$!;;;;;;;|&@%;!$; `%&%!!$&:
'$$|;!!!!;;||;;;;;;;;;;%%;;;;;;;|@@|!$##; !$!;:!$&:
|#&|;;;;;;!||;;;;;;;;!%|;;;;!$##$;;;;|%' `%$|%%;|&$'
|&%!;;;;;;|%;;;;;;;;$$;;;;;;|&&|!|%&&; .:%&$!;;;:!$@!
`%#&%!!;;;;||;;;;;!$&|;;;!%%%@&!;;;!!;;;|%!;;%@$!%@!
!&!;;;;;;;;;||;;%&!;;;;;;;;;%@&!;;!&$;;;|&%;;;%@%`
'%|;;;;;;;;!!|$|%&%;;;;;;;;;;|&#&|!!||!!|%$@@|'
.!%%&%'`|$; :|$#%|@#&;%#%.
*/
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pii pair<int, int>
#define INOPEN freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout) typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 5e4 + ;
const int maxm = 1e5 + ;
const ll mod = 1e9 + ;
const ll INF = 1e18 + ;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-;
using namespace std; int n, m;
int cas, tol, T;
struct Node{
int l, r;
int sum;
} node[maxn * ];
struct Ask{
int l, r, k;
int id;
} ask[maxn / ];
int a[maxn];
int S[maxn]; //树状数组的根
int rt[maxn]; //主席树的根
int use[maxn]; //use表示树状数组的各个结点对应的树是哪一颗
vector<int> vv;
int L, R; int getid(int x) {
return lower_bound(vv.begin(), vv.end(), x) - vv.begin() + ;
} void init() {
tol = ;
mes(a, );
mes(S, );
mes(rt, );
vv.clear();
mes(use, );
mes(ask, );
mes(node, );
} int Sum(int pos) {
// 各颗树从 S[i] 走到了 used[i] 的位置，然后求左边部分的和
int ans = ;
for(int i=pos; i; i-=lowbit(i))
ans += node[node[use[i]].l].sum;
return ans;
} void update(int l, int r, int &x, int y, int pos, int val) {
x = ++tol;
node[tol] = node[y];
node[tol].sum += val;
if(l == r) return ;
int mid = (l + r) >> ;
if(pos <= mid)
update(l, mid, node[x].l, node[y].l, pos, val);
else
update(mid+, r, node[x].r, node[y].r, pos, val);
} void add(int pos, int k, int v) {
for(int i=pos; i<=n; i+=lowbit(i)) {
update(, vv.size(), S[i], S[i], k, v);
}
} int query(int l, int r, int x, int y, int k) {
if(l == r) return l;
int mid = (l + r) >> ;
//注意树状数组是 L 和 R
//因为是找 L 和 R 树链上的到达 use 位置的值
int tmp = Sum(R) - Sum(L) + node[node[y].l].sum - node[node[x].l].sum;
if(k <= tmp) {
//往现在到达的x，y位置的两棵树的左边查询
//把 L 和 R 这路径上的所有树状数组都往左子树更新
for(int i=L; i; i-=lowbit(i)) use[i] = node[use[i]].l;
for(int i=R; i; i-=lowbit(i)) use[i] = node[use[i]].l;
return query(l, mid, node[x].l, node[y].l, k);
} else {
//往现在到达的x，y位置的两棵树的右边查询
//把 L 和 R 这路径上的所有树状数组都往右子树更新
for(int i=L; i; i-=lowbit(i)) use[i] = node[use[i]].r;
for(int i=R; i; i-=lowbit(i)) use[i] = node[use[i]].r;
return query(mid+, r, node[x].r, node[y].r, k-tmp);
}
} int main() {
scanf("%d", &T);
while(T--) {
init();
scanf("%d%d", &n, &m);
for(int i=; i<=n; i++) {
scanf("%d", &a[i]);
vv.push_back(a[i]);
}
for(int i=; i<=m; i++) {
char ss[];
scanf("%s", ss);
if(ss[] == 'Q') {
ask[i].id = ;
scanf("%d%d%d", &ask[i].l, &ask[i].r, &ask[i].k);
} else {
ask[i].id = ;
scanf("%d%d", &ask[i].l, &ask[i].r);
vv.push_back(ask[i].r);
}
}
sort(vv.begin(), vv.end()); //离散化一下
vv.erase(unique(vv.begin(), vv.end()), vv.end());
for(int i=; i<=n; i++) {
int id = getid(a[i]); //第一颗树
update(, vv.size(), rt[i], rt[i-], id, );
//vv里面的数可能不止有 n 个，切记不可以用 n
}
for(int i=; i<=m; i++) {
if(ask[i].id) {
L = ask[i].l-, R = ask[i].r;
//从 L 和 R 位置开始, use 表示的从 L, R 的S根开始
for(int j=L; j; j-=lowbit(j)) use[j] = S[j];
for(int j=R; j; j-=lowbit(j)) use[j] = S[j];
int pos = query(, vv.size(), rt[L], rt[R], ask[i].k);
printf("%d\n", vv[pos-]);
} else { //第二颗树
int id = getid(a[ask[i].l]);
add(ask[i].l, id, -); //先把之前的清除掉，在加现在的
id = getid(ask[i].r);
add(ask[i].l, id, );
a[ask[i].l] = ask[i].r;
}
}
}
return ;
}