3675.score
2026-10-12
题解
不难发现区间合法只需要关注甲和乙的分差 d,当 d<0 时乙胜利。
转化一下题目操作,当遇到 1 时 d←d−1,当遇到 0 时,若 d<2,则 d←d+1,否则 d←d−1。
0 的刻画不是很自然,不妨改成令 d←d+1,若 d=3,则 d←1。
考虑将 r 扫描线,那么只需要考虑 r 左侧所有位置的合法数量,而我们只需要知道所有的 d,并且他们变化时是相似的,也就是只需要知道某种 d 的区间数量即可。
考虑把分差存在数组里,由于 d∈[−n,2],每次操作时只需要全局加减并且修改至多一个位置,不妨维护一个全局增量 Δ∈[−n,n],f[i] 满足 d=i−b+Δ(其中 b 为偏移量 n+1)。
这样设计的话,0 的位置即为 z=b−Δ,2 的位置为 z+2。
怎么快速统计答案?直接维护一个数 q 表示当前 d<0 的游戏数,那么操作变为:
- 1:q←q+f[z],Δ←Δ−1。
- 0:q←q−f[z−1],f[z]←f[z]+f[z+2],f[z+2]←0,Δ←Δ+1。
简单维护一下,记得开 long long,做完了。
