请问昨晚的D可不可以用类似 P9755 [CSP-S 2023] 种树 的方法,先求出每个点 i 向左扩展到 1 和向右扩展到 n 的最晚扩展时间 Li 和 Ri,可知 Li 是单调递减,Ri 是单调递增的。
假设当前起始点为 P。那么对于一个 i<P,用 P9755 [CSP-S 2023] 种树 的方法,i 被扩展的时间应为 P−i+1+j=P+1∑n[Rj≤Li]。同理,对于 i>P,i 被拓展的时间应为 i−P+1+j=1∑P−1[Lj≤Ri]。这些可以用平衡树 logn 维护。
对于类似 Rj=Li 的情况,我认为扩展的顺序是没有影响的。请问做是否是对的。