题解：P15741 [JAG 2024 Summer Camp #2] Max Sum of GCD

· · 题解

我们思考怎么染色可以让答案最大，相同的数可以合并成一个数，因为 \gcd 与数量无关，如果把一样的数染两种色，答案一定不会变大。

我们不难想到可以让最大值单独一个色，其他的染另一个色，可以过样例。

但是在小规模打表后发现不对，比如 4 5 6，难道假了，我们不妨再考虑次大值一个色，其他的染另一个色，发现没有反例了。

考虑证明：存在最优方案至少有一个色全是一样的数，且这个数至少大与另一个色的 \gcd。

我们记独占一个色的数，其他的一个任意值，其他值的 \gcd 分别为 x,s,g。

有 \gcd(x,s)\ge \frac{x}{2}，所以 x+\gcd(s,g)\ge \gcd(x,s)+g。

再去证明：存在最优方案至少有一个色全是最大值或次大值。

我们记最大值，次大值，次次大值，其他值的 \gcd 分别为 x,y,z,g，根据定义，有 x>y>z>g，我们有 \gcd(x,y)\le x-y，所以 x+\gcd(y,z,g)\ge z+\gcd(x,y,g)，且 y+\gcd(x,z,g)\ge z+\gcd(x,y,g)。

但是 x+\gcd(y,z,g) 和 y+\gcd(x,z,g) 的值我们不好确定，直接去最大值就行。

具体实现要特判次小值不存在的情况。

我们用一个自己喜欢的数据结构维护区间内最大值和次大值和除了这俩的 \gcd。

丑陋的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
/*
#pragma region 哈基米
*/
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9'||c<'0') {if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
const int N=2e5+5;
int n,m,cnt,a[N],c[10];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
struct tree{
    struct leaf{
        int mx,sx,sum;
        leaf operator+(const leaf &t)const{
            c[1]=mx,c[2]=sx,c[3]=t.mx,c[4]=t.sx;sort(c+1,c+5);
            int p=unique(c+1,c+5)-c-1;sort(c+1,c+p+1,greater<int>());
            int res=gcd(sum,t.sum);if(p>=3) res=gcd(res,c[3]);if(p>=4) res=gcd(res,c[4]);
            return (leaf){c[1],c[2],res};
        }
    }tr[N<<2];
    #define ls x<<1
    #define rs x<<1|1
    void push_up(int x){tr[x]=tr[ls]+tr[rs];}
    void build(int x,int l,int r){
        if(l==r) {tr[x]=(leaf){a[l],0,0};return ;}
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        push_up(x);
    }
    leaf query(int x,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return tr[x];
        int mid=(l+r)>>1;leaf res=(leaf){0,0,0};
        if(ql<=mid) res=query(ls,l,mid,ql,qr);
        if(qr>mid) res=res+query(rs,mid+1,r,ql,qr);
        return res;
    }
    int qq(int l,int r){
        leaf res=query(1,1,n,l,r);
        return max({res.mx+gcd(res.sx,res.sum),res.sx+gcd(res.mx,res.sum),
            res.sum==0?(res.sx==0?res.mx*2:res.mx+res.sx):0});
    }
}tr;
signed main(){
    // freopen("1.in" ,"r",stdin );
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    m=read();tr.build(1,1,n);
    while(m--) {
        int l=read(),r=read();
        printf("%lld\n",tr.qq(l,r));
    }
    return 0;
}