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)\) 。