求找不同

#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0;
	char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+(c-'0'),c=getchar();
	return x;
}
struct node{
	int x,y,z;
}b[1000005];
bool cmp(node a,node b){
	return a.z<b.z;
}
int n,a[1000005],m,q,x,y,z,j;
map<int,int> ma,rma;
int fat[1000005],topp;
int Findf(int k){
	if(fat[k]==k) return k;
	return fat[k]=Findf(fat[k]);
}
int l[1000005],r[1000005],c[1000005],rr;
void build(){
	sort(b+1,b+1+m,cmp);
	for(int i=1;i<=n;i++) fat[i]=++topp;
	for(int i=1;i<=m;i++){
		int x=Findf(b[i].x),y=Findf(b[i].y);	
		if(x==y) continue;
		++topp,fat[topp]=fat[x]=fat[y]=topp;
		l[topp]=x,r[topp]=y,c[topp]=b[i].z;
	}
	rr=Findf(1);
}
int rt[1000005],ls[8000005],rs[8000005],f[8000005],top;
int update(int rot,int l,int r,int k){
	int root=++top,mid=(l+r)>>1;
	f[root]=f[rot],ls[root]=ls[rot],rs[root]=rs[rot];
	if(l==r){ f[root]++;return root; }
	if(k<=mid) ls[root]=update(ls[root],l,mid,k);
	else rs[root]=update(rs[root],mid+1,r,k);
	f[root]=f[ls[root]]+f[rs[root]];
	return root;
}
int Find(int rot,int root,int l,int r,int k){
	if(l==r) return f[root]-f[rot]<k?-1:l;
	int mid=(l+r)>>1;
	if(k<=f[rs[root]]-f[rs[rot]]) return Find(rs[rot],rs[root],mid+1,r,k);
	else return Find(ls[rot],ls[root],l,mid,k-f[rs[root]]+f[rs[rot]]);
}
int siz[1000005],fa[1000005][30],dfn[1000005],df;
void dfs(int x,int fat){
	siz[x]=1,fa[x][0]=fat,dfn[x]=++df;
	if(x<=n){ rt[dfn[x]]=update(rt[dfn[x]-1],1,n,a[x]);return; } 
	else rt[dfn[x]]=rt[dfn[x]-1];
	if(l[x]) dfs(l[x],x),siz[x]+=siz[l[x]];
	if(r[x]) dfs(r[x],x),siz[x]+=siz[r[x]];
}
int main(){
	n=read(),m=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=read(),ma[a[i]]=1;
	for(map<int,int>::iterator i=ma.begin();i!=ma.end();i++)
		i->second=++j,rma[i->second]=i->first;
	for(int i=1;i<=n;i++) a[i]=ma[a[i]];
	for(int i=1;i<=m;i++) b[i]={read(),read(),read()};
	build(),dfs(rr,0);
	for(int i=1;i<=25;i++) for(int j=1;j<=top;j++)
		fa[j][i]=fa[fa[j][i-1]][i-1];
	for(int i=1;i<=q;i++){
		x=read(),y=read(),z=read();
		int k=x;
		for(int j=25;j>=0;j--) if(fa[k][j]&&c[fa[k][j]]<=y)
			k=fa[k][j];
		int l=rma[Find(rt[dfn[k]-1],rt[dfn[k]+siz[k]-1],1,n,z)];
		printf("%d\n",l==0?-1:l);
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0;
	char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+(c-'0'),c=getchar();
	return x;
}
int n,m,q,a[100005],j,x,y,z;
map<int,int> ma,rma;
struct node{
	int x,y,z;
}b[500005];
bool cmp(node a,node b){
	return a.z<b.z;
}
int fat[800005],c[800005],ls[800005],rs[800005],top,rot;
int Findf(int x){
	if(x==fat[x]) return x;
	return fat[x]=Findf(fat[x]);
}
void build(){
	for(int i=1;i<=n;i++) fat[i]=++top;
	sort(b+1,b+1+m,cmp);
	for(int i=1;i<=m;i++){
		int x=Findf(b[i].x),y=Findf(b[i].y);
		if(x==y) continue;
		++top;fat[top]=fat[x]=fat[y]=top;
		ls[top]=x,rs[top]=y,c[top]=b[i].z;
	}
	rot=Findf(1);
}
int rt[800005],f[8000005],lss[8000005],rss[8000005],topp;
int update(int root,int l,int r,int k){
	int rot=++topp,mid=(l+r)>>1;
	f[rot]=f[root],lss[rot]=lss[root],rss[rot]=rss[root];
	if(l==r){ f[rot]++;return rot; }
	if(k<=mid) lss[rot]=update(lss[root],l,mid,k);
	else rss[rot]=update(rss[root],mid+1,r,k);
	f[rot]=f[lss[rot]]+f[rss[rot]];
	return rot;
}
int Find(int root1,int root2,int l,int r,int k){
	if(l==r){
		if(k>f[root2]-f[root1]) return -1;
		else return l;
	}
	int mid=(l+r)>>1;
	//cout<<root1<<" "<<root2<<" "<<l<<" "<<r<<" "<<k<<" "<<f[rss[root2]]<<" "<<f[rss[root1]]<<"\n";
	if(k<=f[rss[root2]]-f[rss[root1]]) return Find(rss[root1],rss[root2],mid+1,r,k);
	else return Find(lss[root1],lss[root2],l,mid,k-(f[rss[root2]]-f[rss[root1]]));
}
int fa[800005][30],dfn[800005],df,siz[800005];
void dfs(int x,int ff){
	fa[x][0]=ff,siz[x]=1,dfn[x]=++df;
	if(x<=n){ rt[df]=update(rt[df-1],1,n,a[x]);return; }
	else rt[df]=rt[df-1];
	if(ls[x]) dfs(ls[x],x);
	if(rs[x]) dfs(rs[x],x);
	siz[x]+=siz[ls[x]]+siz[rs[x]];
}
int main(){
	n=read(),m=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=read(),ma[a[i]]=1;
	for(map<int,int>::iterator i=ma.begin();i!=ma.end();i++)
		i->second=++j,rma[i->second]=i->first;
	for(int i=1;i<=n;i++) a[i]=ma[a[i]];
	for(int i=1;i<=m;i++) b[i]={read(),read(),read()};
	build(),dfs(rot,0);
	for(int i=1;i<=25;i++) for(int j=1;j<=top;j++)
		fa[j][i]=fa[fa[j][i-1]][i-1];
	int l=0;
	for(int i=1;i<=q;i++){
		x=read(),y=read(),z=read();
		int p=x;
		for(int i=25;i>=0;i--) if(fa[p][i]&&c[fa[p][i]]<=y)
			p=fa[p][i];
		l=rma[Find(rt[dfn[p]-1],rt[dfn[p]+siz[p]-1],1,n,z)];
		printf("%d\n",l==0?-1:l);
	}
	return 0;
}