DUCK

Goose, Goose, DUCK? 对于这种确定 L,R 可简单求出区间答案的问题,我们常常考虑通过固定端点,移动另一端计算贡献。 具体的,我们移动 R,计算[1,R]中的点对答案的贡献。 假设某个值在 [1,R] 中出现位置为 \(1\leq a_1,a_2...a_m\leq R\),可以得 ......

洛谷传送门 CF 传送门 首先转化一下，让鸭子不动，猎人往右移动，就相当于开的相邻两枪距离 \(> m\)。 设 \(f_{x, i}\) 为仅考虑 \(r \le x\) 的鸭子，上一次在 \(i\) 开枪，能打到的最大鸭子个数。 \(f_{x - 1} \to f_x\) 时，首先有 \(f_{ ......