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

#include <bits/stdc++.h>
using namespace std;
const int mn=2e5+7;
struct ccf{
	int l,r,cnt;
}tree[mn*20];
int a[mn],b[mn];
int len=0,root[mn];
bool cmp(int x,int y)
{
	return x<y;
}
void build(int &k,int l,int r)
{
	k=++len;
	if(l==r)  return ;
	int m=(l+r)>>1;
	build(tree[k].l,l,m);
	build(tree[k].r,m+1,r);
}
void up(int re,int &k,int l,int r,int x)
{
	k=++len;
	tree[k]=tree[re];
	++tree[k].cnt;
	if(l==r)  return ;
	int m=(l+r)>>1;
	if(x<=m)  up(tree[re].l,tree[k].l,l,m,x);
	else  up(tree[re].r,tree[k].r,m+1,r,x);
}
int ask(int rt1,int rt2,int l,int r,int k)
{
	if(l==r)  return b[l];
	int ll=tree[rt1].l,lr=tree[rt2].l;
	int s=tree[lr].cnt-tree[ll].cnt;
	int m=(l+r)>>1;
	if(k<=s)  return ask(ll,lr,l,m,k);
	return ask(tree[rt1].r,tree[rt2].r,m+1,r,k-s);
}
int main()
{
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n,cmp);
	int e=unique(b+1,b+1+n)-b-1;
	build(root[0],1,e);
	for(int i=1;i<=n;++i)
	{
		int k=lower_bound(b+1,b+e+1,a[i])-b;
		up(root[i-1],root[i],1,e,k);
	}
	while(q--)
	{
		int x,y,k;
		scanf("%d%d%d",&x,&y,&k);
		printf("%d
",ask(root[x-1],root[y],1,e,k));
	}
}