调了一天了/kk

小号玄关

#include <bits/stdc++.h>
#define int long long
#define maxm 500005
#define maxn 1005
#define inf 0x3f3f3f3f3f3f
using namespace std;
int n,m,kk,len,cnt,ans_0;
int a[maxm],c[maxm],fa[maxm],sum[maxm],ans[maxm],rt[maxm];
struct node{
	int x,y,z,id;
}e[maxm],q[maxm];
bool cmp(node x,node y){
	return x.z<y.z;
}
struct Seg{
	int lson,rson,l,r,sum;
}t[maxm<<4];
#define lc t[k].lson
#define rc t[k].rson
void Pushup(int k){
	t[k].sum=t[lc].sum+t[rc].sum;
}
void Build(int &k,int l,int r,int x){
	if(l>x||r<x)return ;
	if(!k){
		k=++cnt;
		t[k]=(Seg){0,0,l,r,0};
	}
	if(l==r){
		t[k].sum++;
		return ;
	}
	int mid=l+r>>1;
	Build(lc,l,mid,x);
	Build(rc,mid+1,r,x);
	Pushup(k);
}
void Merge(int &k,int u){
	if(!k||!u){
		k=k+u;
		//t[k].sum+=t[u].sum;
		return ;
	}
	Merge(lc,t[u].lson);
	Merge(rc,t[u].rson);
	Pushup(k);
}
void Ask(int k,int x){
	if(t[k].l==t[k].r){
		ans_0=t[k].l;
		return ;
	}
	if(t[lc].sum>=x)Ask(lc,x);
	else Ask(rc,x-t[lc].sum);
}
int Getfa(int x){
	if(x==fa[x])return x;
	return fa[x]=Getfa(fa[x]);
}
void merge(int k){
	int fx=Getfa(e[k].x),fy=Getfa(e[k].y);
	if(fx!=fy){
		if(sum[fy]>sum[fx])swap(fx,fy);
		sum[fx]+=sum[fy];
		fa[fy]=fx;
		Merge(rt[fx],rt[fy]);
	}
} 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>kk;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[i]=a[i];
		fa[i]=i;
	}
	sort(c+1,c+n+1);
	len=unique(c+1,c+n+1)-c-1;
	for(int i=1;i<=m;i++){
		cin>>e[i].x>>e[i].y>>e[i].z;
		e[i].id=i;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=kk;i++){
		cin>>q[i].x>>q[i].z>>q[i].y;
		q[i].id=i;
	}
	sort(q+1,q+kk+1,cmp);
	for(int i=1;i<=n;i++){
		int num=lower_bound(c+1,c+len+1,a[i])-c;
		Build(rt[i],1,len,num);
	//	cout<<rt[i]<<"\n";
	}
	int now=1;
	for(int i=1;i<=kk;i++){
	//	cout<<"q:"<<q[i].x<<" "<<q[i].y<<" "<<q[i].z<<"\n";
		while(now<=m&&e[now].z<=q[i].z){
			merge(now);
			now++;
		}
		int fx=Getfa(q[i].x);
		ans[q[i].id]=-1;
		ans_0=-1;
		int p=t[rt[fx]].sum-q[i].y+1;
		if(p<=0)continue;
		Ask(rt[fx],p);
		if(ans_0==-1)continue;
		ans[q[i].id]=c[ans_0];
	}
	for(int i=1;i<=kk;i++)cout<<ans[i]<<"\n";
    return 0;
}