Problem Description
There are N boys in CodeLand.
Boy i has his coding skill Ai.
CRB wants to know who has the suitable coding skill.
So you should treat the following two types of queries.
Query 1: 1 l v
The coding skill of Boy l has changed to v.
Query 2: 2 l r k
This is a report query which asks the k-th smallest value of coding skill between Boy l and Boy r(both inclusive).

Input
There are multiple test cases.
The first line contains a single integer N.
Next line contains N space separated integers A1, A2, …, AN, where Ai denotes initial coding skill of Boy i.
Next line contains a single integer Q representing the number of queries.
Next Q lines contain queries which can be any of the two types.
1 ≤ N, Q ≤ 105
1 ≤ Ai, v ≤ 109
1 ≤ l ≤ r ≤ N
1 ≤ k ≤ r – l + 1

Output
For each query of type 2, output a single integer corresponding to the answer in a single line.

Sample Input

5
1 2 3 4 5
3
2 2 4 2
1 3 6
2 2 4 2

Sample Output

3
4

题意：动态区间第K大。
解法：

我们将树状数组的每一个节点代表对应的数字（需要将询问读入，然后把所有出现的数字离散化），平衡树中保存每一个数在序列中的下标。
修改：将原来序列中的数字在对应的树状数组套的平衡树中删除，再同理插入新的数字
询问：考虑答案的二进制表示，通过巧妙地运用树状数组的性质，我们可以从高位往地位贪心的构造答案，每次贪心在平衡树中查找对应区间的数字个数。
修改时间复杂度O(log^2N)
询问时间复杂度O(log^2N)

#include <bits/stdc++.h>
///树状数组的每一个节点代表对应的数字（需要将询问读入，然后把所有出现的数字离散化），平衡树中保存每一个数在序列中的下标。 #include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
const int maxn = 100010;
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> bit[maxn*4];
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>::iterator it;
//exSTL红黑树,G++ Only,低版本中null_type为null_mapped_type
struct node{int op,l,r,k;}q[maxn];
int num[maxn], n, H, Hash[maxn*4], cnt;
int lowbit(int x){return x&-x;}
void add(int pos, int val){
    for(int i=pos; i<=cnt; i+=lowbit(i)) bit[i].insert(val);
}
void del(int pos, int val){
    for(int i=pos; i<=cnt; i+=lowbit(i)) bit[i].erase(val);
}
int getid(int x){
    return lower_bound(Hash,Hash+cnt,x)-Hash+1;
}
int query(int l, int r, int k){//查询到的是下标
    int num = 0;
    for(int i=H; i; i>>=1){
        int tmp = num+i;
        if(tmp > cnt) continue;
        int rnk = bit[tmp].order_of_key(r+1)-bit[tmp].order_of_key(l);
        if(rnk >= k) continue;
        num = tmp, k-=rnk;
    }
    return num;
}
int main()
{
    int t,n,qq;
    while(~scanf("%d", &n)){
        cnt = 0;
        for(int i=1; i<=n; i++){
            scanf("%d", &num[i]);
            Hash[cnt++] = num[i];
        }
        scanf("%d", &qq);
        for(int i=1; i<=qq; i++){
            scanf("%d", &q[i].op);
            if(q[i].op==1){
                scanf("%d %d",&q[i].l,&q[i].k);
                Hash[cnt++]=q[i].k;
            }
            else{
                scanf("%d %d %d", &q[i].l, &q[i].r, &q[i].k);
            }
        }
//        for(int i=0; i<cnt; i++) printf("%d ", Hash[i]); printf("\n");
        sort(Hash, Hash+cnt);
        cnt = unique(Hash, Hash+cnt)-Hash;
        for(int i=1; i<=cnt; i++) bit[i].clear();
        H = 1;
        while(H*2 < cnt) H*=2;
        for(int i=1; i<=cnt; i++){
            if(q[i].op == 1){
                q[i].k = getid(q[i].k);
            }
        }
        for(int i=1; i<=n; i++){
            num[i] = getid(num[i]);
            add(num[i], i);
        }
        for(int i=1; i<=qq; i++){
            if(q[i].op == 1){
                del(num[q[i].l], q[i].l);
                add(q[i].k, q[i].l);
                num[q[i].l] = q[i].k;
            }
            else{
                printf("%d\n", Hash[query(q[i].l, q[i].r, q[i].k)]);
            }
        }
    }
    return 0;
}