【bzoj3545/bzoj3551】[ONTAK2010]Peaks/加强版 Kruskal+树上倍增+Dfs序+主席树

时间:2022-06-04 23:47:17

bzoj3545

题目描述

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

输入

第一行三个数N,M,Q。
第二行N个数,第i个数为h_i
接下来M行,每行3个数a b c,表示从a到b有一条困难值为c的双向路径。
接下来Q行,每行三个数v x k,表示一组询问。

输出

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

样例输入

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

样例输出

6
1
-1
8

bzoj3551

输入

接下来Q行,每行三个数v x k,表示一组询问。v=v xor lastans,x=x xor lastans,k=k xor lastans。如果lastans=-1则不变。


题解

Kruskal+倍增算法+dfs序+主席树

p3445允许离线,所以还可以用Treap启发式合并。

然而p3451强制在线,这样做肯定不行。

首先肯定是先Kruskal求最小生成树,而一般的最小生成树也无法表示任意两点间距离最大值。

这里用到一个黑科技:Kruskal重构树。

在求最小生成树时,不直接连接两个节点,而是将两个节点的祖先连接到一个新的节点上。

这个新的节点与这两个节点之间的边权就是边的长度。

这有什么好处?

【bzoj3545/bzoj3551】[ONTAK2010]Peaks/加强版  Kruskal+树上倍增+Dfs序+主席树

上图是按照这种方式重构的一棵树,其中节点1~10为原节点,11~19为新加节点。

可以看出,从下至上的路径,边权是单调不减的(看作点权即大根堆)。

那么,想要寻找路径小于等于x的所有能到达的点,就可以从最下方的原节点向上查找最远的路径小于x的点,这个点的子树就是所求的点集合。

题目要求这个点集合里第k大的,需要使这些点连续出现,于是想到Dfs序。

我们可以构建一个Dfs序,然后使用主席树来维护并查询第k大。

需要注意的是这两道题都需要读入优化,否则会TLE。

以下为p3545的代码,若为p3551,只需要在询问时修改一小部分即可。

