C++(clang++11) 解法, 执行用时: 2074ms, 内存消耗: 383464K, 提交时间: 2021-01-19 21:08:32

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int M=450;
int n,m,q,ans,a[N],x[N],y[N],be[N],v[N],sx[N],sy[N],s[N][M];
long long w[N];
struct dd
{
	int x,y;
	friend bool operator <(dd a,dd b)
	{
		return a.x<b.x;
	}
}b[N];
struct dp
{
	int l,r;
	long long k;
}c[N];
vector<int>g[N];
int get(int x)
{
	return (x+M-1)/M;
}
void add(int l,int r)
{
	while (l%M!=1 && l<=r) sx[l]++,l++;
	if (l>r) return;
	while (r%M!=0 && r>=l) sx[r]++,r--;
	if (l>r) return;
	for (int i=get(l);i<=get(r);i++) sy[i]++;
}
int ask(int x)
{
	return sx[x]+sy[get(x)];	
} 
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i].x=a[i],b[i].y=i;
	sort(b+1,b+n+1);
	for (int i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]);
	for (int i=1;i<=q;i++) scanf("%d%d%lld",&c[i].l,&c[i].r,&c[i].k);
	for (int i=1;i<=n;i+=M)
	{
		for (int j=1;j<=n;j++) v[j]=0;
		for (int j=i;j<min(i+M,n+1);j++) v[b[j].y]=1;
		for (int j=1;j<=n;j++) v[j]+=v[j-1];
		w[0]=0;
		for (int j=1;j<=m;j++) w[j]=w[j-1]+v[y[j]]-v[x[j]-1];
		for (int j=1;j<=q;j++)
		if (!be[j])
		{
			long long p=w[c[j].r]-w[c[j].l-1];
			if (c[j].k>p) c[j].k-=p; else be[j]=get(i);
		}
	}
	for (int i=1;i<=q;i++)
	{
		g[c[i].r].push_back(i);
		g[c[i].l-1].push_back(-i);
	}
	for (int i=1;i<=m;i++)
	{
		add(x[i],y[i]);
		for (int j=0;j<g[i].size();j++)
		{
			int u=g[i][j],f=1;
			if (u<0) f=-1,u=-u;
			int st=(be[u]-1)*M+1;
			for (int t=st;t<st+M && t<=n;t++) s[u][t-st+1]+=f*ask(b[t].y);
		}
	}
	for (int i=1;i<=q;i++)
	{
		long long p=0;
		for (int j=1;j<=M;j++)
		{
			p+=s[i][j];
			if (p>=c[i].k)
			{
				ans=(be[i]-1)*M+j;
				break;
			}
		}
		printf("%d\n",b[ans].x);
	}
	return 0;
}