题解：P17846 回天

zsjaaaxy · 2026-11-11 19:17:10 · 题解

solution

首先刻画一下最优解的特征。定义只有一种数的可重集为单集，否则为双集。

首先发现它不可能由两个双集构成，原因是我们发现答案有一个下界为 m+1（选最大值单独一个集合即得），其中 m=\max_{i=1}^n(a_{i})。如果有两个双集，有 f(A)\le\frac{m}{2},f(B)\le\frac{m}{2}，故 f(A)+f(B)<m+1，不如选最大值单独一个集合。

如果我们枚举单集是由哪种数组成的显然复杂度太高，考虑剪掉一些不优解。具体地，我们发现单集的数只能选严格最大值与次大值，否则不优。考虑证明，假设去重后从大到小排完序后为 a_{1},a_{2},.....,a_{n}，选了 a_{k}(k>2) 作为单集的数的种类，假设除 a_{k} 外 a 的 \gcd 为 d。那么 a_{1}-a_{2}\ge d。此时我们的混乱值是 a_{k}+d，如果改成以 a_{1} 为值的单集的混乱值为 a_{1}+1，如果改完不劣只需证 (a_{k}+d)-(a_{1}+1)\le 0，即证 a_{1}-a_{k} \ge d-1，由于 a_{1}-a_{k}>a_{1}-a_{2}\ge d，所以原命题成立。

接下来只需考虑钦定单集元素之后的事情，相当于要求除它之外所有数的 \gcd，建立动态开点线段树维护即可。

时间复杂度 O((n+q)\log V)。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1000000,V=1000000000;
int n,a[N],q;
struct SGT
{
    int idx=1;
    struct node
    {
        int lp,rp,l,r,sum,cnt;
    }tree[N*20];
    void update(int x,int qp,int op)
    {
        if(tree[x].l==tree[x].r)
        {
            tree[x].cnt+=op;
            if(tree[x].cnt)
            {
                tree[x].sum=tree[x].l;
            }
            else
            {
                tree[x].sum=0;
            }
            return;
        }
        int mid=((tree[x].l+tree[x].r)>>1);
        if(qp<=mid)
        {
            if(!tree[x].lp)
            {
                tree[x].lp=++idx;
                tree[tree[x].lp]={0,0,tree[x].l,mid,0,0};
            }
            update(tree[x].lp,qp,op);
        }
        else
        {
            if(!tree[x].rp)
            {
                tree[x].rp=++idx;
                tree[tree[x].rp]={0,0,mid+1,tree[x].r,0,0};
            }
            update(tree[x].rp,qp,op);
        }
        tree[x].sum=__gcd(tree[tree[x].lp].sum,tree[tree[x].rp].sum);
        return;
    }
    int query(int x,int ql,int qr)
    {
        if(!x)
        {
            return 0;
        }
        if(ql<=tree[x].l&&tree[x].r<=qr)
        {
            return tree[x].sum;
        }
        int res=0,mid=((tree[x].l+tree[x].r)>>1);
        if(ql<=mid)
        {
            res=__gcd(query(tree[x].lp,ql,qr),res);
        }
        if(qr>mid)
        {
            res=__gcd(query(tree[x].rp,ql,qr),res);
        }
        return res;
    }
}S;
set<int> s;
unordered_map<int,int> mp;
int f(int x)
{
    return __gcd(S.query(1,1,x-1),S.query(1,x+1,V))+x;
}
void solve()
{
    if(s.size()==1)
    {
        cout<<2*(*s.rbegin())<<"\n";
        return;
    }
    int h=(*s.rbegin());
    int ans=f(h);
    s.erase(h);
    if(!s.empty())
    {
        ans=max(ans,f((*s.rbegin())));
    }
    s.insert(h);
    cout<<ans<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    S.tree[1]={0,0,1,V,0};
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];  
        S.update(1,a[i],1);
        mp[a[i]]++;
        if(mp[a[i]]==1)
        {
            s.insert(a[i]);
        }
    } 
    solve();
    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        S.update(1,a[x],-1);
        mp[a[x]]--;
        if(mp[a[x]]==0)
        {
            s.erase(a[x]);
        }
        S.update(1,y,1);
        a[x]=y;
        mp[y]++;
        if(mp[y]==1)
        {
            s.insert(y);
        }
        solve();
    }
    return 0;
}