「Ynoi2011」成都七中

    「Ynoi2011」成都七中

    Luogu P5311

    给出一棵包含 nn 个点的树,每个节点有一种颜色 cic_i。

    有 mm 次查询,每次查询给出三个参数 l,r,xl, r, x,表示询问只保留编号在 [l,r][l, r] 范围内的点时,xx 所在连通块的颜色种类数。

    数据范围:1≤n,m≤1051 \leq n, m \leq 10^5,1≤ci≤n1 \leq c_i \leq n,1≤l≤x≤r≤n1 \leq l \leq x \leq r \leq n。

    时空限制:11s / 250250MiB。

    Solution

    算法一:点分治

    考虑与 xx 在同一个连通块的节点 yy,显然要满足从 xx 到 yy 的简单路径上经过的所有点中,编号最小值 ≥l\geq l,编号最大值 ≤r\leq r。

    如果可以从 xx 只经过编号在 [l,r][l, r] 内的点到达 x′x',则询问 l,r,xl, r, x 可以等价于询问 l,r,x′l, r, x'(相当于从 x′x' 出发)。

    如果不能从 xx 只经过编号在 [l,r][l, r] 内的点到达 x′x',则整棵树可以被 x′x' 划分成若干个连通块,由于 xx 不能到达 x′x',故 xx 无法穿过 x′x' 到达其他的连通块。

    这启发我们进行点分治,对于当前的分治中心 rt\mathrm{rt},我们处理出 rt\mathrm{rt} 到达当前连通块每个点 ii 的简单路径上,编号最小值 lei\mathrm{le}_i 和编号最大值 rgi\mathrm{rg}_i。

    对于一个询问 l,r,xl, r, x,若可以从 rt\mathrm{rt} 只经过编号在 [l,r][l, r] 内的点到达 xx(即 l≤leil \leq \mathrm{le}_i 且 rgi≤r\mathrm{rg}_i \leq r),则询问 l,r,xl, r, x 相当于询问 l,r,rtl, r, \mathrm{rt};如果不能到达 xx,则当前连通块又被 rt\mathrm{rt} 划分成了若干个连通块,按照点分治的模式继续分治即可。

    现在的目标就是要解决询问 l,r,rtl, r, \mathrm{rt}。对于当前连通块内的一个点 ii,若满足 l≤leil \leq \mathrm{le}_i 且 rgi≤r\mathrm{rg}_i \leq r,则就会对答案有一个 coli\mathrm{col}_i 颜色的贡献。发现这可以简单地扫描线解决,不过多赘述。

    时间复杂度 O(nlog⁡2n+mlog⁡n)\mathcal{O}(n \log^2 n + m \log n)。

    #include <bits/stdc++.h>
    
    #define debug(a) std::cout << #a << "=" << (a) << ' '
    
    using s64 = long long;
    using u64 = unsigned long long;
    
    /* 取 min */
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    /* 取 max */
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    /* ----- ----- ----- 正文 ----- ----- ----- */
    
    const int N = 100100;
    
    int n, m;
    int col[N];
    
    struct Graph {
        std::vector< std::vector<int> > table;
    
        void init(int _n) {
            table.assign(_n + 1, {});
        }
    
        void add_edge(int u, int v) {
            table[u].push_back(v);
        }
    } G;
    
    int ban[N];
    
    int sz[N], mp[N];
    int tot_sz, tot_rt;
    
    void GetRoot(int u, int fu) {
        sz[u] = 1, mp[u] = 0;
        for (int v : G.table[u]) {
            if (v == fu || ban[v]) continue;
            GetRoot(v, u);
            sz[u] += sz[v];
            chmax(mp[u], sz[v]);
        }
        chmax(mp[u], tot_sz - sz[u]);
        if (tot_rt == 0 || mp[u] < mp[tot_rt]) tot_rt = u;
    }
    
    std::vector<int> seq;
    int le[N], rg[N];
    
    void find(int u, int fu) {
        seq.push_back(u);
    
        le[u] = rg[u] = u;
        if (fu) chmin(le[u], le[fu]), chmax(rg[u], rg[fu]);
    
        for (int v : G.table[u]) {
            if (v == fu || ban[v]) continue;
            find(v, u);
        }
    } 
    
    std::vector< std::tuple<int, int, int> > qry[N];
    int ans[N];
    
    int lst[N];
    
    namespace BIT {
        int c[N];
    
        void add(int x, int y) {
            for (; x <= n; x += x & -x) {
                c[x] += y;
            }
        }
    
        int ask(int x) {
            int ans = 0;
            for (; x; x -= x & -x) {
                ans += c[x];
            }
            return ans;
        }
    }
    
    void solve(int u) {
        ban[u] = 1;
    
        seq.clear();
        find(u, 0);
    
        std::vector< std::array<int, 3> > op;
        std::vector< std::array<int, 3> > qr;
    
        for (int x : seq) {
            op.push_back({rg[x], le[x], col[x]});
        }
    
        for (int x : seq) {
            for (auto &[l, r, id] : qry[x]) {
                if (id == -1) continue;
                if (l <= le[x] && rg[x] <= r) {
                    qr.push_back({r, l, id});
                    id = -1;
                }
            }
        }
    
        std::sort(op.begin(), op.end());
        std::sort(qr.begin(), qr.end());
    
        int t = 0;
        for (auto [r, l, id] : qr) {
            while (t < op.size() && op[t][0] <= r) {
                auto [_, x, c] = op[t ++];
                if (x > lst[c]) {
                    if (lst[c]) BIT::add(lst[c], -1);
                    BIT::add(x, +1);
                    lst[c] = x;
                }
            }
            ans[id] = BIT::ask(r) - BIT::ask(l - 1);
        }
    
        for (auto [y, x, c] : op) {
            if (lst[c]) {
                BIT::add(lst[c], -1);
                lst[c] = 0;
            }
        }
    
        for (int v : G.table[u]) {
            if (ban[v]) continue;
            tot_sz = sz[v], tot_rt = 0;
            GetRoot(v, u), solve(tot_rt);
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        std::cin >> n >> m;
    
        for (int i = 1; i <= n; i ++) {
            std::cin >> col[i];
        }
    
        G.init(n);
        for (int i = 1; i < n; i ++) {
            int x, y;
            std::cin >> x >> y;
    
            G.add_edge(x, y), G.add_edge(y, x);
        }
    
        for (int i = 1; i <= m; i ++) {
            int l, r, x;
            std::cin >> l >> r >> x;
    
            qry[x].push_back({l, r, i});
        }
    
        tot_sz = n, tot_rt = 0;
        GetRoot(1, 0), solve(tot_rt);
    
        for (int i = 1; i <= m; i ++) {
            std::cout << ans[i] << '\n';
        }
    
        return 0;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/

    算法二:Kruskal 重构树

    考虑与 xx 在同一个连通块的节点 yy,显然要满足从 xx 到 yy 的简单路径上经过的所有点中,编号最小值 ≥l\geq l,编号最大值 ≤r\leq r。

    考虑给树边赋上两种不同的权值。第一类权值设为两端点编号的较小值,则从 xx 到 yy 只能经过第一类权值 ≥l\geq l 的边;第二类权值设为两端点编号的较大值,则从 xx 到 yy 只能经过第二类权值 ≤r\leq r 的边。

    发现这两部分能到达的点集,都可以使用 Kruskal 重构树进行刻画。对第一类权值建 kruskal 最大生成重构树,对第二类权值建 kruskal 最小生成重构树。此时可以发现 xx 在两部分中能到达的点集,都是一棵子树。那么 xx 在原树上能到达的点集,就是这两棵子树的交集。那么现在的任务就是要对两棵子树的交集进行数颜色。

    对第一棵树进行 DSU on tree,维护第一棵子树内的点在第二棵树上的信息。现在还要考虑颜色去重的问题,对于一个颜色 cc,若其在第二棵树上有 x1,x2,…,xkx_1, x_2, \dots, x_k 这些点,那么颜色 cc 会对这些点到根节点的树链并有 11 的贡献。有一个经典的树上差分做法:将 x1,x2,…,xkx_1, x_2, \dots, x_k 按照 dfs 序排序。

    • 对于 1≤i≤k1 \leq i \leq k,令 xix_i 的差分数组 +1+1。
    • 对于 1≤i<k1 \leq i < k,令 LCA(xi,xi+1)\mathrm{LCA}(x_i, x_{i + 1}) 的差分数组 −1-1。

    对每种颜色记录一个 std::set,用于维护每种颜色所拥有节点的 dfs 序。每次插入或删除节点,考虑其与 dfs 序上的前驱后继产生的影响即可。

    时间复杂度 O(nlog⁡2n+mlog⁡n)\mathcal{O}(n \log^2 n + m \log n)。

    #include <bits/stdc++.h>
    
    #define debug(a) std::cout << #a << "=" << (a) << ' '
    
    using s64 = long long;
    using u64 = unsigned long long;
    
    /* 取 min */
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    /* 取 max */
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    /* ----- ----- ----- 正文 ----- ----- ----- */
    
    const int N = 100100;
    const int SIZE = N * 2;
    
    int n, m;
    int col[N];
    
    struct Edge {
        int x, y, z;
    } e[N];
    
    int fa[SIZE];
    int get(int x) {
        return fa[x] == x ? x : fa[x] = get(fa[x]);
    }
    
    struct Tree {
        int t;
        int val[SIZE];
        int son[SIZE][2], anc[18][SIZE];
        int dep[SIZE], sze[SIZE];
        int dfsClock, dfn[SIZE], idx[SIZE];
    
        void init() {
            t = n;
            for (int i = 1; i <= n * 2; i ++) {
                fa[i] = i;
            }
        }
    
        void dfs_init(int u, int fu) {
            dep[u] = dep[fu] + 1;
            sze[u] = 1;
            dfsClock ++, dfn[u] = dfsClock, idx[dfsClock] = u;
            if (u <= n) return;
            dfs_init(son[u][0], u), sze[u] += sze[son[u][0]];
            dfs_init(son[u][1], u), sze[u] += sze[son[u][1]];
        }
    
        int lca(int x, int y) {
            if (!x || !y) return 0;
            if (dep[x] > dep[y]) std::swap(x, y);
            for (int i = 17; i >= 0; i --)
                if (dep[x] <= dep[y] - (1 << i)) y = anc[i][y];
            if (x == y) return x;
            for (int i = 17; i >= 0; i --)
                if (anc[i][x] ^ anc[i][y]) x = anc[i][x], y = anc[i][y];
            return anc[0][x];
        }
    
        void deal() {
            dfs_init(t, 0);
            for (int j = 1; j <= 17; j ++) {
                for (int i = 1; i <= t; i ++) {
                    anc[j][i] = anc[j - 1][anc[j - 1][i]];
                }
            }
        }
    } T1, T2;
    
    void build1() {
        for (int i = 1; i < n; i ++) {
            e[i].z = std::min(e[i].x, e[i].y);
        }
        std::sort(e + 1, e + n, [&] (Edge lhs, Edge rhs) -> bool {
            return lhs.z > rhs.z;
        });
    
        T1.init();
    
        for (int i = 1; i < n; i ++) {
            auto [x, y, z] = e[i];
    
            int p = get(x), q = get(y);
    
            int u = ++ T1.t;
            T1.val[u] = z;
            T1.son[u][0] = p, T1.son[u][1] = q;
            T1.anc[0][p] = T1.anc[0][q] = u;
            fa[p] = fa[q] = u;
        }
    
        T1.deal();
    }
    
    void build2() {
        for (int i = 1; i < n; i ++) {
            e[i].z = std::max(e[i].x, e[i].y);
        }
        std::sort(e + 1, e + n, [&] (Edge lhs, Edge rhs) -> bool {
            return lhs.z < rhs.z;
        });
    
        T2.init();
    
        for (int i = 1; i < n; i ++) {
            auto [x, y, z] = e[i];
    
            int p = get(x), q = get(y);
    
            int u = ++ T2.t;
            T2.val[u] = z;
            T2.son[u][0] = p, T2.son[u][1] = q;
            T2.anc[0][p] = T2.anc[0][q] = u;
            fa[p] = fa[q] = u;
        }
    
        T2.deal();
    }
    
    std::set<int> g[N];
    
    namespace BIT {
        int c[SIZE];
    
        void add(int x, int y) {
            if (!x) return;
            for (; x <= T2.dfsClock; x += x & -x) {
                c[x] += y;
            }
        }
    
        int ask(int x) {
            int ans = 0;
            for (; x; x -= x & -x) {
                ans += c[x];
            }
            return ans;
        }
    
        int get(int x) {
            int l = T2.dfn[x], r = T2.dfn[x] + T2.sze[x] - 1;
            return ask(r) - ask(l - 1);
        }
    }
    
    void add(int x) {
        int c = col[x];
        auto it = g[c].lower_bound(T2.dfn[x]);
        int net = T2.idx[*it],
            pre = T2.idx[*std::prev(it)];
        BIT::add(T2.dfn[x], +1);
        BIT::add(T2.dfn[T2.lca(pre, x)], -1);
        BIT::add(T2.dfn[T2.lca(x, net)], -1);
        BIT::add(T2.dfn[T2.lca(pre, net)], +1);
        g[c].insert(T2.dfn[x]);
    }
    
    void dec(int x) {
        int c = col[x];
        auto it = g[c].lower_bound(T2.dfn[x]);
        int pre = T2.idx[*std::prev(it)],
            net = T2.idx[*std::next(it)];
        BIT::add(T2.dfn[x], -1);
        BIT::add(T2.dfn[T2.lca(pre, x)], +1);
        BIT::add(T2.dfn[T2.lca(x, net)], +1);
        BIT::add(T2.dfn[T2.lca(pre, net)], -1);
        g[c].erase(it);
    }
    
    std::pair<int, int> find(int l, int r, int x) {
        int p = x;
        for (int i = 17; i >= 0; i --) {
            if (T1.anc[i][p] && T1.val[T1.anc[i][p]] >= l) {
                p = T1.anc[i][p];
            }
        }
        int q = x;
        for (int i = 17; i >= 0; i --) {
            if (T2.anc[i][q] && T2.val[T2.anc[i][q]] <= r) {
                q = T2.anc[i][q];
            }
        }
        return {p, q};
    }
    
    std::vector< std::pair<int, int> > qry[SIZE];
    int ans[N];
    
    void change(int u, int opt) {
        if (u <= n) opt ? add(u) : dec(u);
        if (T1.son[u][0]) change(T1.son[u][0], opt);
        if (T1.son[u][1]) change(T1.son[u][1], opt);
    }
    
    void solve(int u) {
        if (u > n) {
            if (T1.sze[T1.son[u][0]] < T1.sze[T1.son[u][1]]) {
                std::swap(T1.son[u][0], T1.son[u][1]);
            }
            solve(T1.son[u][1]), change(T1.son[u][1], 0);
            solve(T1.son[u][0]), change(T1.son[u][1], 1);
        } else {
            add(u);
        }
    
        for (auto [v, id] : qry[u]) {
            ans[id] = BIT::get(v);
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        std::cin >> n >> m;
    
        for (int i = 1; i <= n; i ++) {
            std::cin >> col[i];
        }
    
        for (int i = 1; i < n; i ++) {
            int x, y;
            std::cin >> x >> y;
            e[i] = {x, y, 0};
        }
    
        build1();
        build2();
    
        for (int i = 1; i <= n; i ++) {
            g[i] = {0, T2.dfsClock + 1};
        }
    
        for (int i = 1; i <= m; i ++) {
            int l, r, x;
            std::cin >> l >> r >> x;
    
            auto [p, q] = find(l, r, x);
    
            qry[p].push_back({q, i});
        }
    
        solve(T1.t);
    
        for (int i = 1; i <= m; i ++) {
            std::cout << ans[i] << '\n';
        }
    
        return 0;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/