题解：P15939 [JOI Final 2026] 传奇团子吃家 / Legendary Dango Eater

Grace2022 · 2026-04-08 16:06:53 · 题解

一个贪心策略是对辣团子取相反数，能吃就吃，如果当前积攒的团子和小于 0 就放弃。有如下 O(nq) 代码：

for(int i = 1; i <= n; ++i){
    read(a[i]);
    if(i % 2 == 0) a[i] = -a[i];
}
//对于每个询问：
for(int i = l; i <= r; ++i){
    if(a[i] > 0){
        ans += (s + a[i]) / k;
        s = (s + a[i]) % k;
    }
    else s = max(s + a[i], 0ll);
}
write(ans), putchar('\n');

我们以 s 变为 0 为分界点（相当于重置成起点），这样就可以在每个询问倍增跳段了。设 sum_i 表示取相反数后一正一负的 a 的前缀和。现在要找到 f_{0, x}，表示 (\sum_{j = x} ^{f_{0, x} - 1} a_j) \bmod k + a_{f_{0, x}} \le 0 的最小辣团子位置 f_{0, x}。

这个式子等价于 (sum_{f_{0, x} - 1} - sum_{x - 1}) \bmod k \le -a_{f_{0, x}}。我们从小到大枚举 i，辣团子的 f_{0, i} = i + 1（因为以这个辣团子开头没用不如舍弃），把还没计算过甜团子的 f_{0, i} 的 i 丢进一个 set 里。现在考虑当前辣团子 i 可以当哪些甜团子的 f。

令 tmp 为取模过的 sum_{i - 1}（对应式子的 sum_{f_{0, x} - 1}），j 为 set 里的候选甜团子（sum_{j - 1} 就对应上述 sum_{x - 1}）。取模是环形的，所以候选甜团子分为：

以上利用了 set 的自动排序，具体实现定义一个 set<pair<long long, int> > 即可，pair.first 表示 sum_{j - 1}，pair.second 表示 j。对于所有满足条件的 j，有 f_{0, j} = i，然后把 j 从集合里删除。

直到最后还在 set 里的 j，说明没有令 j 满足上述条件不等式的 f_{0, j}，这时令 f_{0, j} = n + 1。