[文章目录]
Description
同3545 ， 强制在线
纳尼？？？强制在线？？？
先预处理，将整个合并过程每个时间对应的树都存下来，那么每次合并就需要建一个新树，记录根。接下来问题就在于找到对应权值对应节点的根。
我们每次合并的时候是将y变成x的一个儿子，之后y便不再作为连通块的标记，假设每个合并操作我们都把x向y连一条边，边权为合并的权值，那么生成的图发现是一个森林。并且根到叶子的边权满足单调性。
假设v节点，x权值所对应时刻x所在的联通块的标记为y节点，那么一定满足v节点一直向祖先走，直到合并的权值大于x的时候到达的节点就是y。那么只需要找到以y节点代表联通块的时候的对应的根。
对于一个节点代表自己所在联通块变化的时候，将根和权值扔进该节点的链表中，发现权值同样满足单调性，每次找到节点后二分权值找到根。
时间复杂度O(nlogn+mlogn)
自己YY的做法居然A了。开心。读入优化很重要。。。
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100100
const int inf=0x3f3f3f3f;
int n,m,q,h[N],b[N],c[N],tot;
inline char nc()
{
static char buf[100000] , *p1 , *p2;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 100000 , stdin) , p1 == p2) ? EOF : *p1 ++ ;
}
inline void read(int &x)
{
char ch=nc(); x=0;
while(ch<'0'||ch>'9') ch=nc();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=nc();
}
inline int getid(int x) {return lower_bound(c+1,c+tot+1,x)-c;}
struct edge {
int x,y,w;
}ed[N*5];
bool cmp(edge x,edge y){return x.w<y.w;}
int fa[N][17],data[N];
bool rd[N];
struct node {
int rt,w;
};
vector<node>ve[N];
struct seg
{
int ls,rs,siz;
}s[N*40];
int se,rt[N],f[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int merge(int x,int y)
{
if(!x||!y) return x|y;
int re=++se; s[re].siz=s[x].siz+s[y].siz;
s[re].ls=merge(s[x].ls,s[y].ls);
s[re].rs=merge(s[x].rs,s[y].rs);
return re;
}
void insert(int l,int r,int &x,int z)
{
x=++se; s[x].siz=1;
if(l==r) return ; int mid=(l+r)>>1;
if(z<=mid) insert(l,mid,s[x].ls,z);
else insert(mid+1,r,s[x].rs,z);
}
int query(int l,int r,int x,int y)
{
if(l==r) return c[l];
int mid=(l+r)>>1,z=s[s[x].ls].siz;
if(y<=z) return query(l,mid,s[x].ls,y);
else return query(mid+1,r,s[x].rs,y-z);
}
int main()
{
scanf("%d%d%d",&n,&m,&q); int i;
for(i=1;i<=n;++i) {read(h[i]); b[i]=h[i]; f[i]=i;}
sort(b+1,b+n+1); c[++tot]=b[1];
for(i=2;i<=n;++i) if(b[i]!=b[i-1]) c[++tot]=b[i];
for(i=1;i<=n;++i)
{
insert(1,tot,rt[i],getid(h[i]));
ve[i].push_back((node){rt[i],-1});
}
for(i=1;i<=m;++i) {read(ed[i].x); read(ed[i].y); read(ed[i].w);}
sort(ed+1,ed+m+1,cmp); int x,y;
for(i=1;i<=m;++i)
{
x=find(ed[i].x); y=find(ed[i].y);
if(x!=y)
{
f[y]=x; rd[y]=1; fa[y][0]=x; data[y]=ed[i].w;
rt[x]=merge(rt[x],rt[y]);
ve[x].push_back((node){rt[x],ed[i].w});
}
}
for(i=0;i<=n;++i) if(!rd[i]) data[i]=inf;
for(i=1;i<=16;++i)
for(int j=1;j<=n;++j)
fa[j][i]=fa[fa[j][i-1]][i-1];
int ans=-1,l,r,mid,v,k,rot;
while(q--)
{
read(v); read(x); read(k);
if(ans!=-1) v^=ans,x^=ans,k^=ans;
for(i=16;~i;--i) if(data[fa[v][i]]<=x) v=fa[v][i];
if(data[v]<=x&&fa[v][0]) v=fa[v][0];
l=0,r=ve[v].size();
while(l<r)
{
mid=(l+r)>>1;
if(ve[v][mid].w<=x) l=mid+1;
else r=mid;
}
rot=ve[v][l-1].rt;
if(s[rot].siz<k) ans=-1;
else ans=query(1,tot,rot,s[rot].siz-k+1);
printf("%d\n",ans);
}
return 0;
}