专栏文章

题解:P14004 [eJOI 2025] Vacation

P14004题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minsnt6w
此快照首次捕获于
2025/12/02 07:42
3 个月前
此快照最后确认于
2025/12/02 07:42
3 个月前
查看原文
如果最终交集的区间 [l,r][l,r] 不与任意一个端点重合,那么可以在不改变长度的情况下向两边移动,总有一个方向的代价 0\leq 0,因此可能的 [l,r][l,r] 的端点与已有端点重合。并且由于 [l,r][l,r] 的长度不大于任意已有区间的长度,因此没有包含。固定 l,rl,r 调整的代价就是 max(rRi,0)+max(Lil,0)\sum\max(r-R_i,0)+\max(L_i-l,0)。二分答案 midmid,双指针去掉这个 max\max。时间复杂度 O(n(logn+logV))\mathcal O(n(\log n+\log V))

评论

1 条评论,欢迎与作者交流。

正在加载评论...