CF1516D 题解

· · 个人记录

一个非倍增的做法。

考虑如何处理一个询问。显然一个区间合法的充要条件是其中不能出现两个拥有相同质因子的数。由此，右端点一定时左端点越靠右答案越优。进一步想到贪心策略：从左端点起向右找到最靠右的合法右端点，以这两个端点作为一个区间，然后考虑下一个数。重复直到到达右端点。

因此，对于一个固定的点 r，我们可以利用 dp 来快速解决以其为右端点的询问。令 f_l 表示区间 [l,r] 最优划分时的区间个数，则可有状态转移 f_i=1+f_{j+1}，其中 j 的意义为以 i 为左端点时最远的合法右端点。为了方便，我们令 j \leq n+1，同时令 \forall k > r, f_k = 0。

不难发现 r 改变时每个点的最大合法右端点（以下简称后继）不变。同时，每个点具有唯一后继。这样，状态转移其实就可以视作一棵以 n+1 为根节点的树，每个非根节点的答案等于其父节点答案 +1。那么我们就可以离线询问，按照 r 从小到大排序，同时维护一个指针，加入一个右端点时其 f 值由 0 变为 1，其子树内所有节点的 f 值也要加一，可以用 dfs 序 + 树状数组维护。

复杂度 O(n\sqrt n + nlogn)，可以用调和级数优化到 O(nlogn)，但代码里是根号分解。

代码如下：

#include<bits/stdc++.h>
#define ep emplace
#define eb emplace_back

using namespace std;

const int MAXN = 1e5 + 10;

int n, Q; 
int a[MAXN];
vector<int> to[MAXN];
int L[MAXN], R[MAXN], idx;
struct BITree {
    int a[MAXN];
    #define lowbit(x) ((x) & (-(x)))
    void add(int x, int k) {
        for (int i = x; i <= n + 1; i += lowbit(i))
            a[i] += k;
        return;
    }
    int query(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i))
            res += a[i];
        return res;
    }
} tr;
vector<int> spl[MAXN];
struct Query {
    int id, l, r, ans;
} q[MAXN];
vector<int> v[MAXN];

void dfs(int x) {
    L[x] = ++idx;
    for (int y : to[x]) dfs(y);
    R[x] = idx;
    return;
}
vector<int> split(int x) {
    vector<int> v;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            v.eb(i);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) v.eb(x);
    return v;
}

int main() {
    ios:: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> Q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i)
        spl[i] = split(a[i]);
    int nowans = n + 1;
    for (int i = n; i; --i) {
        for (auto j : spl[i]) {
            v[j].eb(i);
            if (v[j].size() > 1) nowans = min(nowans, v[j][v[j].size() - 2]);
        }
        to[nowans].eb(i);
    }
    for (int i = 1; i <= Q; ++i) {
        q[i].id = i;
        cin >> q[i].l >> q[i].r;
    }    
    sort(q + 1, q + Q + 1, [] (Query x, Query y) { return x.r < y.r; });
    dfs(n + 1);
    int now = 1;
    for (int i = 1; i <= Q; ++i) {
        int l = q[i].l, r = q[i].r;
        while (now <= r) {
            assert(L[now]);
            tr.add(L[now], 1), tr.add(R[now] + 1, -1), ++now;
        }
        q[i].ans = tr.query(L[l]);
    }
    sort(q + 1, q + Q + 1, [] (Query x, Query y) { return x.id < y.id; });
    for (int i = 1; i <= Q; ++i)
        cout << q[i].ans << endl;
    return 0;
}