#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
int x , y , z;
}e[500005];
struct data
{
int num , rank;
}a[200005];
int f[200005] , log[200005] , fa[200005][18] , dis[200005][18] , deep[200005];
int head[200005] , to[200005] , val[200005] , next[200005] , cnt;
int lp[200005] , rp[200005] , pl , q[400005] , ref[200005] , top;
int ls[6000005] , rs[6000005] , si[6000005] , root[400005] , tot;
inline int read()
{
int num = 0; char ch;
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') num = num * 10 + ch - '0' , ch = getchar();
return num;
}
bool cmp1(data a , data b)
{
return a.num < b.num;
}
bool cmp2(data a , data b)
{
return a.rank < b.rank;
}
bool cmp3(node a , node b)
{
return a.z < b.z;
}
int find(int x)
{
return x == f[x] ? x : f[x] = find(f[x]);
}
void add(int x , int y , int z)
{
to[++cnt] = y;
val[cnt] = z;
next[cnt] = head[x];
head[x] = cnt;
}
void dfs(int x)
{
int i;
lp[x] = ++pl;
q[pl] = a[x].num;
for(i = head[x] ; i ; i = next[i])
{
if(to[i] != fa[x][0])
{
fa[to[i]][0] = x;
deep[to[i]] = deep[x] + 1;
dfs(to[i]);
}
}
rp[x] = ++pl;
}
void init(int n)
{
int i , j;
for(i = 2 ; i <= n ; i ++ )
log[i] = log[i >> 1] + 1;
for(i = 1 ; i <= log[n] ; i ++ )
for(j = 1 ; j <= n ; j ++ )
if(deep[j] >= (1 << i))
fa[j][i] = fa[fa[j][i - 1]][i - 1] , dis[j][i] = max(dis[j][i - 1] , dis[fa[j][i - 1]][i - 1]);
}
void pushup(int x)
{
si[x] = si[ls[x]] + si[rs[x]];
}
void ins(int x , int &y , int l , int r , int p)
{
y = ++tot;
if(l == r)
{
si[y] = si[x] + 1;
return;
}
int mid = (l + r) >> 1;
if(p <= mid) rs[y] = rs[x] , ins(ls[x] , ls[y] , l , mid , p);
else ls[y] = ls[x] , ins(rs[x] , rs[y] , mid + 1 , r , p);
pushup(y);
}
int query(int x , int y , int l , int r , int p)
{
if(l == r) return ref[l];
int mid = (l + r) >> 1;
if(si[ls[y]] - si[ls[x]] >= p) return query(ls[x] , ls[y] , l , mid , p);
else return query(rs[x] , rs[y] , mid + 1 , r , p - si[ls[y]] + si[ls[x]]);
}
int main()
{
int n , m , qu , i , tx , ty , v , x , k;
n = read() , m = read() , qu = read();
for(i = 1 ; i <= n ; i ++ )
a[i].num= read() , a[i].rank = i;
sort(a + 1 , a + n + 1 , cmp1);
ref[0] = 0x8000000;
for(i = 1 ; i <= n ; i ++ )
{
if(a[i].num != ref[top]) ref[++top] = a[i].num;
a[i].num = top;
}
sort(a + 1 , a + n + 1 , cmp2);
for(i = 1 ; i <= n << 1 ; i ++ )
f[i] = i;
for(i = 1 ; i <= m ; i ++ )
e[i].x = read() , e[i].y = read() , e[i].z = read();
sort(e + 1 , e + m + 1 , cmp3);
for(i = 1 ; i <= m ; i ++ )
{
tx = find(e[i].x) , ty = find(e[i].y);
if(tx != ty)
{
f[tx] = f[ty] = ++n;
fa[tx][0] = fa[ty][0] = n;
dis[tx][0] = dis[ty][0] = e[i].z;
add(n , tx , e[i].z);
add(n , ty , e[i].z);
}
}
dfs(n);
init(n);
for(i = 1 ; i <= pl ; i ++ )
{
if(!q[i]) root[i] = root[i - 1];
else ins(root[i - 1] , root[i] , 1 , top , q[i]);
}
while(qu -- )
{
v = read() , x = read() , k = read();
tx = v;
for(i = log[deep[v]] + 1 ; i >= 0 ; i -- )
if(deep[tx] >= (1 << i) && dis[tx][i] <= x)
tx = fa[tx][i];
printf("%d\n" , si[root[rp[tx]]] - si[root[lp[tx]]] >= k ? query(root[lp[tx]] , root[rp[tx]] , 1 , top , si[root[rp[tx]]] - si[root[lp[tx]]] - k + 1) : -1);
}
return 0;
}

