文章目录
- 题目
- 思路
- 代码
- 思考
题目
强制在线
思路
Kruskal重构树的性质：
- 是一个二叉树
- 如果是按最小生成树建立的话是一个大根堆
- 任意两个点路径上边权的最大值为它们的 LCALCALCA 的点权
这样，我们发现从圆点到根路径上的点的权值是递增的，就可以二分出小于等于 xxx 深度最浅的，然后同一子树内 dfndfndfn 序是连续的，我们就能想办法做第 kkk 大查询
我们只需要保留圆点的 dfndfndfn 序，因为方点我们只需要权值。
然后就套路了，主席树第 kkk 大，而且还是序列版本。。。
代码
#include<set>
#include<map>
#include<cmath>
#include<deque>
#include<stack>
#include<ctime>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
using namespace std;
int read(){
int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return f*x;
}
#define MAXN 100000
#define MAXM 500000
#define INF 0x3f3f3f3f
struct Edge1{
int v,nxt;
}edge[MAXN+MAXM+5];
int ecnt,head[MAXN+MAXM+5];
inline void Addedge(int u,int v){
//printf("<%d %d>\n",u,v);edge[++ecnt]=(Edge1){
v,head[u]},head[u]=ecnt;return ;
}
struct Edge2{
int u,v,w;friend bool operator < (Edge2 a,Edge2 b){
return a.w<b.w; }
}E[MAXM+5];
int n,lg2,m,q,cnt,dfn_cnt;
int h[MAXN+5],ffa[MAXN+MAXM+5],val[MAXN+MAXM+5];
int fa[MAXN+MAXM+5][21],dfn[MAXN+MAXM+5],tid[MAXN+MAXM+5],Le[MAXN+MAXM+5],Ri[MAXN+MAXM+5];
int Find(int x){
return (ffa[x]==x?x:(ffa[x]=Find(ffa[x])));}
void DFS(int u){
if(u<=n){
dfn[u]=++dfn_cnt,tid[dfn_cnt]=u,Le[u]=Ri[u]=dfn[u];return ;}for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].v;if(v==fa[u][0]) continue;fa[v][0]=u,DFS(v);Le[u]=min(Le[u],Le[v]),Ri[u]=max(Ri[u],Ri[v]);}return ;
}
void Prepare(){
for(int j=1;j<=20;j++)for(int i=1;i<=cnt;i++)fa[i][j]=fa[fa[i][j-1]][j-1];return ;
}
int rt[MAXN+5],ncnt,ch[30*MAXN+5][2],siz[30*MAXN+5];
void Copy(int u,int pre){
ch[u][0]=ch[pre][0],ch[u][1]=ch[pre][1],siz[u]=siz[pre];return ;
}
void Insert(int &u,int pre,int L,int R,int val){
u=++ncnt,Copy(u,pre),siz[u]++;if(L==R) return ;int Mid=(L+R)>>1;if(val<=Mid) Insert(ch[u][0],ch[pre][0],L,Mid,val);else Insert(ch[u][1],ch[pre][1],Mid+1,R,val);return ;
}
int Query_Kth(int u,int v,int L,int R,int k){
if(L==R) return L;int Mid=(L+R)>>1,lsiz=siz[ch[v][0]]-siz[ch[u][0]];if(k<=lsiz) return Query_Kth(ch[u][0],ch[v][0],L,Mid,k);else return Query_Kth(ch[u][1],ch[v][1],Mid+1,R,k-lsiz);
}
int dcnt,D[MAXN+5];
void Discrete(){
sort(D+1,D+dcnt+1);dcnt=unique(D+1,D+dcnt+1)-(D+1);return ;
}
int Query(int u,int x,int k){
for(int j=20;j>=0;j--)if(fa[u][j]&&val[fa[u][j]]<=x)u=fa[u][j];if(Ri[u]-Le[u]+1<k)return -1;k=Ri[u]-Le[u]+1-k+1;return D[Query_Kth(rt[Le[u]-1],rt[Ri[u]],1,dcnt,k)];
}
int main(){
n=read(),m=read(),q=read(),lg2=(int)log2(n);for(int i=1;i<=n;i++)D[++dcnt]=h[i]=read();Discrete();for(int i=1;i<=n;i++)h[i]=lower_bound(D+1,D+dcnt+1,h[i])-D;for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();E[i]=(Edge2){
u,v,w};}cnt=n,sort(E+1,E+m+1);for(int i=1;i<=n;i++)ffa[i]=i;val[0]=INF;for(int i=1;i<=m;i++){
int fu=Find(E[i].u),fv=Find(E[i].v);if(fu==fv) continue;val[++cnt]=E[i].w;ffa[fu]=ffa[fv]=ffa[cnt]=cnt;Addedge(cnt,fu),Addedge(cnt,fv);}memset(Le,63,sizeof(Le));for(int i=1;i<=cnt;i++)if(ffa[i]==i)DFS(i);//for(int i=n+1;i<=cnt;i++)// printf("[%d %d]\n",i,val[i]);//for(int i=1;i<=n;i++)// printf("{%d %d}\n",i,dfn[i]);Prepare();for(int i=1;i<=n;i++)Insert(rt[i],rt[i-1],1,dcnt,h[tid[i]]);int lastans=0;for(int i=1;i<=q;i++){
int v=read(),x=read(),k=read();if(lastans!=-1) v^=lastans,x^=lastans,k^=lastans;lastans=Query(v,x,k);printf("%d\n",lastans);}return 0;
}思考
注意第 kkk 大和第 kkk
第 kkk 大：从大到小第 kkk 个
第 kkk 小：从小到大第 kkk 个
还有
void Prepare(){
for(int j=1;j<=20;j++)for(int i=1;i<=cnt;i++)//不是n!!!fa[i][j]=fa[fa[i][j-1]][j-1];return ;
}
血的教训。。。