第一反应:树剖之后树套树维护……
估计是 O(nlog4n) 的(
然而并不是在线的,并且只有一次询问。
如果按上述做法需要把一条路径在两个维度都用树剖划分为几个区间,
但是其中一个维度可以换成树上差分,于是第二个维度变成线段树合并。
线段树使用类似扫描线的写法,避免重复统计。
注意要添加 n 个不存在的 (i,i) 操作,是为了方便计算答案。
否则不容易直接计算满足 u=v 的 (u,v) 点对的个数。
此做法是 O(nlog2n) 的,我太弱了不会一个 log 的。
代码:
1 |
|
第一反应:树剖之后树套树维护……
估计是 O(nlog4n) 的(
然而并不是在线的,并且只有一次询问。
如果按上述做法需要把一条路径在两个维度都用树剖划分为几个区间,
但是其中一个维度可以换成树上差分,于是第二个维度变成线段树合并。
线段树使用类似扫描线的写法,避免重复统计。
注意要添加 n 个不存在的 (i,i) 操作,是为了方便计算答案。
否则不容易直接计算满足 u=v 的 (u,v) 点对的个数。
此做法是 O(nlog2n) 的,我太弱了不会一个 log 的。
代码:
1 | #include <cstdio> |
Related Issues not found
Please contact @Alpha1022 to initialize the comment