Description
【题目描述】同3545
Input
第一行三个数N，M，Q。
第二行N个数，第i个数为h_i
接下来M行，每行3个数a b c，表示从a到b有一条困难值为c的双向路径。
接下来Q行，每行三个数v x k，表示一组询问。v=v xor lastans，x=x xor lastans，k=k xor lastans。如果lastans=-1则不变。
Output
同3545
【思路】
Kruskal+主席树+dfs序
一个叫kruskal重构树的方法QWQ。在kruskal合并子树的时候新建一个ext结点，然后让它成为两棵子树公共的根，赋边权为权值。
新建成的树的性质：
对于一个询问，我们找到v的点权值不超过x的最小祖先，以该祖先为根的子树中所有的点与v都满足条件，然后就是在一个子树中找到第k大的问题，可以基于dfs序建主席树处理。
【代码】
#include<cstdlib>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; typedef long long ll;
const int N = ;
const int M = ;
const int D = ; struct Edge {
int u,v,w;
bool operator < (const Edge& rhs) const {
return w<rhs.w;
}
};
struct LEdge { int v,nxt;
};
struct Tnode{
int lc,rc,sum;
}T[M]; ll read() {
char c=getchar();
ll f=,x=;
while(!isdigit(c)) {
if(c=='-') f=-; c=getchar();
}
while(isdigit(c))
x=x*+c-'',c=getchar();
return x*f;
} int n,m,q,sz,tot,dfsc;
int hash[N],h[N],rt[N],val[N],bin[N];
int p[N],dep[N],fa[N][D],mx[N][D],L[N],R[N]; Edge es[N<<]; LEdge e[N<<];
int en=-,front[N];
void adde(int u,int v)
{
en++; e[en].v=v; e[en].nxt=front[u]; front[u]=en;
}
int ifind(int u)
{
return u==p[u]? u: p[u]=ifind(p[u]);
}
void update(int l,int r,int x,int& y,int num)
{
T[y=++sz]=T[x];
T[y].sum++;
if(l>=r) return ;
int mid=(l+r)>>;
if(num<=mid) update(l,mid,T[x].lc,T[y].lc,num);
else update(mid+,r,T[x].rc,T[y].rc,num);
}
int query(int l,int r,int a,int b,int rk)
{
int mid=(l+r)>>;
if(l>=r) return mid;
int now=T[T[b].rc].sum-T[T[a].rc].sum;
if(rk<=now) return query(mid+,r,T[a].rc,T[b].rc,rk);
else return query(l,mid,T[a].lc,T[b].lc,rk-now);
}
void dfs(int u)
{
L[u]=++dfsc;
update(,tot,rt[L[u]-],rt[L[u]],h[u]);
FOR(i,,D-) {
fa[u][i]=fa[fa[u][i-]][i-];
mx[u][i]=max(mx[u][i-],mx[fa[u][i-]][i-]);
}
for(int i=front[u];i>=;i=e[i].nxt) {
int v=e[i].v;
dep[v]=dep[u]+,
dfs(v);
}
R[u]=dfsc;
}
int find_root(int u,int x)
{
for(int i=D-;i>=;i--)
if(fa[u][i] && mx[u][i]<=x)
u=fa[u][i];
return u;
} int main()
{
//reopen("in.in","r",stdin);
//freopen("out.out","w",stdout); memset(front,-,sizeof(front));
n=read(),m=read(),q=read();
FOR(i,,n) h[i]=read(),hash[i]=h[i];
int u,v,w,x,k,ans=;
FOR(i,,m) {
u=read(),v=read(),w=read();
es[i]=(Edge){u,v,w};
} FOR(i,,*n) p[i]=i;
sort(hash+,hash+n+);
tot=unique(hash+,hash+n+)-hash-;
FOR(i,,n)
h[i]=lower_bound(hash+,hash+tot+,h[i])-hash; sort(es+,es+m+);
FOR(i,,m) {
Edge e=es[i];
int x=ifind(e.u),y=ifind(e.v);
if(x!=y) {
int ext=++n;
fa[x][]=fa[y][]=ext;
mx[x][]=mx[y][]=e.w;
p[x]=p[y]=ext;
adde(ext,x),adde(ext,y);
}
} dfs(n); FOR(i,,q) {
v=read(),x=read(),k=read();
v^=ans,x^=ans,k^=ans;
int root=find_root(v,x);
if(R[root]-L[root]+<k) puts("-1"),ans=;
else {
ans=query(,tot,rt[L[root]-],rt[R[root]],k);
if(!ans) puts("-1");
else printf("%d\n",ans=hash[ans]);
}
}
return ;
}