题解：ABC426F Clearance【线段树】

chenwenmo · 2025-10-05 18:14:00 · 题解

ABC426F Clearance

因为是在线的区间操作，考虑用线段树维护。

既然每种商品之间是独立的，那我们就单独考虑。假设下一次需要购买某种商品 K 个，那么该商品数量 A 有三种状态：

每种商品如果这次是状态 2，之后就一直是状态 3 了。因此可以暴力处理状态 2，最多只会处理 N 次。然后维护状态 1 3。

用线段树维护即可，实现的时候类似于区间线段树二分，只不过一次二分可以同时找到多个状态 2 的位置。复杂度 O((N + Q) \log N)