题解:
考虑询问了区间([l,r]),就知道了和,也就知道了(s[r])和(s[l-1])的差。
那么给(r)和(l-1)连一条边,我们相当于要搞出点为(0..n)的最小生成树。
运用kruskal的想法,每次找最小的连接不同联通块的边,发现一定是一个前缀或者后缀是最优的。
所以考虑找到一个最右的分界点(k)满足(gcd(b[1..k])ge gcd(b[k+1..n])),那么(x le k)的点都是选择(gcd(b[x+1..n])),而(> k)的点都是(gcd(b[1..x]))。
我们知道前缀gcd的变化点只有log个,考虑怎么找出来。
不难想到线段树维护区间(gcd),然后每次线段树二分,直接搞复杂度是(O(n~log^3~n)),注意判断一个区间是否合法时只用看这个区间的(gcd)是不是我要的(gcd)的倍数,即可省掉一个(log)。
Code:
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int N = 1e5 + 5;
int n, Q, b[N], x, y;
int gcd(int x, int y) { return !y ? x : gcd(y, x % y);}
int t[N * 4];
#define i0 i + i
#define i1 i + i + 1
void bt(int i, int x, int y) {
if(x == y) {
t[i] = b[x];
return;
}
int m = x + y >> 1;
bt(i0, x, m); bt(i1, m + 1, y);
t[i] = gcd(t[i0], t[i1]);
}
int pl, pr;
void add(int i, int x, int y) {
if(x == y) {
t[i] = b[x];
return;
}
int m = x + y >> 1;
if(pl <= m) add(i0, x, m); else add(i1, m + 1, y);
t[i] = gcd(t[i0], t[i1]);
}
struct P {
int x, y;
P(int _x = 0, int _y = 0) {
x = _x, y = _y;
}
};
int px, py, pz;
void ef(int i, int x, int y) {
if(y < pl || x > pr) return;
if(t[i] % py == 0) return;
if(x == y) { px = x; return;}
int m = x + y >> 1;
if(!pz) {
ef(i0, x, m);
if(px == -1) ef(i1, m + 1, y);
} else {
ef(i1, m + 1, y);
if(px == -1) ef(i0, x, m);
}
}
P p[N], q[N]; int p0, q0;
void work();
void Qry() {
p0 = 0;
for(int i = 1, s = 0; i <= n; i ++) {
s = gcd(s, b[i]);
pl = i, pr = n;
px = -1, py = s; pz = 0;
ef(1, 1, n);
if(px == -1) px = n + 1;
px --;
p[++ p0] = P(px, s);
i = px;
}
q0 = 0;
for(int i = n, s = 0; i > 0; i --) {
s = gcd(s, b[i]);
pl = 1, pr = i;
px = -1, py = s; pz = 1;
ef(1, 1, n);
if(px == -1) px = 0;
px ++;
q[++ q0] = P(px, s);
i = px;
}
p[p0 + 1].x = n + 1;
q[q0 + 1].x = 0;
q[0].x = n + 1;
work();
}
int qry1(int x) {
fo(i, 1, p0) if(p[i].x >= x)
return p[i].y;
}
int qry2(int x) {
if(x > n) return 1e9 + 1;
fo(i, 1, q0) if(q[i].x <= x)
return q[i].y;
}
int pd(int k) {
if(k < 0) return 0;
int v1 = qry1(k), v2 = qry2(k + 1);
return v1 >= v2;
}
ll sum1(int k) {
ll ans = 0;
fo(i, 1, p0) {
int x = p[i - 1].x + 1, y = p[i].x;
if(y >= k) ans += (ll) p[i].y * (y - max(x, k) + 1);
}
return ans;
}
ll sum2(int k) {
ll ans = 0;
fo(i, 1, q0) {
int x = q[i].x, y = q[i - 1].x - 1;
if(x <= k) ans += (ll) q[i].y * (min(y, k) - x + 1);
}
return ans;
}
void work() {
int k = 0;
fo(i, 1, p0) {
if(pd(p[i].x)) k = max(k, p[i].x);
if(pd(p[i - 1].x + 1)) k = max(k, p[i - 1].x + 1);
}
fo(i, 1, q0) {
if(pd(q[i].x - 1)) k = max(k, q[i].x - 1);
if(pd(q[i - 1].x - 2)) k = max(k, q[i - 1].x - 2);
}
ll ans = sum2(k + 1) + sum1(k + 1);
ans -= p[p0].y;
pp("%lld
", ans);
}
int main() {
scanf("%d %d", &n, &Q);
fo(i, 1, n) scanf("%d", &b[i]);
bt(1, 1, n);
fo(ii, 1, Q) {
scanf("%d %d", &x, &y);
b[x] = y;
pl = pr = x;
add(1, 1, n);
Qry();
}
}