文章目录

题目分析代码

题目

Description 在Bytemountains有$N$座山峰，每座山峰有他的高度$h_i$。有些山峰之间有双向道路相连，共$M$条路径，每条路径有一个困难值，这个值越大表示越难走，现在有$Q$组询问，每组询问询问从点$v$开始只经过困难值小于等于$x$的路径所能到达的山峰中第$k$高的山峰，如果无解输出-1。

Input 第一行三个数$N$，$M$，$Q$。 第二行$N$个数，第$i$个数为$h_i$ 接下来$M$行，每行$3$个数$a,b,c$，表示从$a$到$b$有一条困难值为$c$的双向路径。 接下来$Q$行，每行三个数$v,x,k$，表示一组询问。$v=v\oplus \text{lastans}$，$x=x\oplus \text{lastans}$，$k=k\oplus \text{lastans}$。如果$\text{lastans}=-1$则不变。

Output 对于每组询问，输出一个整数表示答案。

Sample Input

10 11 4 1 2 3 4 5 6 7 8 9 10 1 4 4 2 5 3 9 8 2 7 8 10 7 1 4 6 7 1 6 4 8 2 1 5 10 8 10 3 4 7 3 4 6 1 5 2 1 5 6 1 5 8 8 9 2

Sample Output

6 1 -1 8

Data Constraint $N\le 10^5$，$M,Q\le 5\times 10^5$，$h_i,c,x\le 10^9$。

Source By Sbullet

分析

建Kruskal重构树，然后就可以用倍增的方法$O(\log n)$求得“从点$v$开始只经过困难值小于等于$x$的路径所能到达的山峰”：

令$u$是$v$的，深度最小的，点权小于等于$x$的，一个祖先；那么$u$的子树的所有叶结点就是“从点$v$开始只经过困难值小于等于$x$的路径所能到达的山峰”。

然后查询这些叶结点中的区间第$k$大，主席树即可。 （可持久化线段树的坑以后再填吧，，，，，）

代码

注意看一下注释的地方。

#include<bits/stdc++.h> using namespace std; inline int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9') f|=c=='-',c=getchar(); while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar(); return f?-x:x; } #define LOG 20 #define MAXN 100000 #define MAXM 500000 #define MAXP (2*MAXN) int N,M,Q; int H[MAXN+5]; struct Edge{ int u,v,w; }E[MAXM+5]; bool cmp(Edge i,Edge j){ return i.w<j.w; } int fa[MAXP+5]; void Init(int n){ for(int i=1;i<=n;i++) fa[i]=i; } int Find(int u){ return fa[u]==u?u:fa[u]=Find(fa[u]); } int Num[MAXN+5]; int Rev[MAXN+5]; map<int,int> ID; struct SegmentTree{ #define lch (T[i].ch[0]) #define rch (T[i].ch[1]) struct Node{ int cnt; int ch[2]; }T[MAXN*LOG*8+5]; int N,cnt,Root[MAXP+5]; void PushUp(int i){ T[i].cnt=T[lch].cnt+T[rch].cnt; } void Insert(int &i,int l,int r,int val,int Last){ //不能写这种，要在进入之前判，否则会被卡常！！！！！ // if(val<l||val>r) // return; T[i=++cnt]=T[Last]; if(l==r){ T[i].cnt++; return; } int mid=(l+r)>>1; if(val<=mid) Insert(lch,l,mid,val,T[Last].ch[0]); else Insert(rch,mid+1,r,val,T[Last].ch[1]); PushUp(i); } int Query(int i,int l,int r,int kth,int Last){ if(l==r) return l; int mid=(l+r)>>1; int lcnt=T[lch].cnt-T[T[Last].ch[0]].cnt; if(lcnt>=kth) return Query(lch,l,mid,kth,T[Last].ch[0]); return Query(rch,mid+1,r,kth-lcnt,T[Last].ch[1]); } #undef lch #undef rch }T; #define lch (K[i].ch[0]) #define rch (K[i].ch[1]) struct KruskalNode{ int ch[2]; int w,l,r,id; }K[MAXP+5]; int id; vector<int> A; int Dep[MAXP+5]; bool vis[MAXP+5]; int Anc[MAXP+5][LOG+5]; void Build(int i,int fa,int dep){ Dep[i]=dep,vis[i]=1; if(lch&&rch){ Anc[lch][0]=Anc[rch][0]=i; Build(lch,i,dep+1); Build(rch,i,dep+1); K[i].l=K[lch].l,K[i].r=K[rch].r; } else{ K[i].l=K[i].r=++id; A.push_back(H[K[i].id]); } } #undef lch #undef rch int Query(int u,int lim,int kth){ for(int i=LOG;i>=0;i--) if(Anc[u][i]&&K[Anc[u][i]].w<=lim) u=Anc[u][i]; if(1<=kth&&kth<=K[u].r-K[u].l+1) return T.Query(T.Root[K[u].r],1,T.N,K[u].r-K[u].l-kth+2,T.Root[K[u].l-1]); return 0; } int main(){ N=read(),M=read(),Q=read(); for(int i=1;i<=N;i++) Num[i]=H[i]=read(); for(int i=1;i<=M;i++){ E[i].u=read(), E[i].v=read(), E[i].w=read(); } int cnt=0; sort(Num+1,Num+N+1); for(int i=1;i<=N;i++) if(!ID.count(Num[i])) Rev[ID[Num[i]]=++cnt]=Num[i]; for(int i=1;i<=N;i++) H[i]=ID[H[i]]; //离散化 T.N=cnt; cnt=N; Init(2*N); sort(E+1,E+M+1,cmp); for(int i=1;i<=N;i++) K[i].ch[0]=K[i].ch[1]=0,K[i].id=i; for(int i=1;i<=M;i++){ int u=E[i].u,v=E[i].v; int x=Find(u),y=Find(v); if(x!=y){ ++cnt; K[cnt].ch[0]=x; K[cnt].ch[1]=y; K[cnt].w=E[i].w; fa[x]=y,fa[y]=cnt; } } for(int i=cnt;i>=1;i--) if(!vis[i]){ int u=Find(i); Build(u,-1,1); } for(int i=0;i<int(A.size());i++) T.Insert(T.Root[i+1],1,T.N,A[i],T.Root[i]); for(int j=1;j<=LOG;j++) for(int i=1;i<=2*N;i++) Anc[i][j]=Anc[Anc[i][j-1]][j-1]; int Ans=0; while(Q--){ int u=read(),lim=read(),kth=read(); Ans=Rev[Query(u^Ans,lim^Ans,kth^Ans)]; printf("%d\n",Ans?Ans:-1); } }