传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3551
搞了一上午的系统总算是弄好了，颓
经典题，很早就想做了，正巧要给初三爷讲并$(zhu)$查$(xi)$集$(shu)$，然后发现这道题可以放作业题_(:зゝ∠)_
先是看了$Claris$的题解，瞬间变成猪，太神了和我的逗比做法完全不同
考虑$kruskal$重构树， 对于一条新加入的边$(x,y)$，新建一个节点$z$，把$x$的父亲指向$z$，$y$也一样，$z$的点权为$(x,y)$的边权，用并查集维护，这样就构出了一棵新的树
这个树有什么性质呢，因为边是从小到大加的，于是深度越大点权越小，然后可以发现，对于询问从$v$出发边权小于$x$所能达到的联通块，也就是从$v$向上爬最高的点权小于$x$的点的子树，这个东西可以倍增找，由于我比较弱于是写了树剖，在重链里二分，然后就变成一道裸的$dfs$序主席树了
别问我为什么辣么快，我系不会告诉你的
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 100010
int i,j,k,m,n,x,y,lastans,fa[N<<1],Q,id[N<<1],hs[N],rk[N<<1],top[N<<1],sz[N<<1],dep[N<<1],f[N<<1],in[N<<1],now,ot[N<<1],son[N<<1],tot,cnt,L,h[N],last[N<<1],v[N<<1];bool vis[N<<1];
struct edge{int to,next;}e[N<<2];
struct abc{
int x,y,z;
inline void in(){x=read(),y=read(),z=read();}
inline bool operator<(const abc&b)const{return z<b.z;}
}o[N*5];
struct tree{int l,r,cnt;}T[(N<<1)*20];
inline void add(int u,int v){e[++cnt]=(edge){v,last[u]},last[u]=cnt;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void dfs1(int x,int d){
dep[x]=d,sz[x]=1,vis[x]=1;
for(int i=last[x],y;i;i=e[i].next){
f[y=e[i].to]=x,dfs1(y,x),sz[x]+=sz[y];
if(sz[y]>sz[son[x]])son[x]=y;
}
}
void dfs2(int x,int d){
top[x]=d,rk[in[x]=++now]=x;if(son[x])dfs2(son[x],d);
for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=son[x])dfs2(y,y);ot[x]=now;
}
void insert(int&y,int k,int l,int r,int v){
T[y=++L].cnt=T[k].cnt+1;if(l==r)return;
T[y]=(tree){T[k].l,T[k].r,T[y].cnt};int m=l+r>>1;
v<=m?insert(T[y].l,T[k].l,l,m,v):insert(T[y].r,T[k].r,m+1,r,v);
}
inline int ef(int l,int r,int x){
while(l<=r){
int m=l+r>>1;
if(v[rk[m]]>x)l=m+1;else r=m-1;
}return rk[r+1];
}
inline int up(int l,int r,int x){
while(top[l]!=r)if(v[f[top[l]]]<=x)l=f[top[l]];else return ef(in[top[l]],in[l],x);
return ef(in[r],in[l],x);
}
int ask(int l,int r,int o,int v,int kth){
if(l==r)return l;int m=l+r>>1;
int ret=T[T[v].l].cnt-T[T[o].l].cnt;
if(kth<=ret)return ask(l,m,T[o].l,T[v].l,kth);
else return ask(m+1,r,T[o].r,T[v].r,kth-ret);
}
int main(){
for(n=read(),m=read(),Q=read(),i=1;i<=n;++i)hs[i]=h[i]=read();
for(i=1;i<=m;++i)o[i].in();
for(i=1;i<=n<<1;++i)fa[i]=i;
for(tot=n,sort(o+1,o+m+1),i=1;i<=m;++i){
int p=find(o[i].x),q=find(o[i].y);
if(p!=q)fa[p]=fa[q]=++tot,v[tot]=o[i].z,add(tot,p),add(tot,q);
}
for(i=1;i<=n;++i)if(!vis[i])dfs1(find(i),1),dfs2(find(i),find(i));
for(sort(hs+1,hs+n+1),i=1;i<=n;++i)h[i]=lower_bound(hs+1,hs+n+1,h[i])-hs;
for(i=1;i<=now;++i)if(rk[i]<=n)insert(id[i],id[i-1],1,n,h[rk[i]]);
else id[i]=id[i-1];
for(i=1;i<=Q;++i){
int v=read(),x=read(),k=read();
if(lastans!=-1)v^=lastans,x^=lastans,k^=lastans;
int t=up(v,find(v),x),a=id[in[t]],b=id[ot[t]];
if(T[b].cnt-T[a].cnt<k)lastans=-1;
else lastans=hs[ask(1,n,a,b,T[b].cnt-T[a].cnt-k+1)];
printf("%d\n",lastans);
}
}
$loading...$
评论 (0)
