主席树（可持久化线段树）

先开个坑，这个坑会补的。

简介

代码

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct pp
{
    int a,id;
}a[1000010];
struct node
{
    int l,r,val;
}t[4000010];
int n,m;
int root[1000010];
int tot,f[1000010];

int modify(int pre,int l,int r,int x)
{
    int now=++tot;
    if(l==r)
    {
        t[now].val=t[pre].val+1;
        t[now].l=t[now].r=0;
        return now;
    }
    else
    {
        int mid=l+r>>1;
        if(x<=mid)
        {
            t[now].r=t[pre].r;
            t[now].l=modify(t[pre].l,l,mid,x);
        }
        else
        {
            t[now].l=t[pre].l;
            t[now].r=modify(t[pre].r,mid+1,r,x);
        }
    }
    t[now].val=t[t[now].l].val+t[t[now].r].val;
    return now;
}

int query(int root1,int root2,int l,int r,int k)
{
    if(l==r)
    {
        return l;
    }
    int mid=l+r>>1;
    int suml=t[t[root2].l].val-t[t[root1].l].val;
    if(suml>=k)
      return query(t[root1].l,t[root2].l,l,mid,k);
    else return query(t[root1].r,t[root2].r,mid+1,r,k-suml);
}

bool comp(pp a,pp b)
{
    return a.a<b.a;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].a);
        a[i].id=i;
    }
    sort(a+1,a+n+1,comp);
    int num=0;
    for(int i=1;i<=n;i++)
    {
        f[a[i].id]=i;
    }
    for(int i=1;i<=n;i++)
      root[i]=modify(root[i-1],1,n,f[i]);
    for(int i=1;i<=m;i++)
    {
        int l,r,k;
        int ans=0;
        scanf("%d%d%d",&l,&r,&k);
        ans=query(root[l-1],root[r],1,n,k);
        printf("%d\n",a[ans]);
    }
    return 0;
}