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;
}
}
}