【模运算建模，分段线性优化】邻项校准

题意概括

给定长度为 $N$ 的序列 $A$，以及长度为 $N-1$ 的序列 $B$。

每次操作可以把某个 $A\_i$ 增加 $1$。需要让最终序列满足

$(A\_i+A\_{i+1})\bmod M=B\_i$

对所有 $1\le i\<N$ 都成立，并最小化总操作次数。

由于 $N\le 2\times 10^5$，$M\le 10^9$，不能枚举每个元素最终增加多少，也不能枚举全部 $M$ 种余数后逐个检查。

样例分析

考虑第一组样例：

$A=(4,6,7),\qquad B=(5,5),\qquad M=10.$

假设最终令第一个数模 $10$ 的余数为 $7$。

由第一个限制可得，第二个数的余数必须满足

$7+A\_2'\equiv 5\pmod {10},$

所以第二个数的余数为 $8$。

继续根据第二个限制，

$8+A\_3'\equiv 5\pmod {10},$

所以第三个数的余数为 $7$。

于是最终余数为

$(7,8,7).$

原序列只需要分别增加

$3,\ 2,\ 0$

次，总操作次数为 $5$。

这个过程说明，只要确定第一个数最终的余数，后面所有数的余数都会被唯一确定。

算法思路

整体思路

设第一个数最终模 $M$ 的余数为 $x$。

根据相邻两项的限制，可以依次推导出所有位置的最终余数。奇数位置的余数形如 $x+C\_i$，偶数位置的余数形如 $-x+C\_i$。

对于一个已经确定的目标余数，把 $A\_i$ 增加到该余数所需要的最少操作次数，也是一个关于 $x$ 的模函数。

因此，原问题可以转化为：在 $0\le x\<M$ 中，最小化若干个分段一次函数之和。

函数只会在至多 $O(N)$ 个关键位置发生跳变。将这些位置排序后，通过二分统计每个候选点两侧的元素数量，就能在 $O(N\log N)$ 时间内得到答案。

推导过程

确定余数后，单个位置的最小代价

设最终 $A\_i$ 模 $M$ 的余数为 $R\_i$。

因为只允许增加 $A\_i$，所以最少增加次数为

$(R\_i-A\_i)\bmod M.$

这里的模运算结果取 $0$ 到 $M-1$ 之间的整数。

如果再额外增加 $M$ 次，最终余数不会改变，但操作次数会更多，因此固定最终余数以后，只需要考虑这个最小非负差值。

用 $x$ 表示所有最终余数

设

$R\_1=x.$

为了满足

$R\_i+R\_{i+1}\equiv B\_i\pmod M,$

必须有

$R\_{i+1}\equiv B\_i-R\_i\pmod M.$

定义 $C\_1=0$，并递推

$C\_{i+1}=(B\_i-C\_i)\bmod M.$

可以归纳得到：

$ R\_i= \begin{cases} (x+C\_i)\bmod M, & i\text{ 为奇数},\\ (-x+C\_i)\bmod M, & i\text{ 为偶数}. \end{cases} $

也就是说，所有奇数位置关于 $x$ 的系数为 $1$，所有偶数位置关于 $x$ 的系数为 $-1$。

将每个位置的代价化成统一形式

对于奇数位置 $i$，定义

$Z\_i=(A\_i-C\_i)\bmod M.$

这个位置的操作次数为

$ \begin{aligned} (R\_i-A\_i)\bmod M &=(x+C\_i-A\_i)\bmod M\\ &=(x-Z\_i)\bmod M. \end{aligned} $

对于偶数位置 $i$，定义

$Z\_i=(C\_i-A\_i)\bmod M.$

这个位置的操作次数为

$ \begin{aligned} (R\_i-A\_i)\bmod M &=(-x+C\_i-A\_i)\bmod M\\ &=(Z\_i-x)\bmod M. \end{aligned} $

因此，奇数位置贡献的函数为

$g\_z(x)=(x-z)\bmod M,$

偶数位置贡献的函数为

$h\_z(x)=(z-x)\bmod M.$

展开模运算

当 $0\le x,z\<M$ 时，奇数位置的贡献可以写成

$ g\_z(x)= \begin{cases} x-z+M, & x\<z,\\ x-z, & x\ge z. \end{cases} $

也可以表示为

$g\_z(x)=x-z+M\[x\<z].$

其中方括号表示条件成立时取 $1$，否则取 $0$。

偶数位置的贡献为

