P13692 [CEOI 2025] lawnmower

提供一个比较魔法的做法。我有一个大胆的想法！

---

下文中「列」相当于「割草道」。

第一个“灵感”就是拿割草机一口气推到底，装满箱子就直接去当前列的末尾卸货。可想而知这是不对的，因为在一些割草道的末尾，为了达到最优解，我们即使没有装满也会把箱子清空（比如某一个 $a_i$ 相当大，我们可能会在第 $i-1$ 列割完后清空箱子）。不妨先称这种操作为「特殊操作」。

有一种自然的想法是令 $dp_{i,j}$ 为割完第 $i$ 列后箱子里有 $j$ 个单位的草的最小消耗时间，但是我不会维护。

于是我们需要动用一些魔术技巧了。

---

我们发现两次「特殊操作」之间都是用割草机一口气推到底，不装满不卸货的。而因为要求最后一列割完后也要清空箱子，于是有一个想法就是令 $dp_i$ 为割完了第 $i$ 列，然后对第 $i$ 列进行特殊操作的最小消耗时间。

可以通过枚举上一个「特殊操作」的列进行转移。

$$dp_i=\min_{l<i}dp_l+\lceil\frac{S_i-S_l}{c}\rceil\times b+\sum_{l<j\le i}a_j\times(\lceil\frac{S_j-S_l}{c}\rceil-\lfloor\frac{S_{j-1}-S_l}{c}\rfloor)$$

简写为 $dp_i=\min_{l<i}dp_l+w(l+1,i)$。

其中 $S_i=\sum_{j=1}^i v_j$。

简单维护似乎可做到时间复杂度 $O(n^2)$，听说有人用此法创过去了。

---

假如 $l$ 固定了，已知 $w(l+1,i-1)$，但是右端点从 $i-1$ 转为了 $i$ ，那对 $w$ 的影响是什么呢？

$\Delta=w(l+1,i)-w(l+1,i-1)=(\lceil\frac{S_i-S_l}{c}\rceil-\lceil\frac{S_{i-1}-S_l}{c}\rceil)\times b+(\lceil\frac{S_i-S_l}{c}\rceil-\lfloor\frac{S_{i-1}-S_l}{c}\rfloor)\times a$

把后一项改写一下：$\lfloor\frac{S_{i-1}-S_l}{c}\rfloor=\lceil\frac{S_{i-1}-S_l}{c}\rceil-[S_{i-1}\not\equiv S_l]$

所以 $\Delta=(\lceil\frac{S_i-S_l}{c}\rceil-\lceil\frac{S_{i-1}-S_l}{c}\rceil)\times(a_i+b)+[S_{i-1}\not\equiv S_l]\times a_i$

如果将 $l$ 按照 $S_l \bmod c$ 的值分类，用 $f_r=\min_{S_l \bmod c=r}dp_l+w(l+1,i)$ 存放的话，那上式的后一项就很好维护了，考虑将第一项继续拆分。

---

这个时候就需要一些观察力了，注意到

你谷 Latex 真垃圾，只能截图了

代入 $b=v_i,a=S_{i-1}-S_l$，则发现上面是好处理的，只需对 $f_{S_{i-1}\bmod c}$ 单独处理即可，下面第一项也是好处理的。

剩下的就是给满足 $(S_{i-1}-S_l)\bmod c>c-v_i\bmod c=R$ 的加上 $a_i+b$：

• 如果 $S_{i-1}\bmod c>R$，则对所有 $S_{i-1}+1\le S_l\bmod c\le c-1 \vee0\le S_l\bmod c< S_{i-1}\bmod c-R$ 的 $l$ 区间加一个 $a_i+b$；
• 否则对所有 $S_{i-1}\bmod c+1\le S_l\bmod c<c+S_{i-1}\bmod c-R$ 的 $l$ 加上 $a_i+b$。

将 $S_i\bmod c$ 离散化后使用二分查找+线段树简单维护即可。

---

早说了是魔法了吧

