YZOJ P3392 越野赛车问题

YZOJ P3392 越野赛车问题

时间限制:1000MS      内存限制:262144KB

难度: \(6.0\)

  • 问题描述

某山上一共有 \(n\) 个广场,编号依次为 \(1\) 到 \(n\),这些广场之间通过 \(n-1\) 条双向车道直接或间接地连接在一起。对于每条车道 \(i\),可以用四个正整数 \(u_i, v_i, l_i, r_i\) 描述,表示车道连接广场 \(u_i\) 和 \(v_i\),其速度承受区间为 \([l_i, r_i]\),即汽车必须以不小于 \(l_i\) 且不大于 \(r_i\) 的速度经过车道 \(i\) 。

现计划进行 \(m\) 次训练,每次选择某山上的一条简单路径,然后在这条路径上行驶,且每次训练时的车速都是固定的。现在有在 m 次训练中分别计划使用的车速,要求一条合法的路径(车速在所有车道的速度承受区间的交集内),使得路径上经过的车道数最大

  • 数据输入

输入文件的第一行包含两个正整数 \(n, m\),表示广场数和训练次数。接下来 \(n-1\) 行,每行四个正整数 \(u_i, v_i, l_i, r_i ( \leq n)\),描述所有车道。最后 \(m\) 行,每行一个正整数 \(v (\leq n)\) ,表示每次训练是的车速。

  • 结果输出

输出 \(m\) 行,输出每次训练时的行驶路径经过的最大车道数。

  • 样例输入

  • 样例输出

  • 数据范围

数据点 \(n\) \(m\) 约定
1 \(=5\) \(5\)
2 \(=20\) \(20\)
3 \(=50000\) \(=50000\) \(l_i = 1, u_i = i, v_i = i +1\)
4 \(=70000\) \(=70000\)
5 \(=50000\) \(=50000\) \(u_i = i, v_i = i +1\)
6 \(=70000\) \(=70000\)
7 \(=50000\) \(=50000\) \(l_i = 1\)
8 \(=70000\) \(=70000\)
9 \(=50000\) \(=50000\)
10 \(=70000\) \(=70000\)

 

 

 


 

 

 

首先对于 \(n,m \leq 20\) 的数据,随便乱搜都能过。

然后是对于 \(l_i = 1\) 的数据,也就是说最小允许的速度都是 \(1\) ,只要考虑 \(r_i\) 造成的影响。

所以可以想到按照边的 \(r_i\) 降序排序,同时把询问离线也按照 \(v_i\) 降序排序,每次只需要把所有 \(r\) 比当前询问 \(v\) 大的边加入某个数据结构维护,然后更新答案即可。

由于这里维护的是连通性,所以很自然的想到并查集。但是要求的答案是最长链的长度,所以需要对并查集中的每一个连通子树维护其中最长链的两个端点,设为 \(\{x, y\}\) 。

合并两个并查集的时候,假设另一个并查集最长链的两个端点为 \(\{s, t\}\) ,那么合并后子树的最长链只有六种情况:\(\{x,y\}, \{s,t\}, \{x,s\}, \{x,t\}, \{y,s\}, \{y,t\}\) ,求两点距离的时候用树链剖分或倍增 lca 转换一下。

证明请见YJC同学的补充题解。

这样时间复杂度就是 lca \(+\) 并查集 \(+\) std::sort \(= O(nlogn)\) 。

 

对于所有的数据,\(l_i\) 不一定都为 \(1\) ,也就是说必须考虑 \(l_i\) 造成的影响。若此时还是按照之前的做法,那就需要带权并查集支持任意撤销一条边的连接,这是非常不现实的。

换一种思考方法,把区间 \([l_i, r_i]\) 看作时间区间,那么一条边将在 \(l_i\) 时刻出现,并在 \(r_i\) 时刻后消失,询问 \(v\) 就是询问 \(v\) 时刻的答案。

同时注意到 \(l_i, r_i, v_i \leq n \leq 70000\) ,所以想到线段树分治

线段树分治其实就是按照时间分治,因为分治的区间 \([l, mid], (mid, r]\) 极其类似于线段树分治的区间形式(几乎是一样的),所以可以用分治的方法遍历线段树,同时合并(利用)线段树上维护的信息进行答案的更新。

对于此题来说,对 \(v\) 进行分治,分治区间 \([l, r]\) 维护速度在 \([l, r]\) 范围时的合法的边。显然不能对每个这样的区间(总共不超过 \(4n\) 个)都存下所有的合法的边,这时候线段树的思想就派上用场了。

线段树查询的复杂度只有 \(logn\) ,因为若区间 \([l, r]\) 已经被询问区间完全包含,那么就不用继续往下寻找,直接利用这个区间点的信息更新答案即可。同理,线段树分治也是如此。若一条边在速度为区间 \([l, r]\) 的范围内已经合法,那么就不用对于 \([l, r]\) 内的其余所有子区间都添加这条边了,因为只有分治到 \([l, r]\) 时需要添加这条边的信息,之后分治进的子区间就再也不需要了。这样一条边就最多只会被 \(O(logn)\) 个区间所添加,时间和空间复杂度都是可以接受的。

现在还剩最后一个问题,分治时需要在返回之前撤销在这一层中并查集添加的边。发现只要简单的按栈序撤销即可,所以并查集不能有路径压缩,写一个按秩合并(启发式合并),还原时记得把 \(f\) 数组,\(size\) 或 \(rank\) ,维护的最长链的两个端点,所有连通子树中最长链最大长度(答案) 全部还原!

这样时间复杂度就是 lca \(+\) 并查集 \(+\) 线段树分治 \(= O(nlogn)\) 。

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注