$ h\_z(x)= \begin{cases} z-x, & x\le z,\\ z-x+M, & x>z. \end{cases} $

即

$h\_z(x)=z-x+M\[x>z].$

设所有奇数位置的 $Z\_i$ 构成多重集合 $O$，所有偶数位置的 $Z\_i$ 构成多重集合 $E$。

总操作次数为

$ F(x)=\sum\_{z\in O}g\_z(x)+\sum\_{z\in E}h\_z(x). $

展开后得到

$ \begin{aligned} F(x) \={}&(|O|-|E|)x -\sum\_{z\in O}z +\sum\_{z\in E}z\\ &+M\left( |{z\in O\mid z>x}| \+ |{z\in E\mid z\<x}| \right). \end{aligned} $

对于给定的 $x$，只需要知道：

$|{z\in O\mid z>x}|$

和

$|{z\in E\mid z\<x}|.$

分别将两个集合排序，就可以通过二分查找求出这两个数量。

为什么不需要枚举所有 $x$

奇数位置的函数 $g\_z(x)$ 在 $x=z$ 时发生跳变。

在跳变前需要检查 $z-1$，跳变后需要检查 $z$。

偶数位置的函数 $h\_z(x)$ 在 $x$ 从 $z$ 变成 $z+1$ 时发生跳变，所以需要检查 $z$ 和 $z+1$。

因此只需要检查候选集合

$ \begin{aligned} S={}&{0,M-1}\\ &\cup{Z\_i,(Z\_i-1)\bmod M\mid i\text{ 为奇数}}\\ &\cup{Z\_i,(Z\_i+1)\bmod M\mid i\text{ 为偶数}}. \end{aligned} $

候选点数量不超过 $2N+2$。

任意两个相邻跳变位置之间，所有判断条件 $x\<z$ 和 $x>z$ 都保持不变，因此 $F(x)$ 是关于 $x$ 的一次函数。

一次函数在一段连续整数区间上的最小值一定出现在区间端点。所有区间端点都已经包含在候选集合中，所以检查这些候选点不会遗漏最优答案。

算法流程

1. 读入 $N$、$M$、序列 $A$ 和序列 $B$。

2. 初始化 $C\_1=0$，从左到右处理每个位置。

3. 对于奇数位置 $i$，计算

   $Z\_i=(A\_i-C\_i)\bmod M,$

   并加入数组 $O$。

4. 对于偶数位置 $i$，计算

   $Z\_i=(C\_i-A\_i)\bmod M,$

   并加入数组 $E$。

5. 使用

   $C\_{i+1}=(B\_i-C\_i)\bmod M$

   计算下一个位置的常数项。

6. 将数组 $O$ 和 $E$ 分别排序，并计算它们的元素之和。

7. 枚举候选点：

   • $0$ 和 $M-1$；
   • 对每个 $z\in O$，检查 $z$ 和 $(z-1)\bmod M$；
   • 对每个 $z\in E$，检查 $z$ 和 $(z+1)\bmod M$。

8. 对每个候选点 $x$：

   • 使用 upper_bound 求出 $O$ 中严格大于 $x$ 的元素数量；
   • 使用 lower_bound 求出 $E$ 中严格小于 $x$ 的元素数量；
   • 根据公式计算 $F(x)$。

9. 输出所有候选点中最小的 $F(x)$。

正确性说明

引理一：固定最终余数后，算法计算的单点代价最小

设位置 $i$ 的最终余数为 $R\_i$。

所有能够达到该余数的操作次数均形如

$(R\_i-A\_i)\bmod M+kM,$

其中 $k$ 为非负整数。

当 $k=0$ 时操作次数最少，因此最小代价为

$(R\_i-A\_i)\bmod M.$

引理成立。

引理二：固定 $R\_1=x$ 后，所有最终余数唯一确定

相邻限制要求

$R\_{i+1}\equiv B\_i-R\_i\pmod M.$

所以已知 $R\_i$ 后，$R\_{i+1}$ 的余数唯一确定。

从 $R\_1=x$ 开始依次递推，可以唯一得到所有 $R\_i$。

同时，这样得到的余数必然满足每一个相邻限制。

引理成立。

引理三：公式 $F(x)$ 等于固定 $R\_1=x$ 时的最少操作次数

根据引理二，固定 $x$ 后所有最终余数唯一确定。

对于奇数位置，其最小代价为

$(x-Z\_i)\bmod M.$

对于偶数位置，其最小代价为

$(Z\_i-x)\bmod M.$

