LOJ

分析

设 $s_i$ 为 $\sum_{j=1}^i b_j$，则一次询问可以确定 $s_r-s_{l-1}$。如果我们看成连边 $(l-1,r)$，则相当于要让 $(0,n)$ 连通，也就是要求最小生成树。

根据 Kruskal 那套理论，我们一定会连边 $(0,n)$。

根据 Prim 那套理论，剩下的点要么连 $(0,i)$，要么连 $(i,n)$。更具体的，一定存在一个点 $p$ 满足 $[1,p]$ 都连了 $n$、$[p+1,n-1]$ 都连了 $0$，也就是说 $p$ 左边的点连 $n$ 比连 $0$ 更优。

我们可以用线段树维护区间 $\gcd$，从而在线段树上二分出 $p$。然后我们需要求出 $\sum_{i=1}^p\gcd(a_{i..n})$ 和 $\sum_{i=p+1}^n\gcd(a_{1..i})$，在线段树上找到 $\gcd$ 变化的 $\mathcal{O}(\log n)$ 个位置及其对应的区间即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,b[N];

#define ls (o<<1)
#define rs (o<<1|1)
int gcdv[N<<2];
void pushup(int o) { gcdv[o]=__gcd(gcdv[ls],gcdv[rs]); }
void build(int o,int l,int r) {
    if (l==r) { gcdv[o]=b[l]; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
void modify(int o,int l,int r,int p,int w) {
    if (l==r) { gcdv[o]=w; return; }
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls,l,mid,p,w);
    else modify(rs,mid+1,r,p,w);
    pushup(o);
}
int findp(int o,int l,int r,int dl,int dr) {
    if (l==r) return l;
    int mid=(l+r)>>1,x=__gcd(gcdv[ls],dl),y=__gcd(gcdv[rs],dr);
    return x<=y?findp(ls,l,mid,dl,y):findp(rs,mid+1,r,x,dr);
}
ll queryp(int o,int l,int r,int p,int d) {
    if (l==r) return __gcd(gcdv[o],d);
    int mid=(l+r)>>1,dr=__gcd(gcdv[rs],d),dl=__gcd(gcdv[ls],dr);
    return p<=mid?queryp(ls,l,mid,p,dr):(dl==dr?1ll*(mid-l+1)*dl:queryp(ls,l,mid,mid,dr))+queryp(rs,mid+1,r,p,d);
}
ll querys(int o,int l,int r,int p,int d) {
    if (l==r) return __gcd(gcdv[o],d);
    int mid=(l+r)>>1,dl=__gcd(gcdv[ls],d),dr=__gcd(gcdv[rs],dl);
    return p>mid?querys(rs,mid+1,r,p,dl):(dl==dr?1ll*(r-mid)*dr:querys(rs,mid+1,r,mid+1,dl))+querys(ls,l,mid,p,d);
}
#undef ls
#undef rs

int main() {
    n=read(),Q=read();
    for (int i=1;i<=n;++i) b[i]=read();
    build(1,1,n);
    while (Q--) {
        int p=read(),w=read(); modify(1,1,n,p,w);
        p=findp(1,1,n,0,0);
        printf("%lld\n",queryp(1,1,n,p,0)+querys(1,1,n,p,0)-gcdv[1]);
    }
    return 0;
}