题

给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。

输入：

第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。

第二行包含N个正整数，表示这个序列各项的数字。

接下来M行每行包含三个整数l,r,k l, r, kl,r,k , 表示查询区间[l,r][l, r][l,r]内的第k小值。

输出：

包含k行，每行1个正整数，依次表示每一次查询的结果

 

//这是一道主席树模板题，在这儿先埋个伏笔 -_-|| 

做法

归并树。

就是 线段树 ， 每个节点存储 它的区间内的排序。 

询问操作时二分答案 mid。

query时 利用归并排序的思想，mid的rank就等于各区间的rank加起来，查rank用到一个upper_bound

说实话是个，，很暴力的做法，

vector 的 merge 操作很好用 在这里能省好多代码。

代码

#include
     
      #define MAXN 200005using namespace std;int read(){    int x=0,t=1;char c=getchar();    while(c<'0'||c>'9'){
   if(c=='-')t=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*t;}int N,Q,l[MAXN],r[MAXN],a[MAXN],b[MAXN],siz;vector 
      
        Node[MAXN*4]; void Build_tree(int k,int li,int ri){    l[k]=li,r[k]=ri;    int mid=li+ri>>1;    if(li==ri){Node[k].push_back(a[li]);return;}    Build_tree(k<<1,li,mid);Build_tree(k<<1|1,mid+1,ri);    Node[k].resize(ri-li+1); 　　//上面这行丢了全RE =_=    merge(Node[k<<1].begin(),Node[k<<1].end(),Node[k<<1|1].begin(),Node[k<<1|1].end(),Node[k].begin()); 　　//STLvector里的合并函数 }int Query(int k,int li,int ri,int x){    if(ri
       
        
         >1;            if(Query(1,L,R,b[mid])>=rank)Right=mid-1;            else Left=mid+1;         } 　　　　　//二分时等于号、+1、-1的问题要看个人习惯处理好,不然死都不知道怎么死的...        printf("%d\n",b[Right+1]);    }    return 0;}
        
       
      
     

 

推送

为了发展成音乐博客，写完代码顺便推歌。

写着题解的我正在听 ->

Little Do You Know　　歌手：