【bzoj3545/bzoj3551】[ONTAK2010]Peaks/加强版 Kruskal+树上倍增+Dfs序+主席树的更多相关文章

  1. BZOJ 3551&colon; &lbrack;ONTAK2010&rsqb;Peaks加强版 &lbrack;Kruskal重构树 dfs序 主席树&rsqb;

    3551: [ONTAK2010]Peaks加强版 题意:带权图,多组询问与一个点通过边权\(\le lim\)的边连通的点中点权k大值,强制在线 PoPoQQQ大爷题解传送门 说一下感受: 容易发现 ...

  2. BZOJ 3551&colon; &lbrack;ONTAK2010&rsqb;Peaks加强版 Kruskal重构树&plus;dfs序&plus;主席树&plus;倍增

    建出来 $Kruskal$ 重构树. 将询问点向上跳到深度最小,且合法的节点上. 那么,得益于重构树优美的性质,这个最终跳到的点为根的所有子节点都可以与询问点互达. 对于子树中求点权第 $k$ 大的问 ...

  3. &lbrack;BZOJ3551&rsqb;&lbrack;ONTAK2010&rsqb;Peaks&lpar;加强版&rpar;&lpar;Kruskal重构树&comma;主席树&rpar;

    3551: [ONTAK2010]Peaks加强版 Time Limit: 20 Sec  Memory Limit: 128 MBSubmit: 2438  Solved: 763[Submit][ ...

  4. BZOJ3551 ONTAK2010Peaks加强版(kruskal重构树&plus;dfs序&plus;主席树)

    kruskal重构树本质就是给并查集显式建树来替代可持久化并查集.将边按困难度从小到大排序后建出该树,按dfs序建主席树即可.查询时跳到深度最浅的满足在该重要度下已被合并的点,在子树内查询第k大. # ...

  5. &lbrack;bzoj3306&rsqb;树——树上倍增&plus;dfs序&plus;线段树

    Brief Description 您需要写一种数据结构,支持: 更改一个点的点权 求一个子树的最小点权 换根 Algorithm Design 我们先忽略第三个要求. 看到要求子树的最小点权,我们想 ...

  6. BZOJ3551 &lbrack;ONTAK2010&rsqb;Peaks加强版 kruskal 并查集 主席树 dfs序

    欢迎访问~原文出处——博客园-zhouzhendong 去博客园看该题解 题目传送门 - BZOJ3551 题意概括 Description 在Bytemountains有N座山峰,每座山峰有他的高度 ...

  7. 2018&period;09&period;30 bzoj3551&colon;Peaks加强版(dfs序&plus;主席树&plus;倍增&plus;kruskal重构树)

    传送门 一道考察比较全面的题. 这道题又用到了熟悉的kruskal+倍增来查找询问区间的方法. 查到询问的子树之后就可以用dfs序+主席树统计答案了. 代码: #include<bits/std ...

  8. BZOJ&period;3551&period;&lbrack;ONTAK2010&rsqb;Peaks加强版&lpar;Kruskal重构树 主席树&rpar;

    题目链接 \(Description\) 有n个座山,其高度为hi.有m条带权双向边连接某些山.多次询问,每次询问从v出发 只经过边权<=x的边 所能到达的山中,第K高的是多少. 强制在线. \ ...

  9. 【BZOJ3545&amp&semi;BZOJ3551】Peaks(kruskal重构树,主席树,dfs序)

    题意:在Bytemountains有N座山峰,每座山峰有他的高度h_i. 有些山峰之间有双向道路相连,共M条路径,每条路径有一个困难值,这个值越大表示越难走, 现在有Q组询问,每组询问询问从点v开始只 ...

随机推荐

  1. Vue 入门指南

    英文:http://vuejs.org/guide/index.html 介绍 vue.js 是用来构建web应用接口的一个库 技术上,Vue.js 重点集中在MVVM模式的ViewModel层,它连 ...

  2. BootStrap学习(2)

    使用Bootstrap添加代码框 可先看:简介.引入.包下载等:http://www.cnblogs.com/0201zcr/p/4900062.html Bootstrap 允许您以两种方式显示代码 ...

  3. 查看django里所有的url

    >>> from django.core.urlresolvers import get_resolver >>> get_resolver(None).rever ...

  4. jQuery&lowbar;效果&lpar;淡入淡出&rpar;

    1.jQuery fadeIn() 方法( 用于淡入已隐藏的元素.) 语法: $(selector).fadeIn(speed,callback); 可选的 speed 参数规定效果的时长.它可以取以 ...

  5. 【二分查找最优解】FZU 2056 最大正方形

    题意:现在有一个n*m的矩阵A,在A中找一个H*H的正方形,使得其面积最大且该正方形元素的和不大于 limit. 分析:开始以为是DP或者二维RMQ,其实用二分就可以做出来: 在输入时构造元素和矩阵d ...

  6. &lbrack;Webpack 2&rsqb; Import a non-ES6 module with Webpack

    When you have a dependency that does not export itself properly, you can use the exports-loader to f ...

  7. Python 实现网络爬虫小程序

    Python很简洁,也很强大,作为兴趣,值得一学!   下面这个程序实现的是从一个网站上下载图片,根据自己需要可以进行修改 import re import urllib def gethtml(ur ...

  8. Android4&period;0 以后不允许在主线程进行网络连接

    Android4.0 以后不允许在主线程进行网络连接,否则会出现 android.os.NetworkOnMainThreadException.因此,必须另起一个线程进行网络连接方面的操作. pac ...

  9. iOS&lowbar;SN&lowbar;百度地图基本使用(1)

    上次用了一次百度地图,一直没有记笔记,今天记一笔. 以前没有用过百度地图的时候,听做这方面的朋友说百度地图有不少的坑,但是我做的时候没有遇到太大的坑,主要是要注意官方文档的注意事项,还有配置环境开发中 ...

  10. BZOJ1116&colon; &lbrack;POI2008&rsqb;CLO

    1116: [POI2008]CLO Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 565  Solved: 303[Submit][Status] ...