题解：AT_abc467_e [ABC467E] Adjacent Sums (hard)
Muyangmiku
·
·
题解
我们先将题目形式化。
\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。
因此，$f(x)$ 其实由很多分段的线段组成，这种函数的最值枚举断点分段即可，断点为 $m-d_i$ 和 $d_i+1$，注意线段的左端点可取而右端点不可取，每条线段又一定是单调不降的，我们要求最小值，也就只用考虑每个分段的左端点，即断点。
关于时间复杂度，每一项最多提供两个断点，而我们排了序，时间复杂度为 $O(n\log n)$。
### Code
```cpp
#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*/
```