题解：P12579 [UOI 2021] 哥萨克与 GCD

· · 题解

更好的阅读体验

大型纪录片之 O(n \log^3 n) 跑过 10^5。

假设 s 是 b 的前缀和数组，那么我们每次可以查询 s 上面任意两个位置的差。进一步地，我们考虑一次询问 [l, r] 区间时就连无向边 l-1 和 r，当 0 \sim n 都联通时，每个前缀的和都能通过 s_0 = 0 来推算。

问题转化成，有一个完全图，l, r 之间的边权为 (l, r] 的 \gcd，多次修改 a，求最小生成树。

考虑 prim 算法，选择每个点边权最小的出边。则对于 i，必然连向 0 或 n 中的一个。因此假设 g,h 分别是 a 序列的前缀、后缀 \gcd 数组，则 i 连边的代价是 \min(g_i, h_i)。

我们观察到，g 单调不升，h 单调不降。因此取 g 和取 h 一定只有一个分界点，可以在线段树上二分得到。

考虑一次单点修改可以认为是若干次区间推平。假设我们新加入一个数字 x，则会将一个区间的前缀 \gcd 值变成 x 的一个约数 x_0，会将紧跟在后面的一个区间变成 x_0 的一个约数 x_1，以此类推。后缀 \gcd 同理。所以我们同样可以在线段树上二分到每个值需要推平的区间，然后直接区间修改就可以了。

