P3834 【模板】可持久化线段树 1（主席树）

 #include <bits/stdc++.h>

 #define read read()

 #define up(i,l,r) for(int i = (l);i <= (r);i++)

 using namespace std;

 int read

 {

     int x = ,f = ; char ch = getchar();

     while(ch <  || ch > ) {if(ch == '-') f = -; ch = getchar();}

     while(ch >= && ch <=) {x =  * x + ch - ; ch = getchar();}

     return x * f;

 }

 const int N = 2e5+;

 struct a

 {

     int l,r,sum;

 }node[N*];

 int n,m,cnt,a[N],root[N];

 vector<int> v;

 int Get_id(int x) {return lower_bound(v.begin(),v.end(),x) - v.begin() + ;}

 void update(int l,int r,int &cur,int pre,int pos)

 {

     node[++cnt] = node[pre],node[cnt].sum++,cur = cnt;

     if(l==r) return;

     int mid = (l+r)>>;

     if(pos<=mid) update(l,mid,node[cur].l,node[pre].l,pos);

     else update(mid+,r,node[cur].r,node[pre].r,pos);

 }

 int query(int l,int r,int x,int y,int k)

 {

     if(l==r) return l;

     int mid = (l+r)>>;

     int lsum = node[node[y].l].sum - node[node[x].l].sum;

     if(lsum>=k) return query(l,mid,node[x].l,node[y].l,k);

     else return query(mid+,r,node[x].r,node[y].r,k-lsum);

 }

 int main()

 {

     freopen("input.txt","r",stdin);

     n = read; m = read;

     int l,r,k;

     up(i,,n) a[i] = read,v.push_back(a[i]);

     sort(v.begin(),v.end());

     v.erase(unique(v.begin(),v.end()),v.end());

     up(i,,n) update(,n,root[i],root[i-],Get_id(a[i]));

     up(i,,m)

     {

         l = read; r = read; k = read;

         printf("%d\n",v[query(,n,root[l-],root[r],k)-]);

     }

     return ;

 }