根据引理一，各位置分别选择最少增加次数即可，并且不同位置的增加操作互不影响。

因此把所有位置的最小代价相加，恰好得到固定 $x$ 时的最少总操作次数，即 $F(x)$。

引理成立。

引理四：候选集合中一定包含一个最优解

函数 $F(x)$ 中，奇数位置的判断条件只会在 $x=Z\_i$ 附近发生变化，偶数位置的判断条件只会在 $x=Z\_i+1$ 附近发生变化。

算法将每个跳变位置及其前一个整数都加入候选集合，同时加入区间边界 $0$ 和 $M-1$。

在相邻两个跳变位置之间，所有指示条件保持不变，因此 $F(x)$ 是一次函数。

一次函数在整数区间上的最小值一定出现在区间端点，而这些端点都被算法检查。

所以至少有一个全局最优的 $x$ 位于候选集合中。

引理成立。

定理：算法输出满足全部限制所需的最少操作次数

根据引理四，算法枚举的候选集合中包含一个全局最优的 $x$。

根据引理三，算法对每个候选 $x$ 计算的 $F(x)$，就是固定该 $x$ 时能够达到的最少操作次数。

因此算法取所有候选值中的最小值，等于所有 $0\le x\<M$ 中的最小值，也就是原问题的最优答案。

定理成立。

实现细节与易错点

1. C++ 中负数取模仍可能为负数。计算 $C\_i$ 和 $Z\_i$ 后，需要在结果小于 $0$ 时加上 $M$。

2. 奇数位置使用

   $Z\_i=(A\_i-C\_i)\bmod M,$

   偶数位置使用

   $Z\_i=(C\_i-A\_i)\bmod M.$

   两者顺序不能写反。

3. 对于奇数位置，需要检查 $Z\_i$ 和 $Z\_i-1$。当 $Z\_i=0$ 时，前一个位置应当视为 $M-1$。

4. 对于偶数位置，需要检查 $Z\_i$ 和 $Z\_i+1$。当 $Z\_i=M-1$ 时，下一个位置应当视为 $0$。

5. 奇数集合中需要统计严格大于 $x$ 的元素数量，因此使用 upper_bound。

6. 偶数集合中需要统计严格小于 $x$ 的元素数量，因此使用 lower_bound。

7. 最大答案接近

   $N(M-1),$

   可能达到约 $2\times 10^{14}$，需要使用 long long。

8. 候选点重复不会影响正确性，不需要专门去重。

参考实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    ll m;
    cin >> n >> m;

    vector<ll> a(n), b(n - 1);
    for (ll &x : a) cin >> x;
    for (ll &x : b) cin >> x;

    vector<ll> o, e;
    ll c = 0;

    for (int i = 0; i < n; i++) {
        ll z;

        if (i % 2 == 0) {
            z = (a[i] - c) % m;
            if (z < 0) z += m;
            o.push_back(z);
        } else {
            z = (c - a[i]) % m;
            if (z < 0) z += m;
            e.push_back(z);
        }

        if (i + 1 < n) {
            c = (b[i] - c) % m;
            if (c < 0) c += m;
        }
    }

    sort(o.begin(), o.end());
    sort(e.begin(), e.end());

    ll so = accumulate(o.begin(), o.end(), 0LL);
    ll se = accumulate(e.begin(), e.end(), 0LL);

    auto cal = [&](ll x) {
        ll co = o.end() - upper_bound(o.begin(), o.end(), x);
        ll ce = lower_bound(e.begin(), e.end(), x) - e.begin();

        return ((ll)o.size() - (ll)e.size()) * x
             - so + se + m * (co + ce);
    };

    ll ans = min(cal(0), cal(m - 1));

    for (ll z : o) {
        ans = min(ans, cal(z));
        ans = min(ans, cal((z + m - 1) % m));
    }

    for (ll z : e) {
        ans = min(ans, cal(z));
        ans = min(ans, cal((z + 1) % m));
    }

    cout << ans << '\n';
    return 0;
}

复杂度分析

递推所有 $C\_i$ 并构造两个数组需要 $O(N)$ 时间。

对奇数位置和偶数位置对应的数组排序，需要

$O(N\log N)$

时间。

候选点共有 $O(N)$ 个。每次计算答案需要进行两次二分查找，时间复杂度为 $O(\log N)$，因此枚举候选点的总时间复杂度为

$O(N\log N).$

总时间复杂度为

$O(N\log N).$

两个排序数组共保存 $N$ 个元素，除此之外只使用常数个变量，因此空间复杂度为