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

· · 题解

来个简单做法。

首先考虑如何判定一组询问是合法的，令 s_i = \sum_{j = 1}^i b_j，则每次询问 [l, r] 则可以得到 s_{l - 1} 和 s_r 的关系，将关系看作一张无向图，每次询问 [l, r] 就将 l - 1 和 r 连边，那么如果图连通则该序列合法。

根据 \gcd 的单调性，除 0, n 以外的每个点 i 向 0 和 n 较小边权的点连边，代价为 \min(\gcd_{j = 1}^i a_j, \gcd_{j = i + 1}^n a_j)。不难发现这一步达到了下界。然后这个时候我们还需要将 0, n 搞连通，代价为 \gcd_{i = 1}^n a_i，同样达到了下界，所以这个答案就是最小的。直接暴力容易 O(nq)。

考虑优化，不难发现前缀 \gcd 相同的段很多，具体的，只有最多 O(\log V) 个不同的段，后缀同理。在线段树上维护 \gcd，并在线段树上二分即可快速找到下一个 \gcd 更改的位置，这样就可以 O(\log V \log n) 处理出所有前缀段和后缀段了，然后暴力取交计算答案是 O(\log^2 V)，也可以归并做到 1log 但是没必要，因为前面已经是 2log 的了。时间复杂度 O(n \log n \log V + n \log^2 V)，跑了 500ms。

::::info[代码]

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pir pair<ll, ll> 
#define mkpir make_pair
#define umap unordered_map
#define pb emplace_back
#define fi first
#define se second
#define db double
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;
const ll INF = 1e18, mod = 998244353;
const db eps = 1e-9;

/*
struct edge{
  int v, next;
}edges[M << 1];
int head[N], idx;

il void add_edge(int u, int v){
  edges[++idx] = {v, head[u]};
  head[u] = idx;
}
*/

il void chkmax(ll& x, ll y){if(x < y) x = y;}
il void chkmin(ll& x, ll y){if(x > y) x = y;}
il void chkmax(int& x, int y){if(x < y) x = y;}
il void chkmin(int& x, int y){if(x > y) x = y;}
il void ADD(ll& x, ll y){x += y; ((x >= mod) ? x -= mod : 0ll);}
il void MUL(ll& x, ll y){x = x * y % mod;}

il ll qpow(ll x, int y){
  ll ret = 1;
  for(; y; y >>= 1, MUL(x, x)) if(y & 1) MUL(ret, x);
  return ret;
}
//#define int long long

int n, a[N], pre[N], suf[N]; 

struct Segtree{
  #define ls (o << 1)
  #define rs (o << 1 | 1)
  #define mid ((l + r) >> 1)
  int gd[N << 2];
  void pushup(int o){gd[o] = __gcd(gd[ls], gd[rs]);}
  void build(int o, int l, int r){
    if(l == r) return gd[o] = a[l], void();
    build(ls, l, mid); build(rs, mid + 1, r);
    pushup(o);
  }
  void modify(int o, int l, int r, int x, int v){
    if(l == r) return gd[o] = v, void();
    if(x <= mid) modify(ls, l, mid, x, v);
    else modify(rs, mid + 1, r, x, v);
    pushup(o);
  }
  int getval(int o, int l, int r, int s, int t){
    if(l == 0 || r == n + 1) return 0;
    if(s <= l && r <= t) return gd[o];
    int ret = 0;
    if(s <= mid) ret = __gcd(ret, getval(ls, l, mid, s, t));
    if(mid < t) ret = __gcd(ret, getval(rs, mid + 1, r, s, t));
    return ret;
  }
  int getL(int o, int l, int r, int v, int pi){
    if(__gcd(v, gd[o]) >= pi) return r + 1;
    if(l == r) return l; int L = __gcd(v, gd[ls]);
    if(L < pi) return getL(ls, l, mid, v, pi);
    else return getL(rs, mid + 1, r, L, pi);
  }
  int getR(int o, int l, int r, int v, int pi){
    if(__gcd(v, gd[o]) >= pi) return l - 1;
    if(l == r) return l; int R = __gcd(v, gd[rs]);
    if(R < pi) return getR(rs, mid + 1, r, v, pi);
    else return getR(ls, l, mid, R, pi);
  }
}tr;

void bf(){
  for(int i = 1; i <= n; i++) pre[i] = __gcd(pre[i - 1], a[i]);
  for(int i = n; i; i--) suf[i] = __gcd(suf[i + 1], a[i]);
  ll ans = pre[n];
  for(int i = 1; i < n; i++) ans += min(suf[i + 1], pre[i]);
  cout << ans << "\n";
}

struct Seg{
  int l, r, v;
}sl[N], sr[N];

void solve(){
  int l = 1, now = a[1], lt = 0, r, rt = 0;
  while(l <= n){
    r = tr.getL(1, 1, n, 0, now); 
    sl[++lt] = (Seg){l, r - 1, now}; now = tr.getval(1, 1, n, 1, r);
    l = r;
  } now = a[n], r = n; 
  while(r > 0){
    l = tr.getR(1, 1, n, 0, now);
    sr[++rt] = (Seg){l, r - 1, now}; now = tr.getval(1, 1, n, l, n);
    r = l;
  } ll ans = tr.getval(1, 1, n, 1, n);
  for(int i = 1; i <= lt; i++) for(int j = 1; j <= rt; j++){
    int L = max(sl[i].l, sr[j].l), R = min(sl[i].r, sr[j].r);
    if(L > R) continue;
    ans += 1ll * (R - L + 1) * min(sl[i].v, sr[j].v);
  } cout << ans << "\n";
}

signed main(){
  //freopen(".in", "r", stdin);
  //freopen(".out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int Q; cin >> n >> Q;
  for(int i = 1; i <= n; i++) cin >> a[i];
  tr.build(1, 1, n); solve();
  while(Q--){
    int x, y; cin >> x >> y;
    a[x] = y; tr.modify(1, 1, n, x, y); solve();
  }

  return 0;
}