这个题的 std 用了 cdq 分治,但是 cdq 分治有一个问题,就是它会在取等的时候出锅。也就是说 [l,mid] 中有可能有数会偏序 [mid+1,r]([mid+1,r] 里的数对 [l,mid] 有贡献)。这也是为什么模板题要去重的原因。但是这道题比较好的一点是,不会出现这个问题。如果 r 和 b 都相等时,直接按 dfs 序从大到小排序即可(对于两个 dfs 序 x,y,若 x>y,则 y 的点包含 x 的点)。这样 [l,mid] 中的节点的要么 b 比 [mid+1,r] 的节点小,要么 dfs 序比 [mid+1,r] 中的大。这样一定不会统计错答案。
这样的思路我觉得是对的,可能 std 也是这样的思路避免等号,但是 std 最后一维竟然是按照结束时间(即文中的 sti+sizi−1)从小到大排序的。因为 dfs 序的时间和结束时间恰好相反,则这样看起来是没问题的。但是这个结束时间有可能相等!我猜可能 std 少在结束的地方 ++cnt 了。这里我有一个 hack 数据:
2
1 2
1 1
1 1
正解输出:
1
而 std 将 1 号节点放在了 2 号节点的前面,所以无输出。
综上,我觉得 std 的大体思路没啥问题,而且避开等号的方法挺妙的,但是这个细节写挂了。希望可以修改一下 std 并添加这个数据。