坠机：AT_abc454_f [ABC454F] Make it Palindrome 2

· · 题解

:::info[什么样的人生是失败的？（第十弹）] 点击标题可以看见上一次坠机。

怎么把分店都开到 abc 来了，这不对吧？

闪击 ABC 成功，D 看错题手滑加强一万倍大战 5min 写完过样例然后吃一发罚又调了 10min，这就是傻逼我说白了。

看对题秒掉以后开 E 大战 40min 无法战胜，这就是区。

开 E 前看了眼榜发现 Floweryhb 怎么跳 E 过 F 了，于是决定开 F，大战不到 25min 以后切掉了。

还剩 10min，金 perf，开香槟！

看了 5min E 还是不会，看看大家的分。

？！全过 G 了？！

开 G 看眼吧。

？！dsu on tree 板子？！

还能蒸吗！几点了？21:37 /hec

配几个图。

一定要把题开全。

@flc_love_dsu 一定要开到 dsu 的题。 :::

ABCDF 遗憾离场。

为什么会变成这样子呢？我问我自己。

区间加 1 并取模，要求最终得到回文串。

显然对应点其实是在做环上追逐的一个问题，于是考虑对应位减一下变成差值。

奇数长度的序列中间那个数可以直接扔出去不管。

假设你是用左边减去右边，那么同时增加左右等于不改。

注意到第一个通过平衡达到不改的数，比其更靠近中间的位置一定也会被覆盖，所以也不改。

所以会修改的恰好是一个区间，并且我们可以通过加左边或者加右边做到区间加 1 或减 1。

于是就变成一个序列，区间加 1 或减 1 并对 m 取模，变成全 0 串的最小步数。

区间修改，考虑差分一下变成单点修改。

于是就变成一个序列，单点加 1 或减 1 并对 m 取模，变成全 0 串的最小步数。

显然操作 m 次和不操作同义，不知道为啥赛时纠结了好一会能不能直接取模。

一个点变成 0 有两种手段，其一是直接全部减掉，代价是 a_i，其二是加到 m 取模归零，代价是 m-a_i。

然后你注意到我们把原题面转化成了差分形式，一个区间操作由一个加法和一个减法组成，所以总代价其实是上述两个手段分别统计代价后的较大值。

考虑贪心。

假设现在我们全部选择方案一操作，如果我们把一个点扔到方案二，扔哪个最优呢？

显然是最大的那个，方案一减少的最多，方案二增加的最少，所以这个贪心是正确的。

排序后扫一遍过去动态维护方案一和方案二分别需要承担的代价即可，答案就是最小值。

时间复杂度 O(n\log n)，瓶颈在于排序。

#include<bits/stdc++.h>
#define eps (1e-12)
#define inf ((int)1e18)
#define lowbit(x) ((x)&(-(x)))
#define mod 998244353
#define int long long
#define N 200005
using namespace std;
inline char get_char(bool op);
inline int read();
inline void print(int x);
inline int qpow(int a,int b=mod-2);
inline int gcd(int a,int b);
int a[N];
int b[N];
inline void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    a[i]-=a[n-i+1];
    n/=2;
    for(int i=1;i<=n;i++)
    a[i]%=m,a[i]+=m,a[i]%=m;
    for(int i=n;i;i--)
    a[i]-=a[i-1];
    int sum=0;
    for(int i=1;i<=n;i++)
    a[i]%=m,a[i]+=m,a[i]%=m,sum+=m-a[i];
    sort(a+1,a+1+n);
    int cnt=0;
    int ans=sum;
    for(int i=1;i<=n;i++){
        sum-=m-a[i];
        cnt+=a[i];
        ans=min(ans,max(sum,cnt));
    }
    cout<<ans<<'\n';
}
signed main(){
    int t=1;
    t=read();
    while(t--)solve();
    return 0;
}
inline int gcd(int a,int b){
    int flc=min(__builtin_ctz(a),__builtin_ctz(b)),tmp;
    b>>=__builtin_ctz(b);
    while(a){
        a>>=__builtin_ctz(a);
        tmp=b-a;
        if(a<b)b=a;
        a=abs(tmp);
    }
    return (b<<flc);
}
inline char get_char(bool op=1){
    if(op)return getchar();
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int sum=0,fish=1;
    char c=get_char();
    while((c<'0'||c>'9')&&c!='-')c=get_char();
    if(c=='-')fish=-1,c=get_char();
    while(c>='0'&&c<='9')sum=sum*10+(c-'0'),c=get_char();
    return sum*fish;
}
inline void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else print(x/10),putchar(x%10+'0');
}
inline int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
//「——悲伤应该是一种特别的情感吧。我那时候就察觉到了，原来我确实是幸福的。在少了一个人，灿烂的光辉开始削弱之后，我才终于发现这件事。」

//「除此之外还有一点。我明白了幸福一旦出现裂痕，后续只会不断崩毁。就像是从指间滑落的细沙一样，即便握紧拳头也无法阻止。灿烂耀眼的只有过去，指间掌握住的是现在。所以，我对未来无法抱有任何期待——」

//「潘丽宝，你……」

//「我再说一遍，我并非想寻死。不过我也没有积极地抗拒死亡的意思。自己是否度过了美好的人生，唯有人生终结之际才能透过回想来判断。而我想度过美好的人生。」