P4197 Peaks

感谢[HRLYB](https://www.luogu.org/space/show?uid=126621)的指出 #### [更多内容在我的博客](https://www.cnblogs.com/asd369-blog/p/P4197-Peaks.html) 以惊人的毅力调完了这道题 ~~（虽然最后发现是个sb错误）~~ 其实这道题还是很裸的……由于有困难值的限制，所以想到$Kruskal$重构树，然后对于询问中不能经过困难值大于$x$的路径，反映在重构树上就是只**在点权小于等于$x$的节点的子树上移动** 样例的重构树大概长这样 ~~(图难看忍忍)~~  #### （红色括号内是点权，白色的点是$Kruskal$重构树中新加的点） 接着是求第$k$大（显然用主席树啦$qwq$） 一开始我想直接打个$dfs$序，因为是子树上的问题。但通过上面的图，发现其实**每个点都对应一段区间**，例如$19$对应的区间就是$(0,10]$，于是问题就变得更为简化了。 ~~丑陋的代码~~（休想直接复制）： ```cpp #pragma GCC optimize(3) //手动O3 #include<bits/stdc++.h> using namespace std; template <typename T> inline void Read(T &t) { int c=getchar(),f=0; for(;c<'0'||c>'9';c=getchar())f=(c=='-'); for(t=0;c>='0'&&c<='9';c=getchar())t=(t<<3)+(t<<1)+(c^48); if(f)t=-t; } const int N=2e5+5,M=5e5+5; int n,m,q,tot,cnt,num,size; int head[N],b[N],h[N],f[N],diff[N],fa[N][25]; int Rt[N],range[N][2]; struct Edge { int u,v,dif,next; void add(int x, int y, int d) {u=x,v=y,dif=d;} void _add(int x, int y) {v=y,next=head[x],head[x]=tot;} bool operator < (Edge e1) const {return dif<e1.dif;} }e[M],E[M]; struct HJTtree //主席树（黄嘉泰=Hu Jintao） { private: int lc[N<<5],rc[N<<5],sum[N<<5]; public: void build(int &rt, int l, int r) { rt=++cnt; if(l==r)return; int mid=(l+r)>>1; build(lc[rt],l,mid); build(rc[rt],mid+1,r); } void modify(int pre, int &rt, int l, int r, int x) { rt=++cnt; lc[rt]=lc[pre],rc[rt]=rc[pre],sum[rt]=sum[pre]+1; if(l==r)return; int mid=(l+r)>>1; if(x<=mid)modify(lc[pre],lc[rt],l,mid,x); else modify(rc[pre],rc[rt],mid+1,r,x); } int query(int x, int y, int l, int r, int k) { if(l==r)return l; int mid=(l+r)>>1,d=sum[rc[y]]-sum[rc[x]]; if(k<=d)return query(rc[x],rc[y],mid+1,r,k); else return query(lc[x],lc[y],l,mid,k-d); } }t; void dfs(int x) { for(int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; range[x][0]=num; //对应区间的左端点（左开右闭） if(!head[x]) { int kkk=lower_bound(b+1,b+size+1,h[x])-b; range[x][0]=++num; t.modify(Rt[num-1],Rt[num],1,size,kkk); return; } for(int i=head[x],flag=0;i;i=E[i].next) dfs(E[i].v); range[x][1]=num; } int Find(int x) {return f[x]==x?x:f[x]=Find(f[x]);} void kruskal() { sort(e+1,e+m+1); for(int i=1;i<=n;i++)f[i]=i; int temp=n; for(int i=1;i<=m;i++) { int u=Find(e[i].u),v=Find(e[i].v); if(u==v)continue; diff[++temp]=e[i].dif; f[u]=f[v]=f[temp]=temp; E[++tot]._add(temp,u),E[++tot]._add(temp,v); fa[u][0]=fa[v][0]=temp; } t.build(Rt[0],1,size); dfs(temp); } int main() { Read(n),Read(m),Read(q); for(int i=1;i<=n;i++) Read(h[i]),b[i]=h[i]; sort(b+1,b+n+1); size=unique(b+1,b+n+1)-b-1; //离散化 for(int i=1,x,y,d;i<=m;i++) { Read(x),Read(y),Read(d); e[i].add(x,y,d); } kruskal(); while(q--) { int x,d,k; Read(x),Read(d),Read(k); for(int i=20;i>=0;i--) if(fa[x][i]&&diff[fa[x][i]]<=d)x=fa[x][i]; //找到深度最小且点权不大于k的祖先 if(sum[Rt[range[x][1]]]-sum[Rt[range[x][0]]]<k) {puts("-1");continue;} //如果查询的k大于该区间高度值个数，无解 //如果这里写range[x][1]-range[x][0]也是一样的 printf("%d\n",b[t.query(Rt[range[x][0]],Rt[range[x][1]],1,size,k)]); } return 0; } ```