P3863 序列 笔记

根据操作和询问，涉及两个维度：序列和时间。

由于询问只涉及单点，考虑对序列下标做扫描线，那么就可以把操作差分，变成需要维护一种数据结构可以做到：

• 对 $[t,+\mathrm{\infty })$ 后缀进行 $+x$ 操作。
• 查询 $[1,t)$ 中 $\ge x$ 的数有多少个。

$\log$ 数据结构都不太好做，考虑对时间分块，整块维护一个 $\mathrm{tag}$ 操作时一起加，散块暴力一个一个加。

为了方便查询，可以在每个块内按值排序，每次操作散块的时候就遍历整个块找到满足 $t$ 的再查，这样查询就可以在每个块里用 lower_bound 了。

时间复杂度 $O(n\sqrt{n}\log n)$