P3180 [HAOI2016]地图 题解

· · 题解

题意

给定一个 n 个点 m 条边的仙人掌 (1\le n\le 10^5, n-1\le m\le 1.5\cdot10^5)，定义 u 的子仙人掌为去掉 u 到 1 的所有简单路径经过的街道后 u 所在的连通块。每个点有点权，q (1\le q\le 10^5) 次询问一个点的子仙人掌中出现次数为奇数/偶数的点权个数。

题解

进行一遍 dfs， 对于每个环，删掉其中的所有边并从其中 dfs 序最小的点向环上其他所有点连边。容易发现，进行这样的操作后原图变成了一棵树，且这个树上 u 的子树所包含的点与原图中 u 的子仙人掌所包含的点相同。问题转化为了子树询问，因此线段树合并即可。

时间复杂度：O((n+q)\log n+m)。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
struct Node {
    Node *lc, *rc;
    int cnt[2];
    Node(Node *lc = nullptr, Node *rc = nullptr, int c0 = 0, int c1 = 0) : lc(lc), rc(rc), cnt{c0, c1} {}
};
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    auto values = a;
    std::sort(values.begin(), values.end());
    values.erase(std::unique(values.begin(), values.end()), values.end());
    for (auto &i : a)
        i = std::lower_bound(values.begin(), values.end(), i) - values.begin();
    std::vector<std::vector<int>> e(n);
    std::vector<int> parent(n, -1), dep(n, -1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u;
        --v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dep[0] = 0;
    std::function<void(int)> dfs = [&](int u) {
        for (auto v : e[u]) {
            if (v == parent[u])
                continue;
            if (dep[v] == -1) {
                parent[v] = u;
                dep[v] = dep[u] + 1;
                dfs(v);
            } else if (dep[v] > dep[u]) {
                for (auto i = v; i != u; )
                    std::tie(i, parent[i]) = {parent[i], u};
            }
        }
    };
    dfs(0);
    for (int i = 0; i < n; ++i)
        e[i].clear();
    for (int i = 1; i < n; ++i)
        e[parent[i]].push_back(i);
    std::vector<Node *> root(n);
    std::function<Node *(int, int, int)> insert = [&](int l, int r, int v) {
        if (r - l == 1)
            return new Node(nullptr, nullptr, 0, 1);
        int m = (l + r) / 2;
        if (v < m) {
            return new Node(insert(l, m, v), nullptr, 0, 1);
        } else {
            return new Node(nullptr, insert(m, r, v), 0, 1);
        }
    };
    for (int i = 0; i < n; ++i)
        root[i] = insert(0, values.size(), a[i]);
    std::function<Node *(Node *, Node *)> merge = [&](Node *p, Node *q) {
        if (p == nullptr)
            return q;
        if (q == nullptr)
            return p;
        if (p -> lc == nullptr && p -> rc == nullptr) {
            int c = (p -> cnt[1] + q -> cnt[1]) % 2;
            return new Node(nullptr, nullptr, c == 0, c == 1);
        }
        Node *r = new Node(merge(p -> lc, q -> lc), merge(p -> rc, q -> rc));
        if (r -> lc != nullptr) {
            r -> cnt[0] += r -> lc -> cnt[0];
            r -> cnt[1] += r -> lc -> cnt[1];
        }
        if (r -> rc != nullptr) {
            r -> cnt[0] += r -> rc -> cnt[0];
            r -> cnt[1] += r -> rc -> cnt[1];
        }
        return r;
    };
    std::function<void(int)> dfs1 = [&](int u) {
        for (auto v : e[u]) {
            dfs1(v);
            root[u] = merge(root[u], root[v]);
        }
    };
    dfs1(0);
    std::function<int(Node *, int, int, int, int)> query = [&](Node *p, int l, int r, int b, int v) {
        if (l >= b || p == nullptr)
            return 0;
        if (r <= b)
            return p -> cnt[v];
        int m = (l + r) / 2;
        return query(p -> lc, l, m, b, v) + query(p -> rc, m, r, b, v);
    };
    int q;
    std::cin >> q;
    while (q--) {
        int v, u, b;
        std::cin >> v >> u >> b;
        --u;
        b = std::upper_bound(values.begin(), values.end(), b) - values.begin();
        std::cout << query(root[u], 0, values.size(), b, v) << "\n";
    }
    return 0;
}