那么这道题就做完了，由于线段树需要维护 \gcd，因此一次线段树操作的复杂度是 O(\log n \log V) 的。由于一个询问会拆成 \log V 个区间，因此复杂度是 O(n \log n \log^2 V)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 100006
using namespace std;
int n,q,a[N],lgcd[N],rgcd[N];
inline int read()
{
    int ret=0,f=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();
    return ret*f;
}
inline void write(int k)
{
    if(k<0)putchar('-'),k=-k;
    int nnum[20],ttp=0;
    while(k)nnum[++ttp]=k%10,k/=10;
    if(!ttp)nnum[++ttp]=0;
    while(ttp)putchar(nnum[ttp--]^48);
}
inline int gcd(int a,int b)
{
    int az=__builtin_ctz(a),bz=__builtin_ctz(b),z=min(az,bz),dif;
    b>>=bz;
    while(a)
    {
        a>>=az,dif=b-a,az=__builtin_ctz(dif);
        if(a<b) b=a;if(dif<0)a=-dif;else a=dif;
    }
    return b<<z;
}
int lsum[N<<2],rsum[N<<2],tagl[N<<2],tagr[N<<2];
inline void build(int p,int l,int r)
{
    tagl[p]=tagr[p]=0;
    if(l==r)return lsum[p]=lgcd[l],rsum[p]=rgcd[l],(void)0;
    int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    lsum[p]=lsum[p<<1]+lsum[p<<1|1],rsum[p]=rsum[p<<1]+rsum[p<<1|1];
}
inline void addtagl(int p,int l,int r,int x){tagl[p]=x,lsum[p]=(r-l+1)*x;}
inline void addtagr(int p,int l,int r,int x){tagr[p]=x,rsum[p]=(r-l+1)*x;}
inline void push_down(int p,int l,int r)
{
    int mid=l+r>>1;
    if(tagl[p])addtagl(p<<1,l,mid,tagl[p]),addtagl(p<<1|1,mid+1,r,tagl[p]);
    if(tagr[p])addtagr(p<<1,l,mid,tagr[p]),addtagr(p<<1|1,mid+1,r,tagr[p]);
    tagl[p]=tagr[p]=0;
}
inline void updatel(int p,int l,int r,int L,int R,int x)
{
    if(L>R)return;if(L<=l&&r<=R)return addtagl(p,l,r,x);
    push_down(p,l,r);int mid=l+r>>1;
    if(L<=mid)updatel(p<<1,l,mid,L,R,x);
    if(R>mid)updatel(p<<1|1,mid+1,r,L,R,x);
    lsum[p]=lsum[p<<1]+lsum[p<<1|1],rsum[p]=rsum[p<<1]+rsum[p<<1|1];
}
inline void updater(int p,int l,int r,int L,int R,int x)
{
    if(L>R)return;if(L<=l&&r<=R)return addtagr(p,l,r,x);
    push_down(p,l,r);int mid=l+r>>1;
    if(L<=mid)updater(p<<1,l,mid,L,R,x);
    if(R>mid)updater(p<<1|1,mid+1,r,L,R,x);
    lsum[p]=lsum[p<<1]+lsum[p<<1|1],rsum[p]=rsum[p<<1]+rsum[p<<1|1];
}
inline int queryl(int p,int l,int r,int L,int R)
{
    if(L>R)return 0;if(L<=l&&r<=R)return lsum[p];
    push_down(p,l,r);int mid=l+r>>1,ret=0;
    if(L<=mid)ret+=queryl(p<<1,l,mid,L,R);
    if(R>mid)ret+=queryl(p<<1|1,mid+1,r,L,R);
    return ret;
}
inline int queryr(int p,int l,int r,int L,int R)
{
    if(L>R)return 0;if(L<=l&&r<=R)return rsum[p];
    push_down(p,l,r);int mid=l+r>>1,ret=0;
    if(L<=mid)ret+=queryr(p<<1,l,mid,L,R);
    if(R>mid)ret+=queryr(p<<1|1,mid+1,r,L,R);
    return ret;
}
inline int findpos(int p,int l,int r)
{
    if(l==r)return l;
    push_down(p,l,r);int mid=l+r>>1;
    if(queryl(1,1,n,mid+1,mid+1)>=queryr(1,1,n,mid+1,mid+1))
        return findpos(p<<1|1,mid+1,r);
    else return findpos(p<<1|1,l,mid);
}
int tree[N<<2];
inline void build2(int p,int l,int r)
{
    if(l==r)return tree[p]=a[l],(void)0;
    int mid=l+r>>1;build2(p<<1,l,mid),build2(p<<1|1,mid+1,r);
    tree[p]=gcd(tree[p<<1],tree[p<<1|1]);
}
inline void update(int p,int l,int r,int k,int x)
{
    if(l==r)return tree[p]=x,(void)0;
    int mid=l+r>>1;k<=mid?update(p<<1,l,mid,k,x):update(p<<1|1,mid+1,r,k,x);
    tree[p]=gcd(tree[p<<1],tree[p<<1|1]);
}
inline int query(int p,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)return tree[p];
    int mid=l+r>>1,ret=0;
    if(L<=mid)ret=gcd(ret,query(p<<1,l,mid,L,R));
    if(R>mid)ret=gcd(ret,query(p<<1|1,mid+1,r,L,R));
    return ret;
}
inline int findl(int p,int l,int r,int lg,int x)
{
    if(l==r)return gcd(lg,tree[p])<x?l:n+1;
    int mid=l+r>>1,lg2=gcd(lg,tree[p<<1]);
    if(lg2<x)return findl(p<<1,l,mid,lg,x);
    else return findl(p<<1|1,mid+1,r,lg2,x);
}
inline int findr(int p,int l,int r,int rg,int x)
{
    if(l==r)return gcd(tree[p],rg)<x?l:0;
    int mid=l+r>>1,rg2=gcd(rg,tree[p<<1|1]);
    if(rg2<x)return findr(p<<1|1,mid+1,r,rg,x);
    else return findr(p<<1,l,mid,rg2,x);
}
main()
{
    n=read(),q=read();
    for(register int i=1;i<=n;i++)a[i]=read();
    for(register int i=1;i<=n;i++)lgcd[i]=gcd(lgcd[i-1],a[i]);
    for(register int i=n-1;i;i--)rgcd[i]=gcd(rgcd[i+1],a[i+1]);
    rgcd[n]=1e15,build(1,1,n),build2(1,1,n);
    int pos=findpos(1,1,n);
    write(min(queryl(1,1,n,pos+1,n)+queryr(1,1,n,1,pos),queryl(1,1,n,1,n))),putchar(10);
    while(q--)
    {
        int k=read(),x=read();
        update(1,1,n,k,x);
        for(register int i=k,j,val;i<=n;i=j)
            val=query(1,1,n,1,i),j=findl(1,1,n,0,val),updatel(1,1,n,i,j-1,val);
        for(register int i=n,j,val;i;i=j)
            val=query(1,1,n,i,n),j=findr(1,1,n,0,val),updater(1,1,n,max(1ll,j),i-1,val);
        int pos=findpos(1,1,n);
        write(min(queryl(1,1,n,pos+1,n)+queryr(1,1,n,1,pos),queryl(1,1,n,1,n))),putchar(10);
    }
    return 0;
}

很久之前做的，今天才想起来写题解。

我做的时候这题还是蓝题来着 /oh