【BZOJ-3545&3551】Peaks&加强版 Kruskal重构树 + 主席树 + DFS序 + 倍增

3545: [ONTAK2010]Peaks

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1202  Solved: 321
[Submit][Status][Discuss]

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,表示一组询问。

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

HINT

【数据范围】

N<=10^5, M,Q<=5*10^5,h_i,c,x<=10^9。

Source

By Sbullet

3551: [ONTAK2010]Peaks加强版

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 810  Solved: 275
[Submit][Status][Discuss]

第一行三个数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则不变。

Solution

先是非加强版,不强制在线,可以考虑离线,进行排序然后平衡树启发式合并搞搞就可以。

加强版要异或lastans,很显然不能上述做法,按照出题人的做法去搞:

首先我们发现,对结果有贡献的边,即最小生成树上的边,其余的边都是无用的,所以不妨先Kruskal建出最小生成树

但是这里的Kruskal与以往有不同,以往是直接连边,而这里需要 用到另一种方式 即 Kruskal重构树

具体方法很简单,以前是按边排序,用并查集维护联通性,每次连最小的边,这里思路类似,但是不是直接连边,而是构造一个新的节点,向这个边的两个端点连边,点权为这条边的边权(注意这里是单向边)

这里的Kruskal重构树有一些有用的性质:

1.二叉树(好吧这题意义不大)

2.原树与新树两点间路径上边权(点权)的最大值相等

3.子节点的边权小于等于父亲节点(大根堆)

4.原树中两点之间路径上边权的最大值等于新树上两点的LCA的点权

对于维护路径上的最值,就可以考虑倍增,倍增出来之后,建棵主席树,每次询问区间第K即可

PS.Claris好像有种方法,利用线段树合并来做,具体的并不会 ,但大体上会个板子

int merge(int x,int y,int a,int b)
{
if (!x) return y;
if (!y) return x;
int z=++tot;
if (a==b)
v[z]=v[x]+v[y],return z;
int mid=(a+b)>>;
l[z]=merge(l[x],l[y],a,mid);
r[z]=merge(r[x],r[y],mid+,b);
v[z]=v[l[z]]+v[r[z]];
return z;
}

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-')f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define maxn 100100
#define maxm 500100
int n,m,q; int hh[maxn],ls[maxn]; int steck[maxn<<],top;
struct data{
int from,to,hard;
bool operator < (const data& A) const
{return hard<A.hard;}
}road[maxm];
struct dat{int next,to;}edge[maxn<<];int head[maxn<<],cnt;
void add(int u,int v){cnt++;edge[cnt].next=head[u];head[u]=cnt;edge[cnt].to=v;}
int fa[maxn<<],va[maxn<<];
void init(){for (int i=; i<=n*; i++) fa[i]=i;}
int find(int x) {if (x==fa[x]) return x; return fa[x]=find(fa[x]);}
void Kruskal()
{
init(); int zz=n;
sort(road+,road+m+);
for (int i=; i<=m; i++)
{ int u=road[i].from,v=road[i].to,w=road[i].hard;
int fa1=find(u),fa2=find(v);
if (fa1!=fa2)
{
zz++; fa[fa1]=fa[fa2]=zz; va[zz]=w;
add(zz,fa2);add(zz,fa1);
if (zz==*n-) break;
}
}
}
bool visit[maxn<<];int father[maxn<<][],maxx[maxn<<][],deep[maxn<<];
void dfs(int x)
{
visit[x]=; steck[++top]=x;
for (int i=; i<; i++)
if (deep[x]>=(<<i))
father[x][i]=father[father[x][i-]][i-],
maxx[x][i]=max(maxx[x][i-],maxx[father[x][i-]][i-]);
else break;
for (int i=head[x]; i; i=edge[i].next)
{
deep[edge[i].to]=deep[x]+;
maxx[edge[i].to][]=va[x];
father[edge[i].to][]=x;
dfs(edge[i].to);
}
if (x>n) steck[++top]=x;
}
int sum[maxn*],ll[maxn*],rr[maxn*],root[maxn<<],sz;
void insert(int l,int r,int &now,int fat,int val)
{
now=++sz; sum[now]=sum[fat]+;
if (l==r) return;
ll[now]=ll[fat],rr[now]=rr[fat];
int mid=(l+r)>>;
if (val<=mid) insert(l,mid,ll[now],ll[fat],val);
else insert(mid+,r,rr[now],rr[fat],val);
}
int query(int l,int r,int L,int R,int kth)
{
if (l==r) return l;
int mid=(l+r)>>;
if (sum[ll[R]]-sum[ll[L]]>=kth) return query(l,mid,ll[L],ll[R],kth);
else return query(mid+,r,rr[L],rr[R],kth-sum[ll[R]]+sum[ll[L]]);
}
int st[maxn<<],ed[maxn<<];
void prework()
{
for (int i=; i<=n; i++)
if (!visit[i]) dfs(find(i));
for (int i=; i<=top; i++)
{
int tmp=steck[i];
if (tmp<=n) insert(,n,root[i],root[i-],hh[tmp]);
else
{
root[i]=root[i-];
if (!st[tmp]) st[tmp]=i; else ed[tmp]=i;
}
}
}
int search(int x,int val)
{
for(int i=;i>=;i--)
if(deep[x]>=(<<i) && maxx[x][i]<=val) x=father[x][i];
return x;
}
int main()
{
n=read(),m=read(),q=read();
for (int i=; i<=n; i++) hh[i]=read(),ls[i]=hh[i];
sort(ls+,ls+n+);
for (int i=; i<=n; i++)
hh[i]=lower_bound(ls+,ls+n+,hh[i])-ls;
for (int i=; i<=m; i++)
road[i].from=read(),road[i].to=read(),road[i].hard=read();
Kruskal();
prework();
int lastans=-,ans;
for (int i=; i<=q; i++)
{
int v=read(),x=read(),k=read();
if (lastans!=-) v^=lastans,x^=lastans,k^=lastans;
int tmp=search(v,x);
int a=root[st[tmp]],b=root[ed[tmp]];
if (sum[b]-sum[a]<k) ans=-;
else ans=ls[query(,n,a,b,sum[b]-sum[a]-k+)];
printf("%d\n",ans); lastans=ans;
}
return ;
}

开始RE,后来MLE,后来WA,如此这般...简直不要太坑...外加本机Gena测全WA,提交AC....背水淹没

上一篇:洛谷P3402 【模板】可持久化并查集 [主席树,并查集]


下一篇:Codeforces 789D Weird journey - 欧拉路 - 图论