时间戳

首页 > 技术文章 > 【数据结构】树上莫队

【数据结构】树上莫队

purinliang 2021-03-16 17:27 原文

CF375D - Tree and Queries

题意：给定一棵 \(n(2\leq n\leq 10^5)\) 个结点的树，根结点为 \(1\) 号结点，每个结点有颜色 \(c(\leq c\leq 10^5)\) 。然后 \(m(1\leq m\leq 10^5)\) 次询问，每次询问给两个参数 \((v,k)\) ，询问 \(v\) 子树内，频次至少有 \(k\) 次的颜色有多少种。

题解：经典计数颜色的数量，使用莫队算法。不过这一次颜色的数量 \(k\) 不确定，也要作为一个维度进行转移。这一次查询的并非树链而是子树，所以结点出栈的时候不需要删除这个结点的信息。对每个询问给一个区间 \([fst[v],lst[v]]\) 查询频次至少有 \(k\) 次的颜色有多少种。考虑带修改的莫队算法，块的大小为 \(\sqrt[3]{nk}\) ，总复杂度为 \(O(\sqrt[3]{n^4k})\) 。但是实测表明开 \(\sqrt[2]{n}\) 更快，不知道原因是什么，可能和这里的区间并非任意指定有关（是dfs序的区间）。

namespace MoAlgorithmOnTree {

    static const int MAXM = 1e5 + 10;
    static const int MAXN = 1e5 + 10;
    static const int MAXC = 1e5 + 10;

    int n, m, BLOCK;
    vector<int> G[MAXN];
    int id[MAXN], idt, fst[MAXN], lst[MAXN];

    void dfs(int u, int p) {
        id[++idt] = u;
        fst[u] = lst[u] = idt;
        for (int v : G[u]) {
            if (v == p)
                continue;
            dfs(v, u);
            lst[u] = lst[v];
        }
    }

    struct Node {
        int l, r, k, id;
        bool operator<(const Node &node) const {
            if (l / BLOCK != node.l / BLOCK)
                return l < node.l;
            if (r / BLOCK != node.r / BLOCK)
                return r < node.r;
            return k < node.k;
        }
    } node[MAXM];
    ll ans[MAXM];

    int L, R, K;
    ll curans;

    int c[MAXN], cnt[MAXC], sum[MAXN];

    void add(int x) {
        --sum[cnt[c[id[x]]]];
        ++cnt[c[id[x]]];
        ++sum[cnt[c[id[x]]]];
        if (cnt[c[id[x]]] == K)
            ++curans;
    }

    void sub(int x) {
        if (cnt[c[id[x]]] == K)
            --curans;
        --sum[cnt[c[id[x]]]];
        --cnt[c[id[x]]];
        ++sum[cnt[c[id[x]]]];
    }

    void addK() {
        curans -= sum[K];
        ++K;
    }

    void subK() {
        --K;
        curans += sum[K];
    }

    void Solve() {
        ms(cnt), ms(sum);
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
            G[i].clear();
        for (int i = 1; i <= n; ++i)
            scanf("%d", &c[i]);
        for (int i = 1; i <= n - 1; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].eb(v);
            G[v].eb(u);
        }
        idt = 0;
        dfs(1, 0);
        BLOCK = (int)ceil(pow(n, 0.667));
        for (int i = 1; i <= m; ++i) {
            int v, k;
            scanf("%d%d", &v, &k);
            node[i].l = fst[v];
            node[i].r = lst[v];
            node[i].k = k;
            node[i].id = i;
        }
        sort(node + 1, node + 1 + m);
        L = 1, R = 0, K = 0, curans = n, sum[0] = n;
        for (int i = 1; i <= m; ++i) {
            while (L > node[i].l)
                --L, add(L);
            while (R < node[i].r)
                ++R, add(R);
            while (L < node[i].l)
                sub(L), ++L;
            while (R > node[i].r)
                sub(R), --R;
            while (K < node[i].k)
                addK();
            while (K > node[i].k)
                subK();
            ans[node[i].id] = curans;
        }
        for (int i = 1; i <= m; ++i)
            printf("%lld\n", ans[i]);
    }

};

但是换一种思路，其实K没有必要作为其中一个维度，不过就不再维护curans，或者说，curans是一个数组，curans[i]表示频次大于等于i的颜色数。考虑一种颜色频次从cnt增加到cnt+1时，只会让大于等于cnt+1的答案+1，对于大于等于cnt其实是没有变化的。

这道题也可以树上启发式合并做。

推荐阅读