题意：求区间第k小

思路：无修改主席树

AC代码：

#include "iostream"#include "iomanip"#include "string.h"#include "stack"#include "queue"#include "string"#include "vector"#include "set"#include "map"#include "algorithm"#include "stdio.h"#include "math.h"#pragma comment(linker, "/STACK:102400000,102400000")#define bug(x) cout<
     
      <<" "<<"UUUUU"<
      
       >1;    creat(ls[cur], l, mid);    creat(rs[cur], mid+1, r);}void update(int &cur, int l, int r, int p, int last){    cur=++cnt;    ls[cur]=ls[last];    rs[cur]=rs[last];    sum[cur] = sum[last]+1;    if(l==r) return;    int mid=l+r>>1;    if(p<=mid) update(ls[cur], l, mid, p, ls[cur]);    else update(rs[cur], mid+1, r, p, rs[cur]);}int query(int cur_l, int cur_r, int l, int r, int k){    if(l==r) return l;    int t=sum[ls[cur_r]]-sum[ls[cur_l]];    int mid=l+r>>1;    if(t>=k) return query(ls[cur_l], ls[cur_r], l, mid, k);    else return query(rs[cur_l], rs[cur_r], mid+1, r, k-t);}struct Node{    int id, x;    bool friend operator< (Node a, Node b){        return a.x
       
        >n>>m){        for(int i=1; i<=n; ++i){            cin>>a[i].x; a[i].id=i;        }        sort(a+1,a+1+n); cnt=0;        int sz=n;//unique(a+1,a+1+n) - (a+1); ///cout<
        
         <
         
          >l>>r>>k;            cout<