放在一块的都是维护同一类贡献。时间复杂度 $O(n\log n)$。

// I love Furina forever!
# include <bits/stdc++.h>
// # include "grader.cpp"
# define maxn 500100
# define mod 1000000007
# define inf 0x3f3f3f3f
# define int long long
# define mem(a, val) memset(a, val, sizeof(a))
# define rep(i, j, k) for(int i = j; i <= k; ++i)
# define per(i, j, k) for(int i = j; i >= k; --i)
using namespace std;

namespace Segment_Tree {
    # define ls (p << 1)
    # define rs (p << 1 | 1)
    # define mid (pl + pr >> 1)
    int Min[maxn << 1], tag[maxn << 1];

    inline void push_up(int p) {Min[p] = min(Min[ls], Min[rs]);}
    inline void push_down(int p) {int x = tag[p]; Min[ls] += x; Min[rs] += x; tag[ls] += x; tag[rs] += x; tag[p] = 0;}
    inline void build(int p, int pl, int pr) {Min[p] = inf; if(pl != pr) build(ls, pl, mid), build(rs, mid + 1, pr);}
    inline void update(int p, int pl, int pr, int pos, int x) {
        if(pl == pr) Min[p] = min(Min[p], x);
        else push_down(p), (pos <= mid ? update(ls, pl, mid, pos, x) : update(rs, mid + 1, pr, pos, x)), push_up(p);
    }

    inline void update(int p, int pl, int pr, int l, int r, int x) {
        if(l <= pl && pr <= r) {Min[p] += x, tag[p] += x; return;}
        push_down(p);
        if(l <= mid) update(ls, pl, mid, l, r, x);
        if(r > mid) update(rs, mid + 1, pr, l, r, x);
        push_up(p); 
    }
} using namespace Segment_Tree;

int n, b, c, m;
int a[maxn], val[maxn], preSum[maxn], R[maxn << 1], pos[maxn], dp[maxn];

inline int Find2(int x, int num) {
    int l = 1, r = num, res = 0;
    while(l <= r) {int Mid = l + r >> 1; R[Mid] < x ? res = Mid, l = Mid + 1 : r = Mid - 1;}
    return res;
}

long long mow(signed n1, signed c1, signed b1, std::vector<signed> &a1, std::vector<signed> &v1) {
    n = n1, c = c1, b = b1; m = n + 1; rep(i, 0, n - 1) a[i + 1] = a1[i], val[i + 1] = v1[i];
    rep(i, 1, n) preSum[i] = (preSum[i - 1] + val[i]) % c, R[i] = preSum[i];
    sort(R + 1, R + m + 1); int num = unique(R + 1, R + m + 1) - R - 1;
    rep(i, 1, num) R[i + num] = R[i] + c;
    rep(i, 1, m) pos[i] = lower_bound(R + 1, R + num + 1, preSum[i]) - R; pos[0] = pos[m];

    build(1, 1, num);
    update(1, 1, num, pos[0], 0);

    rep(i, 1, n) {
        int r = c - val[i] % c;
        update(1, 1, num, 1, num, a[i]); update(1, 1, num, pos[i - 1], pos[i - 1], -a[i]);
        
        update(1, 1, num, pos[i - 1], pos[i - 1], (a[i] + b) * ((val[i] + c - 1) / c));
        update(1, 1, num, 1, num, val[i] / c * (a[i] + b)); update(1, 1, num, pos[i - 1], pos[i - 1], -val[i] / c * (a[i] + b));
       
        int l1 = pos[i - 1] + 1, r1 = Find2(c + R[pos[i - 1]] - r, num + num);
       if(l1 <= r1) {
            if(l1 <= num) update(1, 1, num, l1, min(r1, num), a[i] + b);
            if(r1 > num) update(1, 1, num, 1, r1 - num, a[i] + b);
        }
        dp[i] = Min[1];
        update(1, 1, num, pos[i], dp[i]);
    }
    return dp[n];
}