当前位置: 代码迷 >> 综合 >> bzoj 3551: [ONTAK2010]Peaks加强版
  详细解决方案

bzoj 3551: [ONTAK2010]Peaks加强版

热度:71   发布时间:2023-10-29 07:52:35.0

题意

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

题解

如果离线的话很好做,按x排个序,线段树合并就可以了
但是在线就不可以了。。
一开始想到,如果我们建立最小生成树,显然,树边肯定保证连通的时候是最短的。然后用倍增跳到能跳的最上边的父亲。问题就变成了问一个子树里面,只走边权不超过x的边,能走到的第k高。。想了半天。。发现我不会做
于是就去膜题解了、
见到一个没见过的东西:

Kruskal重构树
这里我们Kruskal连边时并不直接连边 而是新建一个节点ext 将两个点所在子树都连到ext的儿子上
这样生成的树有一些十分优美的性质:
1.二叉树(好吧这题意义不大)
2.原树与新树两点间路径上边权(点权)的最大值相等
3.子节点的边权小于等于父亲节点(大根堆)
4.原树中两点之间路径上边权的最大值等于新树上两点的LCA的点权

然后就可以主席树乱搞一波了
感觉很妙啊
CODE:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=100005*2;
int n,m,q;
struct qq{int x,y,z,last;}E[N*5],e[N*10];
int num,last[N];
int A[N];
int val[N];
bool cmp (qq x,qq y){
   return x.z<y.z;}
int f[N];
int tot;
int find (int x){
   return f[x]==x?f[x]:f[x]=find(f[x]);}
void init (int x,int y)
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
int L[N],R[N],now=0;
int belong[N];
int fa[N][21];
void dfs (int x)
{if (x<=n){R[x]=L[x]=++now;belong[now]=x;}else L[x]=now+1;for (int u=1;u<=20;u++) fa[x][u]=fa[fa[x][u-1]][u-1];for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;fa[y][0]=x;dfs(y);}R[x]=now;
}
int s1[N*10],s2[N*10],t[N*10];
void change (int &rt1,int rt2,int l,int r,int x)
{rt1=++num;t[rt1]=t[rt2]+1;if (l==r) return ;int mid=(l+r)>>1;if (x<=mid) change(s1[rt1],s1[rt2],l,mid,x),s2[rt1]=s2[rt2];else change(s2[rt1],s2[rt2],mid+1,r,x),s1[rt1]=s1[rt2];
}
int get (int x,int v)
{for (int u=20;u>=0;u--)if (fa[x][u]!=0&&val[fa[x][u]]<=v) x=fa[x][u];return x;
}
int find (int rt1,int rt2,int l,int r,int x)
{if (t[rt1]-t[rt2]<x) return -1;if (l==r) return l;int mid=(l+r)>>1;if (t[s2[rt1]]-t[s2[rt2]]>=x) return find(s2[rt1],s2[rt2],mid+1,r,x);else return find(s1[rt1],s1[rt2],l,mid,x-(t[s2[rt1]]-t[s2[rt2]]));
}
int root[N];
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d%d%d",&n,&m,&q);for (int u=1;u<=n;u++) f[u]=u;for (int u=1;u<=n;u++) scanf("%d",&val[u]),A[u]=val[u];sort(A+1,A+1+n);int A_tot=unique(A+1,A+1+n)-A-1;for (int u=1;u<=n;u++) val[u]=lower_bound(A+1,A+1+A_tot,val[u])-A;for (int u=1;u<=m;u++)  scanf("%d%d%d",&E[u].x,&E[u].y,&E[u].z);sort(E+1,E+1+m,cmp);tot=n;for (int u=1;u<=m;u++){int x=find(E[u].x),y=find(E[u].y);if (x==y) continue;tot++;val[tot]=E[u].z;init(tot,x);init(tot,y);f[tot]=f[x]=f[y]=tot;}/*for (int u=1;u<=num;u++) {printf("%d %d\n",e[u].x,e[u].y);system("pause");}*/
/*  for (int u=1;u<=tot;u++) {printf("%d\n",val[u]);system("pause");}*/dfs(tot);num=0;for (int u=1;u<=now;u++)change(root[u],root[u-1],1,n,val[belong[u]]);int ans=-1;while (q--){int x,v,k;scanf("%d%d%d",&x,&v,&k);if (ans>-1) {
   x^=ans;v^=ans;k^=ans;}int p=get(x,v);ans=find(root[R[p]],root[L[p]-1],1,n,k);if (ans>-1) ans=A[ans];printf("%d\n",ans);}return 0;
}