Luogu P3834 可持久化线段树2（主席树）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define maxn 200010
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;bool flag=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c==‘-‘) flag=1;
	for(;isdigit(c);c=getchar()) x=x*10+(c^48);
	if(flag) x=-x;
}

int n,m,a[maxn],num,l,r,k;
int size,s[maxn],rt[maxn<<5],ls[maxn<<5],rs[maxn<<5],cnt[maxn<<5];

void modify(int &cur,int pos,int l,int r){
    int x=++size;
    ls[x]=ls[cur],rs[x]=rs[cur],cnt[x]=cnt[cur]+1,cur=x;
    if(l==r) return ;
    int mid=(l+r)/2;
    if(pos<=mid) modify(ls[cur],pos,l,mid);
    if(pos>mid) modify(rs[cur],pos,mid+1,r);
}

int query(int k,int ql,int qr,int l,int r){
    if(l==r) return l;
    int v=cnt[ls[qr]]-cnt[ls[ql]];//********
    int mid=(l+r)/2;
    if(k<=v) return query(k,ls[ql],ls[qr],l,mid);
    if(k>v) return query(k-v,rs[ql],rs[qr],mid+1,r);
}

int main(){
    read(n),read(m);
    for(int i=1;i<=n;i++) read(a[i]),s[i]=a[i];
    sort(s+1,s+n+1);
    num=unique(s+1,s+n+1)-(s+1);
    for(int i=1;i<=n;i++) a[i]=lower_bound(s+1,s+num+1,a[i])-s;
    for(int i=1;i<=n;i++) rt[i]=rt[i-1],modify(rt[i],a[i],1,n);
    for(int i=1;i<=m;i++){
        read(l),read(r),read(k);
        printf("%d\n",s[query(k,rt[l-1],rt[r],1,n)]);
    }
    return 0;
}

Luogu P3834 可持久化线段树2（主席树）

原文：https://www.cnblogs.com/DReamLion/p/14724884.html