[CF2148G] Farmer John's Last Wish

题目

CF2148G。

思路

首先我们注意到，设 $G_k=\gcd(a_1,a_2,\dots,a_k)$，那么 $G_{k+1}=\gcd(G_k,a_{k+1})\mid G_{k}$。

根据 $\gcd$ 的性质，一定有 $G_{k+1}\le G_k$，那么如果 $G_{k+1}\neq G_k$ 就满足 $G_{k+1}<G_k$ 了。

可以从枚举因子 $d$ 的角度思考，因为如果 $i=1,2,\dots,k+1$ 时，都有 $d\mid a_i$，那么就有 $d\mid G_{k+1}\mid G_{k}$。

可以从集合的角度来考虑，如果设 $S_k$ 表示 $G_k$ 的质因数分解后构成的多重集，那么 $G_{k+1}\mid G_k$ 就相当于 $S_{k+1}\subset S_k$，那我们只需要判断是否 $\complement_{S_k}S_{k+1}\neq \varnothing$。

如果 $S_{k+1}\neq S_k$，那么就一定存在一个 $d$，使它质因数分解构成的多重集 $S$ 满足 $S\subset S_{k}$ 但是 $S$ 中含有 $\complement_{S_k}S_{k+1}$ 中的元素，于是 $\complement_{S_k}S_{k+1}\neq \varnothing$。

反之，如果存在一个 $d$，使得 $d\mid G_k$ 但是 $d\not\mid G_{k+1}$，就说明 $S\not\subset S_{k+1}$ 且 $S,S_{k+1}\subset S_k$，那么就一定有 $S_{k+1}\neq S_k$，即 $G_{k+1}\neq G_k$。

因此，我们只需要找到这样一个 $d$，在前缀长度为 $n$ 的数字中，它的倍数数量 $k\le n-1$ 时，就可以把这 $k$ 个数排在前面，使得 $d\mid G_k$ 且 $d\not\mid G_{k+1}$。

该如何维护倍数数量？朴素地做法是：

$$f(d)=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \operatorname{cnt}(id)$$

反过来，如果我们每加入一个数字 $a_i$，都去更新 $f(1)\sim f(n)$，那么更新次数最坏是 $d(a_i)$，它的上界是 $100$ 的数量级。

我们的目标是找到 $f(1)\sim f(n)$ 中最大的并且 $\le n-1$ 的那个数字，容易知道最大值可能是 $n$，所以我们需要记录最大值和次大值。

线段树维护即可，复杂度 $O(nd(a_i)\log n)$。

实现

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define Mid ((L+R) >> 1)
#define ls (u<<1)
#define rs (u<<1|1)
const int N = 2e5+10, INF = 2e9;
vector<int> d[N];

int mx1[N<<2], mx2[N<<2];
int leaf[N];

void pushup(int u) {
    if (mx1[ls] == mx1[rs]) {
        mx1[u] = mx1[ls];
        mx2[u] = max(mx2[ls], mx2[rs]);
    }
    else if (mx1[ls] < mx1[rs]) {
        mx1[u] = mx1[rs];
        mx2[u] = max(mx2[rs], mx1[ls]);
    }
    else {
        mx1[u] = mx1[ls];
        mx2[u] = max(mx1[rs], mx2[ls]);
    }
}

void build(int u, int L, int R) {
    if (L == R) return mx1[u] = 0, mx2[u] = -INF, leaf[L] = u, void();
    build(ls, L, Mid);
    build(rs, Mid+1, R);
    pushup(u);
}

void modify(int p) {
    int u = leaf[p];
    mx1[u]++;
    while (u >>= 1) pushup(u);
}

void solve() {
    int n;
    cin >> n;
    build(1, 1, n);
    for (int p = 1, a; p <= n; p++) {
        cin >> a;
        for (int k: d[a]) modify(k);
        int ans = 0;
        if (mx1[1] <= p-1) ans = mx1[1];
        else ans = mx2[1];
        if (ans < 0) ans = 0;
        cout << ans << " \n"[p == n];
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    for (int i = 2; i < N; i++) {
        for (int j = i; j < N; j += i) {
            d[j].pb(i);
        }
    }

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}