P12003 在小小的奶龙山里面挖呀挖呀挖（加强版）题解

暴力莫队草过去了。

首先你分解质因数，那么每个数只有

\log

个质因数，然后再用树上莫队。复杂度是

O(n \sqrt n \log V)

的，这样就做完了。

但是写完你发现全炸了而且死得很惨。

我们发现莫队的瓶颈在于指针的移动，但是这样做我们只能做到单次

O(\log V)

的慢速指针移动，这个

\log

无论如何是放不到根号里面的。

复杂度不会优化怎么办？你考虑卡常。

你发现你之前用 vector 存了每个点的质因数，这样很慢。

你在括号序上求质因数，而不是在原来的点上求，同时你把这一堆质因数放到同一个 vector 里，括号序上每个位置存对应的区间。这样莫队指针移动访问的内存就是连续的！这样做就是对的！！！

https://www.luogu.com.cn/record/210964459

CPP

#include <algorithm>
#include <cmath>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
const int N = 3e5 + 5, V = 1e8 + 5, V0 = 5761456;
int n, m, a[N], st[N], ed[N], b[N * 2], f[N][19], dep[N], p[V0], pre[V], pl[N * 2], pr[N * 2],
    val[V0], ans[N], siz, idx, cnt, l = 1, r, cur;
bool vis[N], flg[V];
vector<int> G[N], P;
struct query {
    int l, r, lca, id;
    inline bool operator<(const query &x) const {
        if (l / siz != x.l / siz) return l < x.l;
        return l / siz & 1 ? r < x.r : r > x.r;
    }
} q[N];
inline void add(int u, int v) { G[u].push_back(v); }
inline void addedge(int u, int v) { add(u, v), add(v, u); }
inline void dfs(int u, int fa) {
    b[st[u] = ++idx] = u, f[u][0] = fa, dep[u] = dep[fa] + 1;
    for (int i = 1; i < 19; i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for (int v : G[u])
        if (v != fa) dfs(v, u);
    b[ed[u] = ++idx] = u;
}
inline int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 18; i >= 0; i--)
        if (dep[f[u][i]] >= dep[v]) u = f[u][i];
    if (u == v) return u;
    for (int i = 18; i >= 0; i--)
        if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}
inline void insl(int u) {
    for (int i = pl[u]; i < pr[u]; i++) cur += !val[P[i]]++;
}
inline void dell(int u) {
    for (int i = pl[u]; i < pr[u]; i++) cur -= !--val[P[i]];
}
inline void updl(int u) { (vis[b[u]] ^= true) ? insl(u) : dell(u); }
inline void insr(int u) {
    for (int i = pr[u] - 1; i >= pl[u]; i--) cur += !val[P[i]]++;
}
inline void delr(int u) {
    for (int i = pr[u] - 1; i >= pl[u]; i--) cur -= !--val[P[i]];
}
inline void updr(int u) { (vis[b[u]] ^= true) ? insr(u) : delr(u); }
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m, siz = n * 2 / sqrt(m);
    for (int i = 2; i <= 1e8; i++) {
        if (!flg[i]) p[++cnt] = i, pre[i] = cnt;
        for (int j = 1; j <= cnt && i * p[j] <= 1e8; j++) {
            flg[i * p[j]] = true;
            pre[i * p[j]] = j;
            if (!(i % p[j])) break;
        }
    }
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v; i < n; i++) cin >> u >> v, addedge(u, v);
    dfs(1, 0);
    for (int i = 1; i <= idx; i++) {
        pl[i] = P.size();
        int x = a[b[i]];
        while (x != 1) {
            int y = pre[x];
            P.push_back(y);
            while (pre[x] == y) x /= p[y];
        }
        pr[i] = P.size();
    }
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        if (st[u] > st[v]) swap(u, v);
        int l = lca(u, v);
        if (l == u) q[i] = {st[u], st[v], 0, i};
        else q[i] = {ed[u], st[v], st[l], i};
    }
    sort(q + 1, q + m + 1);
    for (int i = 1; i <= m; i++) {
        while (l > q[i].l) updr(--l);
        while (r < q[i].r) updl(++r);
        while (l < q[i].l) updl(l++);
        while (r > q[i].r) updr(r--);
        if (q[i].lca) updr(q[i].lca);
        ans[q[i].id] = cur;
        if (q[i].lca) updr(q[i].lca);
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}

P12003 在小小的奶龙山里面挖呀挖呀挖（加强版）题解

文章操作

相关推荐

评论

P12003 在小小的奶龙山里面挖呀挖呀挖（加强版）题解