传送门
题意：
- 给长度为 \(n\) 与 \(n-1\) 的序列 \(A\) 和 \(B\)，所有元素都在 \([0, M-1]\) 内。
- 一次操作：将 \(A_i\) 增加 \(1\)。
- 目标：满足 \((A_i + A_{i+1}) \bmod M = B_i\)
- 求最少操作次数。
\(?\) \(!\) \(拆拆\) \(!\) \(?\)
设最终数组为 \(x\)，则满足 \(x_i+x_{i+1}\bmod M=B_i\)。可以发现 \(x_1\) 确定则整个序列 \(x\) 确定。
\(x_2 \equiv B_1-x_1 \pmod M\)
\(x_3 \equiv B_2-x_2 \equiv B_2-B_1+x_1\pmod M\)
\(\dots\)
\(x_n \equiv B_n-B_{n-1}+B_{n-2}-\dots +(-1)^{n+1}B_1\pmod M\)
所以设 \(s_1=0,s_{i+1}=(B_i-s_i)\bmod M\)(其实这里\(s\)就是一个满足条件的\(x\))，\(x_i=(s_i+(-1)^{i+1}x_1)\bmod M\)
让 \(A_i\) 到达 \(x_i\) 的最小步数为 \((x_i-A_i)\bmod M\)。
我们想求 \(f(x_1)=\sum_{i=1}^{n}(x_i-A_i)\bmod M\) 的最小值，设 \(v_i=(s_i-A_i)\bmod M\)，考察第 \(i\) 项
当 \(i\) 是奇数是 \((v_i+x_1)\bmod M\)，反之为 \((v_i-x_1)\bmod M\)。
\(i\) 为奇时 \(v_i+x_1-M*[x_1\ge M-v_i]\)，反之为 \(v_i-x_1+M*[x1\ge v_i+1]\)。
\(f\) 就是一个分段函数，那最小值一定是在每一段的分界上，用 map 记录每个临界点计算 \(x_1\) 在这个区间的 \(f(x_1)\)，开头 \(1\) 结尾 \(M\) 也计算一遍，取最小。复杂度 \(O(n\log n)\)。
CODE
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
const int N=200005;
#define int long long
int a[N],b[N],s[N],v[N],n,m;
map<int,int>mp;
signed main()
{cin>>n>>m;rep(i,1,n) cin>>a[i];rep(i,1,n-1) cin>>b[i];rep(i,2,n){s[i]=(b[i-1]-s[i-1])%m;if(s[i]<0) s[i]+=m;}int cnt=0,c0=0;rep(i,1,n){v[i]=(s[i]-a[i])%m;if(v[i]<0) v[i]+=m;cnt+=v[i];if(i&1) ++c0;else --c0;}rep(i,1,n)if(i&1){int x=(m-1-v[i])%m;if(x<=m-2) mp[x]-=m;}else if(v[i]<=m-2) mp[v[i]]+=m;int ans=cnt,tot=0;for(auto&p:mp) tot+=p.second;ans=min(ans,cnt+c0*(m-1)+tot);int ls=0;for(auto&p:mp){ls+=p.second;ans=min(ans,cnt+c0*(p.first+1)+ls);}cout<<ans<<'\n';
}