[Easy] QOJ9543 Good Partitions

简要题意

给定一个长度为 $n$ 的序列 $a$。

定义一个数 $k$ 是好的，当且仅当 $\forall i\in[1,\left\lceil \frac{n}{k} \right\rceil],a_{(i-1)k+1}\leq a_{(i-1)k+2}\leq \cdots \leq a_{\min(n,ik)}$。

有 $q$ 次操作，每次操作给出 $p,v$，将 $a_p$ 变为 $v$。在所有操作前以及每次操作后，输出 $[1,n]$ 中好的数的数量。

$T$ 组数据。$1\leq \sum n,\sum q\leq 2\times 10^5,1\leq a_i\leq 2\times 10^9$。

思路

考虑好的数有什么性质。对于 $a_i>a_{i+1}$，那么 $a_i,a_{i+1}$ 必须分到题意中不同的段中，换句话说 $i$ 必须是好的数的倍数。换句话说如果能够求出所有形如 $a_i>a_{i+1}$ 的 $i$ 的 gcd，那么答案就是这个 gcd 的因子个数。

于是我们需要一个数据结构，支持插入一个数，删除一个数，查询所有数的 gcd。由于插入删除 $i$ 可以看成在 $i$ 处单点修改，而 $\gcd$ 又满足结合律，因此可以用线段树维护。时间复杂度 $O((n+q)\log n)$。

代码

#include <bits/stdc++.h>
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;

const int N = 2e5 + 5;

template<int N>
struct sgt {
    int t[N << 2];
    void update(int p, int v, int i, int l, int r){
        if(l > r) return;
        if(l == r) return t[i] = v, void();
        if(p <= mid) update(p, v, ls, l, mid);
        else update(p, v, rs, mid + 1, r);
        t[i] = __gcd(t[ls], t[rs]);
    }
    void build(function<int(int)> f, int i, int l, int r){
        if(l > r) return;
        if(l == r) return t[i] = f(l), void();
        build(f, ls, l, mid), build(f, rs, mid + 1, r);
        t[i] = __gcd(t[ls], t[rs]);
    }
};

sgt<N> t;
int n, q, a[N], d[N];

void solve(){
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> a[i];
    d[0] = n;
    t.build([](int i){
        return a[i] > a[i + 1] ? i : 0;
    }, 1, 1, n - 1);
    cout << d[t.t[1]] << '\n';
    while(q--){
        int p, v; cin >> p >> v;
        a[p] = v;
        if(p < n) t.update(p, a[p] > a[p + 1] ? p : 0, 1, 1, n - 1);
        if(p > 1) t.update(p - 1, a[p - 1] > a[p] ? p - 1 : 0, 1, 1, n - 1);
        cout << d[t.t[1]] << '\n';
    }
}

void init(int n){
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j+=i) d[j]++;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; cin >> t, init(2e5);
    while(t--) solve();
    return 0;
}

// Written by xiezheyuan