求问上午公开赛第三题的 std
  • 板块学术版
  • 楼主王熙文
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/10/5 21:57
  • 上次更新2023/10/27 08:36:19
查看原帖
求问上午公开赛第三题的 std
353688
王熙文楼主2022/10/5 21:57

这个题的 std 用了 cdq 分治,但是 cdq 分治有一个问题,就是它会在取等的时候出锅。也就是说 [l,mid][l,mid] 中有可能有数会偏序 [mid+1,r][mid+1,r][mid+1,r][mid+1,r] 里的数对 [l,mid][l,mid] 有贡献)。这也是为什么模板题要去重的原因。但是这道题比较好的一点是,不会出现这个问题。如果 rrbb 都相等时,直接按 dfs 序从大到小排序即可(对于两个 dfs 序 x,yx,y,若 x>yx>y,则 yy 的点包含 xx 的点)。这样 [l,mid][l,mid] 中的节点的要么 bb[mid+1,r][mid+1,r] 的节点小,要么 dfs 序比 [mid+1,r][mid+1,r] 中的大。这样一定不会统计错答案。

这样的思路我觉得是对的,可能 std 也是这样的思路避免等号,但是 std 最后一维竟然是按照结束时间(即文中的 sti+sizi1st_i+siz_i-1)从小到大排序的。因为 dfs 序的时间和结束时间恰好相反,则这样看起来是没问题的。但是这个结束时间有可能相等!我猜可能 std 少在结束的地方 ++cnt 了。这里我有一个 hack 数据:

2
1 2
1 1
1 1

正解输出:

1

而 std 将 11 号节点放在了 22 号节点的前面,所以无输出。

综上,我觉得 std 的大体思路没啥问题,而且避开等号的方法挺妙的,但是这个细节写挂了。希望可以修改一下 std 并添加这个数据。

2022/10/5 21:57
加载中...