AT_abc467_e 题解

Moya_Rao · 2026-07-19 18:51:12 · 题解

挺好的题。

我赛时其实没抱有做出来的期待来着（。但是过了就是很开心哇。涨分快乐。

上不了蓝其实一点也不快乐，都怪 D。

首先我们先看看 C 是怎么做的。我的 C 题做法是，枚举首位为 0 和 1 的两种情况，然后分别算代价，取 \min 后就是最终答案。

容易发现题目这个设定在固定首位的情况下其他位是“一气呵成”的，也就是直接固定了的（这也是为什么 C 能这么做的原因）。但是这题的 M 过于大了，一个个枚举肯定不行，我们需要更聪明的办法。

发现我们只需要从庞大的 M 个可能方案中提取出尽可能少的“有效的”方案，就能大幅优化时间。那么，什么样的方案才算是“有效的”方案，也就是可能成为答案的方案呢？如果你这种变化方式变出的 a' 数组对于任何 i 都有 a'_i \not= a_i 的话，这个方案就是“无效的”，因为在进行一些整体加减后让某个 a'_i = a_i 一定能更优。那它连上去“打擂台”的机会都没有了，抛弃得了。

这样就把 O(M) 数量级变成了 O(n)，这样确实可以逐个枚举了，但你枚举了这种方案情况后，你就没办法再 O(n) 遍历一遍求代价了啊。怎么办呢？

我们研究变化量。先让首位为 0 试试水，求出来一个数组 u 表示首位为 0 时的变化后的合法数组（显然是唯一的），并求出这个代价，记为 alsum（全局和）。如果你增加首位的值，那么其他位置的值大概是 + - + - + - + - ... 这样一个变化图，奇数位置 + 偶数位置 - 这样子。

有了这样的变化趋势图，我们就可以针对 a'_i = a_i 的每个 i 计算其对应首位值 t。具体来讲，如果 i 是奇数则 t = a_i - u_i 否则 t_i = u_i - a_i（要对 M 取模哦）。

得到了首位之后，我们就可以计算代价的变化量了！对于一个 j，我们对下标奇偶性分类讨论其代价变化量：

• - 变化量形如 $(t+u_j)-a_j$ 即 $t+(u_j-a_j)$，由于 $u_j - a_j$ 为前面处理过的正数，所以这里不可能出现负数变化量，只有可能变化量值求出来后 $\ge M$。 - 而 $\ge M$ 的变化量是无意义的，我们要让其对 $M$ 取模（否则你绕一圈绕回来了没有绕的必要），并且只有在 $t \ge M - (u_j - a_j)$ 也就是 $(u_j - a_j) \ge M-t$ 的情况下是要取模的（这里的取模可以等价看作 $-M$），统计个数后乘法累加即可。
• - 变化量形如 $(u_j - t) - a_j$ 即 $(u_j - a_j) - t$，由于 $u_j - a_i$ 为前面处理过的 $< M$ 的值，所以这里不可能出现 $\ge M$ 的变化量，只有可能出现负数变化量。 - 而负数变化量是需要 $+M$ 才合法的，并且只有在 $t > (u_j - a_j)$ 也就是 $(u_j - a_j) < t$ 的情况下是要 $+M$ 的，统计个数后乘法累加即可。

我们发现，两种情况归根到底都是根据 (u_j - a_i) 的大小来判断的，而这些值最开始就固定了，不会变，因此直接把它们塞进数组，排序，要用到的时候二分查找即可。

然后基本上就结束了啦，记得开 long long 哦。

下面放的是赛时代码，有少许调试痕迹，底下还有思路注释，也许你也可以看看哦 qwq。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
const LL INF = 0x3f3f3f3f3f3f3f3f;
LL n,M,a[N],b[N],u[N],alsum,p1[N],p0[N],cnt1,cnt0,Ans;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}

int main(){
    n=read(),M=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<n;i++)b[i]=read();
    u[1]=0;
    for(int i=2;i<=n;i++)
        u[i]=(b[i-1]-u[i-1]+M)%M;
    for(int i=1;i<=n;i++)
        if(i&1)p1[++cnt1]=(u[i]-a[i]+M)%M,alsum+=p1[cnt1];
        else p0[++cnt0]=(u[i]-a[i]+M)%M,alsum+=p0[cnt0];
    sort(p1+1,p1+cnt1+1);
    sort(p0+1,p0+cnt0+1);
    Ans=INF;
    for(int i=1;i<=n;i++){
        LL t=0;
        if(i&1)t=(a[i]-u[i]+M)%M;
        else t=(u[i]-a[i]+M)%M;
        //cout<<i<<":"<<t<<"!!\n";
        //t=0;
        LL res=alsum+(n%2)*t;
        int id=lower_bound(p1+1,p1+cnt1+1,M-t)-p1;
        res-=(cnt1-id+1ll)*M;
        id=lower_bound(p0+1,p0+cnt0+1,t)-p0-1;
        res+=(id+0ll)*M;
        //if(res==-3)cout<<"?\n";
        Ans=min(Ans,res);
    }
    cout<<Ans<<"\n";
    return 0;
}
/*
先让首位为 0 试试水
然后如果你增加首位的值
那么大致就是这样一个变化趋势图：
+ - + - + - + -
奇数 + 偶数 - 这个样子
那么你求值的时候就是看绝对值吧。啊不会要分类讨论吧。
不好做啊感觉

不是绝对值！是差值！啊啊啊我们有救了
你先让首位为 0 试水 得到每个位置的值
然后前面不是给提供了变化趋势吗
你就枚举每个 i（包括 1）然后求出变化到 a[i] 值的这个首位值
然后你求代价。这个代价怎么求呢？

假设最原始值为 x
首位为 0 时其值为 u
然后它是 + 的一个变化
现在你让首位为 t 了
那么它的累加量就是 t+u-x 这样子的
但是要对 M 取模（有可能变成 0）
这个取模好像并不是很好做
但是你考虑你 t 加到什么程度需要取模 取模就是减去一个 M 嘛。
那么你按从大到小存下这些 u-x 值
然后针对这个 t 计算有几个要取模的 减掉就行了

然后如果是 - 的变化呢？
累加量就是 u-t-x 吧 对
但是有可能要 +M
那你就根据这个 u-x 的大小
针对这个 t 计算有几个减炸了的
加上就行了

注意你存下来的 u-x 是 (u-x+M)%M 这个
+ 的情况下就是 t>=M-(u-x) 这样子
即 (u-x)>=M-t
- 的情况下就是 t>(u-x) 这样子
即 (u-x)<t
注意符号呀！然后基本上就结束了

*/

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！