【模板】可持久化线段树 2

就是区间第k大，原题链接
这个是用整体二分做的

这个是用可持久化线段树做的

线段树还是快一点啊

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
	char c=getchar();ll a=0,b=1;
	for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
	for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
struct Segment{
	ll lc,rc,cnt;
}tr[5000001];
ll n,m,a[2000001],tot,cnt,changed,b[2000001],root[5000001],c[2000001];
map<ll,ll> ma;
ll build(ll l,ll r)
{
	ll p=++tot;
	if(l==r)
	{
		tr[p].cnt=0;
		return p;
	}
	ll mid=l+r>>1;
	tr[p].lc=build(l,mid);
	tr[p].rc=build(mid+1,r);
	tr[p].cnt=tr[tr[p].lc].cnt+tr[tr[p].rc].cnt;
	return p;
}
ll insert(ll now,ll l,ll r,ll x,ll val)
{
	ll p=++tot;
	tr[p]=tr[now];
	if(l==r)
	{
		tr[p].cnt+=val;
		return p;
	}
	ll mid=l+r>>1;
	if(x<=mid)tr[p].lc=insert(tr[now].lc,l,mid,x,val);
	else tr[p].rc=insert(tr[now].rc,mid+1,r,x,val);
	tr[p].cnt=tr[tr[p].lc].cnt+tr[tr[p].rc].cnt;
	return p;
}
ll ask(ll now1,ll now2,ll l,ll r,ll k)
{
	if(l==r)return a[l];
	ll mid=l+r>>1;
	ll lcnt=tr[tr[now1].lc].cnt-tr[tr[now2].lc].cnt;
	if(k<=lcnt)return ask(tr[now1].lc,tr[now2].lc,l,mid,k);
	else return ask(tr[now1].rc,tr[now2].rc,mid+1,r,k-lcnt);
}
int main()
{
//	freopen("2.in","r",stdin);
//	freopen("2.out","w",stdout);
	n=read(),m=read();
	for(ll i=1;i<=n;i++)
		b[i]=a[i]=read();
	sort(a+1,a+1+n);
	int ned=0;ned=1;
	for(int i=2;i<=n;i++)
	{
		if(a[i]!=a[i-1])a[++ned]=a[i];
	}
	for(ll i=1;i<=ned;i++)
		ma[a[i]]=++cnt;
	for(int i=1;i<=n;i++)
	{
		b[i]=ma[b[i]];
//		cout<<b[i]<<' ';
	}
//	cout<<endl;
//	sort(b+1,b+1+n);
	for(ll i=1;i<=n;i++)
	{
		root[i]=insert(root[i-1],1,cnt,b[i],1);
	}
	for(ll i=1;i<=m;i++)
	{
		ll l=read(),r=read(),k=read();
		cout<<ask(root[r],root[l-1],1,cnt,k)<<endl;
	}
	return 0;
}
/*
5 2
1 1 3 2 2
1 3 2
3 5 2

*/