【luoguP1533】可怜的狗狗

题目链接

发现区间按左端点排序后右端点也是单调的，所以扫一遍就行了，用权值线段树维护第\(k\)大

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<map>

#define int long long

#define lc (p<<1)

#define rc (p<<1|1)

using namespace std;

const int MAXN=2000010;

const int MAXM=500010;

inline int read(){

	int x=0,f=1; char c=getchar();

	while(c<'0'){ if(c=='-') f=-1; c=getchar(); }

	while(c>='0') x=x*10+c-'0',c=getchar();

	return x*f;

}

int n,m,a[MAXN],t[MAXN],cnt,num;

struct Query{

	int l,r,k,id;

} q[MAXM];

inline bool cmp(Query x,Query y){

	return x.l<y.l;

}

map<int,int> Map;

int rev[MAXN];

int tree[MAXN];

inline void update(int k,int d,int p=1,int l=1,int r=num){

	if(l==r){

		tree[p]+=d;

		return;

	}

	int mid=(l+r)>>1;

	if(k<=mid) update(k,d,lc,l,mid);

	else update(k,d,rc,mid+1,r);

	tree[p]=tree[lc]+tree[rc];

}

inline int query(int k,int p=1,int l=1,int r=num){

	if(l==r) return l;

	int mid=(l+r)>>1;

	if(tree[lc]>=k) return query(k,lc,l,mid);

	else return query(k-tree[lc],rc,mid+1,r);

}

int ans[MAXN];

signed main(){

	n=read(); m=read();

	for(int i=1;i<=n;++i)

		a[i]=read(),t[++cnt]=a[i];

	for(int i=1;i<=m;++i)

		q[i].l=read(),q[i].r=read(),q[i].k=read(),q[i].id=i;

	sort(q+1,q+1+m,cmp);

	sort(t+1,t+1+cnt);

	t[0]=t[1]-1;

	for(int i=1;i<=cnt;++i)

		if(t[i]!=t[i-1]) Map[t[i]]=++num,rev[num]=t[i];

	int L=1,R=0;

	for(int i=1;i<=m;++i){

		while(R<q[i].r) update(Map[a[++R]],1);

		while(L<q[i].l) update(Map[a[L++]],-1);

		ans[q[i].id]=rev[query(q[i].k)];

	}

	for(int i=1;i<=m;++i)

		printf("%lld\n",ans[i]);

	return 0;

}