Description#

给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。 第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。

Input#

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Sample Input#

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output#

3
6

题解#

区间k大+修改
直接树套树

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[10005],n;
class Treap{
    class Node{
    public:
        int size,v,key;
        Node *ch[2];
        Node(int x){
            key=rand();v=x;size=1;
            ch[0]=ch[1]=NULL;
        }
        #define size(_) ((_)?(_)->size:0)
        void Pushup(){
            size=size(ch[0])+size(ch[1])+1;
        }
    }*root;
    Node *Merge(Node *A,Node *B){
        if(!A)return B;
        if(!B)return A;
        if(A->key>B->key){
            A->ch[1]=Merge(A->ch[1],B);
            A->Pushup();
            return A;
        }
        else {
            B->ch[0]=Merge(A,B->ch[0]);
            B->Pushup();
            return B;
        }
    }
    typedef pair<Node*,Node*> DNode;
    DNode Split(Node *rt,int k){
        if(!rt)return DNode(NULL,NULL);
        DNode o;
        if(size(rt->ch[0])>=k){
            o=Split(rt->ch[0],k);
            rt->ch[0]=o.second;
            rt->Pushup();
            o.second=rt;
        }
        else{
            o=Split(rt->ch[1],k-size(rt->ch[0])-1);
            rt->ch[1]=o.first;
            rt->Pushup();
            o.first=rt;
        }
        return o;
    }
public:
    Treap(){
        root=NULL;
    }
    int kth(int k){
        DNode x=Split(root,k-1);
        DNode y=Split(x.second,1);
        Node *ans=y.first;
        root=Merge(x.first,Merge(y.first,y.second));
        return ans->v;
    }
    int rank(int x){
        return rank(root,x);
    }
    int rank(Node *rt,int x){
        if(!rt)return 0;
        return x<=rt->v?rank(rt->ch[0],x):rank(rt->ch[1],x)+size(rt->ch[0])+1;
    }
    void Insert(int x){
        int k=rank(root,x);
        DNode y=Split(root,k);
        Node *n=new Node(x);
        root=Merge(Merge(y.first,n),y.second);
    }
    void remove(int x){
        int k=rank(root,x);
        DNode a=Split(root,k);
        DNode b=Split(a.second,1);
        root=Merge(a.first,b.second);
    }
}root[40000];
#define lch l,m,rt<<1
#define rch m+1,r,rt<<1|1 

void build(int l,int r,int rt){
    for(int i=l;i<=r;i++) root[rt].Insert(a[i]);
}
void buildtree(int l,int r,int rt){
    build(l,r,rt);
    if(l==r)return;
    int m=l+r>>1;
    buildtree(lch);
    buildtree(rch);
}
void updata(int k,int x,int y,int l,int r,int rt){
    root[rt].remove(y);
    root[rt].Insert(x);
    if(l==r)return;
    int m=l+r>>1;
    if(k<=m) updata(k,x,y,lch);
    else updata(k,x,y,rch);
}
int rank(int L,int R,int x,int l,int r,int rt){
    if(L<=l&&R>=r)return root[rt].rank(x);
    int m=l+r>>1;
    if(R<=m)return rank(L,R,x,lch);
    if(L>m) return rank(L,R,x,rch);
    return rank(L,R,x,lch)+rank(L,R,x,rch);
}
int kth(int L,int R,int k){
    int l=-1e10,r=1e10;
    while(l<=r){
        int m=l+r>>1;
        int num=rank(L,R,m,1,n,1)+1;
        if(num<=k)l=m+1;
        else r=m-1;
    }
    return r;
}
int main()
{   
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    buildtree(1,n,1);
    char s[5];int i,j,k,t;
    while(m--){
        scanf("%s",s);
        if(s[0]=='Q'){
            scanf("%d%d%d",&i,&j,&k);
            printf("%d\n",kth(i,j,k));
        }
        else{
            scanf("%d%d",&i,&t);
            updata(i,t,a[i],1,n,1);
            a[i]=t;
        }
    }
}