我们先将题目形式化。
$$
\begin{cases}
a_1+a_2 \equiv b_1 \pmod{m}\
a_2+a_3 \equiv b_2 \pmod{m}\
\dots\
a_{n-1}+a_n \equiv b_{n-1} \pmod{m}
\end{cases}
$$
做完本题的 Easy Version 后，我们发现其实只要确定了最终 $a_1$ 的值，后面的项模 $m$ 的余数都是可以确定的，因此我们考虑枚举最终 $a_1$ 为 $x$，将答案写成 $x$ 的函数。

$$
\begin{cases}
a_1 \equiv x \pmod{m}\
a_2 \equiv b_1-a_1 \equiv b_1-x \pmod{m}\
a_3 \equiv b_2-a_2 \equiv b_2-b_1+x \pmod{m}\
\dots\
a_n \equiv b_{n-1}-a_{n-1} \equiv b_{n-1}-b_{n-2}+b_{n-3}\dots - (-1)^n x\pmod{m}
\end{cases}
$$

不难发现，令 $c_i \equiv b_i-b_{i-1}+b_{i-2}-\dots$，是可以预处理出来的，因此最终的花费为：
$$f(x)=\sum_{i=1}^n ((c_i-(-1)^ix-a_i)\bmod m),x\in[0,m-1]$$
拆开奇偶来分析，并令 $d_i=(c_i-a_i) \bmod m$ 则：
$$f(x)=\sum_{i为奇数}((d_i+x)\bmod m)+\sum_{i为偶数}((d_i-x)\bmod m)$$
这样的函数就很经典了，因为 $d_i,x \in [0,m-1] $，令 $s=\sum_{i为奇数}(d_i+x)+\sum_{i为偶数}(d_i-x)$。

当 $d_i+x \geq m$ 时，相比 $s$ 会多减去一个 $m$；当 $d_i-x<0$ 时，相比 $s$ 会加上一个 $m$。

$s$ 本身是 $x$ 的一次函数，化简后 $s=\sum d_i +(n \bmod 2) x$。

因此，$f(x)$ 其实由很多分段的线段组成，这种函数的最值枚举断点分段即可，断点为 $m-d_i$ 和 $d_i+1$，注意线段的左端点可取而右端点不可取，每条线段又一定是单调不降的，我们要求最小值，也就只用考虑每个分段的左端点，即断点。

关于时间复杂度，每一项最多提供两个断点，而我们排了序，时间复杂度为 $O(n\log n)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+5;
int n,m;
ll a[N],b[N],c[N],d[N],f;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) c[i]=(b[i-1]-c[i-1]+m)%m,d[i]=(c[i]-a[i]+m)%m,f+=d[i];
    vector<ll> v,odd,even;//奇偶断点
    for(int i=1;i<=n;i++){
        if(i%2==0&&d[i]<m-1) v.push_back(d[i]+1),even.push_back(d[i]+1); //x在[0,m-1]，超过的直接不要了
        if(i%2==1&&d[i]>0) v.push_back(m-d[i]),odd.push_back(m-d[i]);
    } 
    sort(v.begin(),v.end());
    sort(even.begin(),even.end());
    sort(odd.begin(),odd.end());
    int i=0,j=0;
    ll ans=f;//实际上是f(0)
    for(ll x:v){
        while(i<odd.size()&&odd[i]<=x) i++;//奇数中，要多减去多少个m
        while(j<even.size()&&even[j]<=x) j++;//偶数中，要多加上多少个m
        ans=min(ans,f+x*(n%2)+(ll)m*(j-i));
    }
    cout<<ans;
    return 0;
}
/*g++ -O2 -std=c++17 test.cpp -o test && .\test< in.txt > out.txt*/