题解：AT_abc467_e [ABC467E] Adjacent Sums (hard)
MaxBlazeResFire
·
·
题解
答案只与 a_1 的增量 \Delta 有关，记作 f(\Delta)。先计算出 f(0) 的答案，以及 0 的时候，每个数需要变成的数 c_i。
将答案写成 \displaystyle f(\Delta)=\sum_{i=1}^n(c_i-a_i)+[c_i<a_i]m。
你发现直接开个 $\rm map$ 维护 $D_d$ 表示当 $\Delta$ 从 $d-1$ 到 $d$ 的时候，$f$ 的额外增量是多少个 $m$ 就可以了（例如，对于 $i$ 是偶数且 $c_i>a_i$，那么其对 $D_{c_i-a_i+1}$ 有 $m$ 的贡献，对于 $i$ 是奇数且 $c_i<a_i$，那么其对 $D_{a_i-c_i}$ 有 $-m$ 的贡献）求的时候枚举有效增量进行累加。复杂度 $O(n\log n)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 200005
#define INF (int)1e18
int n,m,a[MAXN],b[MAXN],ned[MAXN],dif[MAXN];
inline void solve(){
scanf("%lld%lld",&n,&m);
for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&a[i]);
for( int i = 1 ; i < n ; i ++ ) scanf("%lld",&b[i]);
map<int,int> M;
//维护模意义下需求，需求突变次数
int now = a[1],ans = 0;
for( int i = 2 ; i <= n ; i ++ ){
ned[i] = ( b[i - 1] - now + m ) % m;
ans += ( ned[i] >= a[i] ) ? ned[i] - a[i] : ned[i] - a[i] + m;
now = ned[i];
}
for( int i = 2 ; i <= n ; i += 2 ){
if( ned[i] >= a[i] ){
M[ned[i] - a[i] + 1] += m;
}
else{
if( ned[i] != a[i] - 1 ) M[m - ( a[i] - ned[i] ) + 1] += m;
}
}
for( int i = 3 ; i <= n ; i += 2 ){
if( ned[i] < a[i] ){
M[a[i] - ned[i]] -= m;
}
else{
if( ned[i] != a[i] ) M[m - ( ned[i] - a[i] )] -= m;
}
}
//每个点的贡献是 ned[i] >= a[i] 时为 ned[i] - a[i]，否则为 m + ned[i] - a[i]
//a[1] 增加 1 的时候，奇数位置都增加，偶数位置都减少，所以只用管那些突变 -m 或者 +m 的部分
int S = ans,coef = n % 2;
//a[1] 增加 1，S 增加 coef，然后增加若干 m 或减少若干 m，所以必然只用管突变的点
//ned[i] 从 a[i] 变到 a[i] - 1，贡献突然增加 m；
int num = 0;
for( pair<int,int> p : M )
num += p.second,ans = min( ans , S + p.first * coef + num );
printf("%lld\n",ans);
}
signed main(){
int t = 1;
while( t -- ) solve();
return 0;
}
```