Task1 N<=1000
\(O(n^2)\) 算法随便乱搞.
源代码 https://www.luogu.com.cn/record/28868263
Task2 N<= 1e5 且为链
考虑新加入一个节点后, 因为是链, 所以每个节点到新加入的节点的距离的增量是相同的.
观察一下两个小精灵能够成为好朋友的条件:
\[ dist(i,j)\le r_i + r_j \]
移个项:
\[ dist(i,j) - r_j \le r_j \]
于是可以用平衡树维护每个点的 \(dist(i,j)-r_j\), 然后直接查询即可.
算法复杂度 \(O(N\log N)\).
源代码 https://www.luogu.com.cn/record/28868384
Task3 N<= 1e5
\(r \le 10\), 这意味着什么? 这意味着新加入一个节点之后, 最多只需要搜索到深度为 20 就够了, 但是 \(1s\) 后我就发现了问题, 这不是直接就被菊花图卡成 \(n\) 方了吗?
让我们再次考虑一下上面的柿子:
\[ dist(i,j)\le r_i + r_j \]
设 \(dis_i\) 表示以 \(1\) 为根, 从 \(1\) 到节点 \(i\) 的距离, 那么:
考虑新加入一个节点 \(x\) 后, 那么只需分两种情况讨论:
与 \(x\) 在同一条链上的节点
- \(dis_x - dis_i\le r_x + r_i\)
- \(dis_x - r_x \le r_i + dis_i\)
与 \(x\) 不在同一条链上的节点
- \(dis_x + dis_i\le r_x + r_i\)
- \(dis_x - r_x \le r_i - dis_i\)
现在的问题就在于怎么处理是否与 \(x\) 在同一条链上的情况. 每条链建一棵平衡树.
这就触及到我的知识盲区了.
但是我 \(jio\) 得暴力搞的话, 可以过掉一些随机生成树的点.
好的, 到这里, 预计得分是 \(50pts\) 上下.
但是这个部分分我不想写了...
正解
前置芝士:
动态点分治 (由于我太蒟了不会, 所以就先去学了)
平衡树
Update 2020.1.1 一年后 (大雾
[WC2014] 紫荆花之恋 - 动态点分治 + 平衡树
来源: http://www.bubuko.com/infodetail-3361074.html