克鲁斯卡尔重构树

前言

~~水的时候看到的算法~~

正文

对于一些问题，比如什么在一幅图从一个点开始经过的边小于等于某个值所能达到的点集中求balabala
首先搞出最小生成树（显然只有最小生成树上的边有用）
然后从小到大枚举边，把边所连的两个点合并成一个新的点（新的点的权值等于边的权值），新的点继承原来两个点相连的边
将所有点合并完后，我们开始建克鲁斯卡尔重构树，这棵树的点就是原图中的点加上新建的点，这棵树的边是每个新建的点向合并的两个点的连边
这样就会有很好的性质，在一个节点子树内的所有叶子所代表的点在原图中互相达到经过的边小于等于这个节点的权值
然后就可以用各种算法来操作一波了

例题

[bzoj3551][ONTAK2010]Peaks加强版
本题其实大概是裸题了吧
直接克鲁斯卡尔重构树+主席树就好了
代码

#include<cstdio>
#include<cctype>
#include<algorithm>
namespace fast_IO
{const int IN_LEN=1000000,OUT_LEN=1000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);}
}
using namespace fast_IO;
#define getchar() getchar_()
#define putchar(x) putchar_((x))
#define rg register
typedef long long ll;
template <typename T> inline T max(const T a,const T b){return a>b?a:b;}
template <typename T> inline T min(const T a,const T b){return a<b?a:b;}
template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;}
template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;}
template <typename T> inline T abs(const T a){return a>0?a:-a;}
template <typename T> inline void Swap(T&a,T&b){T c=a;a=b;b=c;}
template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);}
template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;}
template <typename T> inline T square(const T x){return x*x;};
template <typename T> inline void read(T&x)
{char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;
}
template <typename T> inline void printe(const T x)
{if(x>=10)printe(x/10);putchar(x%10+'0');
}
template <typename T> inline void print(const T x)
{if(x<0)putchar('-'),printe(-x);else printe(x);
}
const int maxn=200005,maxm=500005;
int n,m,q,h[maxn],lsh[maxn],lshn;
struct edge
{int u,v,w;bool operator <(const edge&b)const{return w<b.w;}
}Q[maxm];
int bcj[maxn],node;
int fa[maxn][21],val[maxn];
void newnode()
{node++;bcj[node]=node;fa[node][0]=node;
}
int find(const int x)
{if(x==bcj[x])return x;return bcj[x]=find(bcj[x]);
}
int son[maxn][2];
int tid[maxn],tim,endd[maxn],bak[maxn];
int SZ[maxn];
void dfs(const int u)
{tid[u]=++tim,bak[tim]=u;if(son[u][0])dfs(son[u][0]),dfs(son[u][1]);endd[u]=tim;
}
struct nd
{nd *lson,*rson;int size;
}*root[maxn],empty,*Null,P[maxn*20];
int usd;
inline nd*newnd()
{usd++;nd*r=&P[usd];r->lson=r->rson=Null,r->size=0;return r;
}
nd*insert(nd*dq,nd*las,const int l,const int r,const int v)
{if(l!=r){const int mid=(l+r)>>1;if(v<=mid){dq->rson=las->rson;dq->lson=insert(newnd(),las->lson,l,mid,v);}else{dq->lson=las->lson;dq->rson=insert(newnd(),las->rson,mid+1,r,v);}}dq->size=las->size+1;return dq;
}
int kth(nd*dq,nd*las,const int l,const int r,const int k)
{if(l==r)return l;const int v=dq->rson->size-las->rson->size,mid=(l+r)>>1;if(v<k)return kth(dq->lson,las->lson,l,mid,k-v);return kth(dq->rson,las->rson,mid+1,r,k);
}
int bz(int v,const int x)
{for(rg int i=20;i>=0;i--)if(val[fa[v][i]]<=x)v=fa[v][i];return v;
}
int main()
{empty.lson=empty.rson=Null=&empty;read(n),read(m),read(q);for(rg int i=1;i<=n;i++)read(h[i]),newnode(),lsh[i]=h[i],SZ[i]=1;std::sort(lsh+1,lsh+n+1);lshn=std::unique(lsh+1,lsh+n+1)-lsh-1;for(rg int i=1;i<=n;i++)h[i]=std::lower_bound(lsh+1,lsh+lshn+1,h[i])-lsh;for(rg int i=1;i<=m;i++)read(Q[i].u),read(Q[i].v),read(Q[i].w);std::sort(Q+1,Q+m+1);for(rg int i=1;i<=m;i++){const int u=Q[i].u,v=Q[i].v,U=find(u),V=find(v);if(U==V)continue;newnode();fa[U][0]=fa[V][0]=node;val[node]=Q[i].w;bcj[U]=bcj[V]=node;son[node][0]=U,son[node][1]=V;SZ[node]=SZ[U]+SZ[V];}for(rg int i=1;i<=20;i++)for(rg int j=1;j<=node;j++)fa[j][i]=fa[fa[j][i-1]][i-1];for(rg int i=1;i<=node;i++)if(fa[i][0]==i)dfs(i);root[0]=newnd();for(rg int i=1;i<=tim;i++)root[i]=insert(newnd(),root[i-1],0,lshn,h[bak[i]]);int lastans=0;while(q--){int v,x,k;read(v),read(x),read(k);v^=lastans,x^=lastans,k^=lastans;const int T=bz(v,x);if(SZ[T]<k){print(-1),putchar('\n');lastans=0;continue;}lastans=lsh[kth(root[endd[T]],root[tid[T]-1],0,lshn,k)];print(lastans),putchar('\n');}return flush(),0;
}