求问昨晚div2的D
  • 板块学术版
  • 楼主PNNNN
  • 当前回复7
  • 已保存回复7
  • 发布时间2024/9/28 11:46
  • 上次更新2024/9/28 14:38:06
查看原帖
求问昨晚div2的D
556975
PNNNN楼主2024/9/28 11:46

请问昨晚的D可不可以用类似 P9755 [CSP-S 2023] 种树 的方法,先求出每个点 ii 向左扩展到 11 和向右扩展到 nn 的最晚扩展时间 LiL_iRiR_i,可知 LiL_i 是单调递减,RiR_i 是单调递增的。

假设当前起始点为 PP。那么对于一个 i<Pi<P,用 P9755 [CSP-S 2023] 种树 的方法,ii 被扩展的时间应为 Pi+1+j=P+1n[RjLi]P-i+1+\sum\limits_{j=P+1}^{n}[R_j\leq L_i]。同理,对于 i>Pi>Pii 被拓展的时间应为 iP+1+j=1P1[LjRi]i-P+1+\sum\limits_{j=1}^{P-1}[L_j\leq R_i]。这些可以用平衡树 lognlogn 维护。

对于类似 Rj=LiR_j=L_i 的情况,我认为扩展的顺序是没有影响的。请问做是否是对的。

2024/9/28 11:46
加载中...