题意：

给n、m，下面有n个数 (编号1到n)

有m个询问，询问的是上面的数的编号在[left,right]之间第k小的数

n、m<=105

题解：

①主席树入门模板题

②对于这种区间求第k小数，我们的思路就是找到一个数x，使得区间中小于x的数恰好不多于k

③于是我们可以对权值建一颗线段树，树的节点储存个数，查询的时候如果左儿子的个数>=k，就递归进左儿子找，否则就去有儿子找

④但由于这道题是区间查询，直接像之前那样建树显然只能查询整个序列，所以我们要建立可持久化线段树(主席树)

⑤显然一个数的出现次数是满足区间加减的，因此，如果要查询一个数x在区间[left,right]中出现的次数，可以用x在[1,right]中出现的次数-x在[1,left-1]中出现的次数即可

⑥于是我们就可以建主席树了

⑦查询的时候直接用right处的主席树的权值 - left-1处的主席树的权值即可

⑧进阶版：HYSBZ 1901 Dynamic Rankings （带修改主席树）

友情链接(四倍经验)：

POJ 2761 Feed the dogs

HDU 2665 Kth number

51Nod 1175 区间中第K大的数

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=100000+10;struct Node{        int lch,rch;        int data;}a[maxn<<5];int n,q,A[maxn];int Map[maxn],cnt;int root[maxn],num;void Init();void Build(int&,int,int);void Update(int&,int,int,int,int);int Query(int,int,int,int,int);signed main(){        Init();        return 0;}void Init(){        num=0;        scanf("%d%d",&n,&q);        for(int i=1;i<=n;i++){                scanf("%d",&A[i]);                Map[i]=A[i];        }        sort(Map+1,Map+1+n);        cnt=unique(Map+1,Map+1+n)-(Map+1);        Build(root[0],1,cnt);//先将根为0的树建出来(建整个树)        for(int i=1;i<=n;i++){                int x=lower_bound(Map+1,Map+1+cnt,A[i])-Map;                Update(root[i],root[i-1],1,cnt,x);        }//将每个点所影响的新链建出来        while(q--){                int left,right,k;                scanf("%d%d%d",&left,&right,&k);                int x=Query(root[left-1],root[right],1,cnt,k);                //查询区间第k大数(小→大第k个)                printf("%d\n",Map[x]);        }}void Build(int &u,int left,int right){        u=++num;        a[u].data=0;        if(left==right)return;        int mid=(left+right)>>1;        Build(a[u].lch,left,mid);        Build(a[u].rch,mid+1,right);}void Update(int &u,int y,int left,int right,int pos){        u=++num;        a[u].lch=a[y].lch;a[u].rch=a[y].rch;        a[u].data=a[y].data+1;        if(left==right)return;        int mid=(left+right)>>1;        if(pos<=mid)Update(a[u].lch,a[y].lch,left,mid,pos);        else Update(a[u].rch,a[y].rch,mid+1,right,pos);}int Query(int u,int v,int left,int right,int k){        if(left==right)return left;        int mid=(left+right)>>1;        int data=a[a[v].lch].data-a[a[u].lch].data;        if(data>=k)return Query(a[u].lch,a[v].lch,left,mid,k);        else return Query(a[u].rch,a[v].rch,mid+1,right,k-data);}