求助一道题
  • 板块学术版
  • 楼主seantheone
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/10/6 18:06
  • 上次更新2023/10/27 08:27:26
查看原帖
求助一道题
456790
seantheone楼主2022/10/6 18:06

自己口胡的,就是给定一棵树,每个点有两个参数 ai,bia_i,b_i,求在 uuvv 的路径上,所有 ai<aja_i<a_jbi<bjb_i<b_j 的点对数量有多少。

显然这道题可以重链剖分套一个 cdq 三维偏序。但是复杂度 O(nlog5n)O(n \log^5 n),比暴力还慢。

求有无更好的做法。

2022/10/6 18:06
加载中...