How CSP-S D

灌水区

WorldMachine @ 2024-10-26 22:26:06

考场上瞪了很久没瞪出来正解写了个错解（抑或是写挂了的 \mathcal O(Tn\log n)？），感觉很不可做，很好奇解法

by cff_0102 @ 2024-10-26 22:27:39

me 2

by WorldMachine @ 2024-10-26 22:32:02

我草是不是我 pushup 写错了

by CCPSDCGK @ 2024-10-26 22:37:34

@Pentiment

前 76 分只需要看出来擂台赛可 O(1) 合并即可，这里不再赘述。

设 solve(l,r,L,R) 为当前分治到了 [l,r] 区间，l左边的区间合并结果结果为 L，r右边的区间合并结果为 R

然后你就做缺一分治。

递归 solve(l,mid,L,merge([mid+1,r],R)) solve(mid+1,r,merge(L,[l,mid]),R) 然后就做完了

你会发现复杂度就是调用 solve 的次数，也就是线性。

糊的，不太清楚正确性。

by WorldMachine @ 2024-10-26 22:37:53

@NujObIuc thx