首页 > 代码库 > bzoj3551 [ONTAK2010]Peaks加强版
bzoj3551 [ONTAK2010]Peaks加强版
Description
//【题目描述】同3545
在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 xor lastans，x=x xor lastans，k=k xor lastans。如果lastans=-1则不变。
Output
//同3545
对于每组询问，输出一个整数表示答案。
Sample Input
Sample Output
HINT
//【数据范围】同3545
N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。
正解：$kruskal$重构树+主席树。
这题的普通版是权限题。。
有一个神奇的东西，叫做$kruskal$重构树。
我们在做最小生成树的时候，并不是直接把两个联通块的根连起来，而是对于两个联通块，新建一个点，连向这两个联通块的根结点，而这个新建点的点权就是这条边的边权。
注意到这样做生成的树有一些性质：
1.这是一棵二叉树。
2.原树点都是叶子结点。
3.子结点比父结点点权小(大根堆)。
4.原树与新树两点间路径最大值与新树相等，且等于新树两点$lca$点权。
然后我们发现，对于任意一个$v$，我们向上找到深度最小的满足点权$<=x$的点，然后查询整个子树的第$k$大，就是答案了。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue> 10 #include <stack> 11 #include <map> 12 #include <set> 13 #define inf (1<<30) 14 #define N (200010) 15 #define il inline 16 #define RG register 17 #define ll long long 18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 19 20 using namespace std; 21 22 struct edge{ int nt,to; }G[N<<1]; 23 struct E{ int u,v,w; }g[N<<2]; 24 25 int head[N],top[N],fa[N],son[N],dep[N],pos[N],dfn[N],ed[N],sz[N],hsh[N],h[N],d[N]; 26 int sum[20*N],ls[20*N],rs[20*N],rt[N],Sz,n,m,Q,RT,num,cnt,tot,ans; 27 28 il int gi(){ 29 RG int x=0,q=1; RG char ch=getchar(); 30 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 31 if (ch==‘-‘) q=-1,ch=getchar(); 32 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); 33 return q*x; 34 } 35 36 il void insert(RG int from,RG int to){ 37 G[++num]=(edge){head[from],to},head[from]=num; return; 38 } 39 40 il int cmp(const E &a,const E &b){ return a.w<b.w; } 41 42 il int find(RG int x){ return (!fa[x] || fa[x]==x) ? x : fa[x]=find(fa[x]); } 43 44 il void dfs1(RG int x,RG int p){ 45 fa[x]=p,dep[x]=dep[p]+1,sz[x]=1; RG int v; 46 for (RG int i=head[x];i;i=G[i].nt){ 47 v=G[i].to; if (v==p) continue; 48 dfs1(v,x),sz[x]+=sz[v]; 49 if (sz[son[x]]<=sz[v]) son[x]=v; 50 } 51 return; 52 } 53 54 il void dfs2(RG int x,RG int p,RG int anc){ 55 top[x]=anc,dfn[x]=++cnt,pos[cnt]=x; 56 if (son[x]) dfs2(son[x],x,anc); RG int v; 57 for (RG int i=head[x];i;i=G[i].nt){ 58 v=G[i].to; if (v==p || v==son[x]) continue; 59 dfs2(v,x,v); 60 } 61 ed[x]=cnt; return; 62 } 63 64 il int lca(RG int x,RG int k){ 65 RG int la=x; while (x && d[top[x]]<=k) la=top[x],x=fa[top[x]]; 66 if (d[x]>k || d[top[x]]<=k) return la; 67 RG int l=dfn[top[x]],r=dfn[x],mid,res; 68 while (l<=r){ 69 mid=(l+r)>>1; 70 if (d[pos[mid]]<=k) res=pos[mid],r=mid-1; else l=mid+1; 71 } 72 return res; 73 } 74 75 il void add(RG int x,RG int &y,RG int l,RG int r,RG int v){ 76 sum[y=++Sz]=sum[x]+1,ls[y]=ls[x],rs[y]=rs[x]; 77 if (l==r) return; RG int mid=(l+r)>>1; 78 v<=mid?add(ls[x],ls[y],l,mid,v):add(rs[x],rs[y],mid+1,r,v); return; 79 } 80 81 il int query(RG int x,RG int y,RG int l,RG int r,RG int k){ 82 if (l==r) return hsh[l]; RG int mid=(l+r)>>1,tmp=sum[rs[y]]-sum[rs[x]]; 83 return k<=tmp?query(rs[x],rs[y],mid+1,r,k):query(ls[x],ls[y],l,mid,k-tmp); 84 } 85 86 il void work(){ 87 n=gi(),m=gi(),Q=gi(); 88 for (RG int i=1;i<=n;++i) fa[i]=i,h[i]=gi(),hsh[++tot]=h[i]; 89 sort(hsh+1,hsh+tot+1),tot=unique(hsh+1,hsh+tot+1)-hsh-1; 90 for (RG int i=1;i<=n;++i) h[i]=lower_bound(hsh+1,hsh+tot+1,h[i])-hsh; 91 for (RG int i=1;i<=m;++i) g[i].u=gi(),g[i].v=gi(),g[i].w=gi(); 92 sort(g+1,g+m+1,cmp),cnt=n; 93 for (RG int i=1,k=0,x,y;i<=m;++i){ 94 x=find(g[i].u),y=find(g[i].v); if (x==y) continue; 95 fa[x]=fa[y]=++cnt,insert(cnt,x),insert(cnt,y); 96 d[cnt]=g[i].w,RT=cnt,++k; if (k==n-1) break; 97 } 98 cnt=0,dfs1(RT,0),dfs2(RT,0,RT); 99 for (RG int i=1;i<=cnt;++i)100 if (pos[i]>n) rt[i]=rt[i-1];101 else add(rt[i-1],rt[i],1,tot,h[pos[i]]);102 for (RG int i=1,v,x,k,Lca;i<=Q;++i){103 v=gi()^ans,x=gi()^ans,k=gi()^ans,Lca=lca(v,x);104 if (sum[rt[ed[Lca]]]-sum[rt[dfn[Lca]-1]]<k) ans=0,puts("-1");105 else ans=query(rt[dfn[Lca]-1],rt[ed[Lca]],1,tot,k),printf("%d\n",ans);106 }107 return;108 }109 110 int main(){111 File("peaks");112 work();113 return 0;114 }
bzoj3551 [ONTAK2010]Peaks加强版
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。