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重构树。
在求最小生成树时,不直接连接两个节点,而是将两个节点的祖先连接到一个新的节点上。
这个新的节点与这两个节点之间的边权就是边的长度。
这有什么好处?
上图是按照这种方式重构的一棵树,其中节点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序+主席树的更多相关文章
-
BZOJ 3551: [ONTAK2010]Peaks加强版 [Kruskal重构树 dfs序 主席树]
3551: [ONTAK2010]Peaks加强版 题意:带权图,多组询问与一个点通过边权\(\le lim\)的边连通的点中点权k大值,强制在线 PoPoQQQ大爷题解传送门 说一下感受: 容易发现 ...
-
BZOJ 3551: [ONTAK2010]Peaks加强版 Kruskal重构树+dfs序+主席树+倍增
建出来 $Kruskal$ 重构树. 将询问点向上跳到深度最小,且合法的节点上. 那么,得益于重构树优美的性质,这个最终跳到的点为根的所有子节点都可以与询问点互达. 对于子树中求点权第 $k$ 大的问 ...
-
[BZOJ3551][ONTAK2010]Peaks(加强版)(Kruskal重构树,主席树)
3551: [ONTAK2010]Peaks加强版 Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 2438 Solved: 763[Submit][ ...
-
BZOJ3551 ONTAK2010Peaks加强版(kruskal重构树+dfs序+主席树)
kruskal重构树本质就是给并查集显式建树来替代可持久化并查集.将边按困难度从小到大排序后建出该树,按dfs序建主席树即可.查询时跳到深度最浅的满足在该重要度下已被合并的点,在子树内查询第k大. # ...
-
[bzoj3306]树——树上倍增+dfs序+线段树
Brief Description 您需要写一种数据结构,支持: 更改一个点的点权 求一个子树的最小点权 换根 Algorithm Design 我们先忽略第三个要求. 看到要求子树的最小点权,我们想 ...
-
BZOJ3551 [ONTAK2010]Peaks加强版 kruskal 并查集 主席树 dfs序
欢迎访问~原文出处——博客园-zhouzhendong 去博客园看该题解 题目传送门 - BZOJ3551 题意概括 Description 在Bytemountains有N座山峰,每座山峰有他的高度 ...
-
2018.09.30 bzoj3551:Peaks加强版(dfs序+主席树+倍增+kruskal重构树)
传送门 一道考察比较全面的题. 这道题又用到了熟悉的kruskal+倍增来查找询问区间的方法. 查到询问的子树之后就可以用dfs序+主席树统计答案了. 代码: #include<bits/std ...
-
BZOJ.3551.[ONTAK2010]Peaks加强版(Kruskal重构树 主席树)
题目链接 \(Description\) 有n个座山,其高度为hi.有m条带权双向边连接某些山.多次询问,每次询问从v出发 只经过边权<=x的边 所能到达的山中,第K高的是多少. 强制在线. \ ...
-
【BZOJ3545&;BZOJ3551】Peaks(kruskal重构树,主席树,dfs序)
题意:在Bytemountains有N座山峰,每座山峰有他的高度h_i. 有些山峰之间有双向道路相连,共M条路径,每条路径有一个困难值,这个值越大表示越难走, 现在有Q组询问,每组询问询问从点v开始只 ...
随机推荐
-
Vue 入门指南
英文:http://vuejs.org/guide/index.html 介绍 vue.js 是用来构建web应用接口的一个库 技术上,Vue.js 重点集中在MVVM模式的ViewModel层,它连 ...
-
BootStrap学习(2)
使用Bootstrap添加代码框 可先看:简介.引入.包下载等:http://www.cnblogs.com/0201zcr/p/4900062.html Bootstrap 允许您以两种方式显示代码 ...
-
查看django里所有的url
>>> from django.core.urlresolvers import get_resolver >>> get_resolver(None).rever ...
-
jQuery_效果(淡入淡出)
1.jQuery fadeIn() 方法( 用于淡入已隐藏的元素.) 语法: $(selector).fadeIn(speed,callback); 可选的 speed 参数规定效果的时长.它可以取以 ...
-
【二分查找最优解】FZU 2056 最大正方形
题意:现在有一个n*m的矩阵A,在A中找一个H*H的正方形,使得其面积最大且该正方形元素的和不大于 limit. 分析:开始以为是DP或者二维RMQ,其实用二分就可以做出来: 在输入时构造元素和矩阵d ...
-
[Webpack 2] 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 ...
-
Python 实现网络爬虫小程序
Python很简洁,也很强大,作为兴趣,值得一学! 下面这个程序实现的是从一个网站上下载图片,根据自己需要可以进行修改 import re import urllib def gethtml(ur ...
-
Android4.0 以后不允许在主线程进行网络连接
Android4.0 以后不允许在主线程进行网络连接,否则会出现 android.os.NetworkOnMainThreadException.因此,必须另起一个线程进行网络连接方面的操作. pac ...
-
iOS_SN_百度地图基本使用(1)
上次用了一次百度地图,一直没有记笔记,今天记一笔. 以前没有用过百度地图的时候,听做这方面的朋友说百度地图有不少的坑,但是我做的时候没有遇到太大的坑,主要是要注意官方文档的注意事项,还有配置环境开发中 ...
-
BZOJ1116: [POI2008]CLO
1116: [POI2008]CLO Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 565 Solved: 303[Submit][Status] ...