专栏文章

题解：AT_abc389_f [ABC389F] Rated Range

vvanueber
AT_abc389_f题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mimz5sh7
此快照首次捕获于
2025/12/01 17:56
3 个月前
此快照最后确认于
2025/12/01 17:56
3 个月前
查看原文

F - Rated Range

先离线，发现初始时 X<YX<Y，那么从开始到结束的所有过程 X≤YX\le Y，即相对顺序不发生改变。
把询问的每个值拍到序列上，发现一次操作的影响是一段区间。
为了维护每个询问的值，需维护以下操作：
  1. 区间加 11。
  2. 找到 ≥x\ge x 的第一个下标。
  3. 找到 ≤y\le y 的最后一个下标。
由于序列是单调的，线段树维护区间最大最小值，然后线段树上二分即可。
时间复杂度 Θ((n+q)log⁡q)\Theta((n+q)\log q)。
code

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...