可持久化线段树(静态区间第k最值)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 3;
int a[maxn],b[maxn],ls[maxn<<5],rs[maxn<<5],t[maxn<<5],sum[maxn<<5],tot;
int build(int l,int r)
{
	int p=++tot;
	if(l==r) return p;
	int mid=(l+r)>>1;
	ls[p]=build(l,mid);
	rs[p]=build(mid+1,r);
	return p;
}
int update(int pre,int l,int r,int x)
{
	int now=++tot;
	ls[now]=ls[pre],rs[now]=rs[pre],sum[now]=sum[pre]+1;
	if(l<r) {
		int mid=(l+r)>>1;
		if(x<=mid) ls[now]=update(ls[pre],l,mid,x);
		else rs[now]=update(rs[pre],mid+1,r,x);	
	}
	return now;
}
int query(int u,int v,int l,int r,int k)
{
	if(l==r) return l;
	int mid=(l+r)>>1,num=sum[ls[v]]-sum[ls[u]];
	if(k<=num) return query(ls[u],ls[v],l,mid,k);
	else return query(rs[u],rs[v],mid+1,r,k-num);
}
int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	int m=unique(b+1,b+1+n)-(b+1);
	t[0]=build(1,m);
	for(int i=1;i<=n;i++) {
		int x=lower_bound(b+1,b+1+m,a[i])-b;
		t[i]=update(t[i-1],1,m,x);
	}
	while(q--)
	{
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",b[query(t[l-1],t[r],1,m,k)]);
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 3;
int a[maxn],b[maxn],ls[maxn<<5],rs[maxn<<5],t[maxn<<5],sum[maxn<<5],tot;
int build(int l,int r)
{
    int p=++tot;
    if(l==r) return p;
    int mid=(l+r)>>1;
    ls[p]=build(l,mid);
    rs[p]=build(mid+1,r);
    return p;
}
int update(int pre,int l,int r,int x)
{
    int now=++tot;
    ls[now]=ls[pre],rs[now]=rs[pre],sum[now]=sum[pre]+1;
    if(l<r) {
        int mid=(l+r)>>1;
        if(x<=mid) ls[now]=update(ls[pre],l,mid,x);
        else rs[now]=update(rs[pre],mid+1,r,x);    
    }
    return now;
}
int query(int u,int v,int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1,num=sum[ls[v]]-sum[ls[u]];
    if(k<=num) return query(ls[u],ls[v],l,mid,k);
    else return query(rs[u],rs[v],mid+1,r,k-num);
}
int main()
{
    int kase;
    scanf("%d",&kase);
    while(kase--)
    {
        int n,q;
        scanf("%d%d",&n,&q);
        tot=0;
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        sort(b+1,b+1+n);
        int m=unique(b+1,b+1+n)-(b+1);
        t[0]=build(1,m);
        for(int i=1;i<=n;i++) {
            int x=lower_bound(b+1,b+1+m,a[i])-b;
            t[i]=update(t[i-1],1,m,x);
        }
        while(q--)
        {
            int l,r,k;
            scanf("%d%d%d",&l,&r,&k);
            printf("%d\n",b[query(t[l-1],t[r],1,m,k)]);
        }
    }
    return 0;
}