牛客练习赛122E-外向树

题意分析

$\qquad$ 首先不难得出，所有要加的边直接往1连就行了，因为1能到任何点，连接了1就连接了万物。然后再分析一下究竟是哪些点之间不能互通，就可以得出只有出度0的点必须要建边，不然就是死胡同。所以原题就变成求编号在 $[l,r]$ 这个区间的点建成虚树上有多个点是虚树的叶子，或者说有多少个点在啊 $[l,r]$ 范围内没有子孙。

解题思路1( ${n\cdot log^2(n)}$ )

$\qquad$ 显然直接去建虚树是没前途，首先解决一下如何 $O(1)$ 查询单个点 $u$ 在 $[l,r]$ 是否有子孙。通过常人都有的注意力观察题目输入的约束。易得出这种 $[l,r]$ s输入形式是有单调性，假设一个点 $u \in [l,r][$ 在 $[l,r]$ 有子孙，那么在更大区间 $[l-d1,r+d2]$ 也是一定有子孙的，其中 $d1,d2>=0$ 。所以要判断 $u$ 是否有子孙只要判断其编号最近子孙的位置即可。所以只要能预处理出每个点编号相邻的两个子孙就行了。

$\qquad$ 这里借用一下隔壁题解符号，令点 $u$ 的子孙中和编号最接近的两个结点编号是 $prev(u)$ 和 $succ(u)$ 其中 $prev(u)<u<succ(u))$ .那么就是判断 $[l,r]$ 是否包含 $[prev(u),u]和[u,succ(u)]$ 中的任意一个。

$\qquad$ 要快速预处理出 $prev$ 和 $succ$ 数组一个暴力好想又好写常数又小的做法就是用一个set记下每个子树的点集，然后计算父亲的点集时直接启发式暴力合并所有孩子的子树点集，然后查询 $u$ 在set中的位置就可以用set的迭代器拿到prev(u)和succ(u)，算法复杂度是 ${n\cdot log^2(n)}$ ).这里推荐看神犇 @Heltion 的代码

$\qquad$ 然后再来分析一下怎么批量解决一个区间的查询，不难发现要查询多少个在 $[l,r]$ 中有子孙，就是求满足如下约束条件的 $u$ 有多少个:

$\{prev(u),u\} \in [l,r]\land \{succ(u),u\} \in [l,r]$ ，

写成不等式约束就是

$(l\le prev(u) \land u\le r) \lor ( l\le u \land succ(u)\le r)$

$\qquad$ 这个形式一看就是最基础的二维偏序，我们直接转换成二维坐标，并直接通过容斥把逻辑或去掉即可。具体操作如下设点 $(prev(u),u)$ 的权值为1， $(u,succ(u))$ 权值为1， $(prev(u), succ(u))$ 的权值为-1，查询转化成计算满足 $x\ge l$ l且 $y\le r$ 的范围内点 $(x,y)$ 的权和。直接一个树状数组或者线段树就可以在 $O(n\cdot log(n))$ 完成查询.具体代码还是参见上面那份Heltion的代码

解题思路2( ${n\cdot log(n)}$ )

$\qquad$ 在解题思路1中我们的复杂度瓶颈在与预处理 $prev(u)$ 和 $succ(u)$ ，能不能更快的预处理呢。以 $prev(u)$ 例，学过的图论的同学都知道子树可以表示成欧拉序上的一段区间，设点 $u$ 进入子树时间为 $in[u]$ 退出子树时间为 $out[u]$ ,那么其实 $prev(u)$ 可以写成如下形式。

$prev(u)=max(\{v | v <u \land in[u]\le in[v]\le out[u]\})$

差分一下对同一个变量的上下界约束可得：

$prev(u)=max(\{v | v <u \land in[v]\le out[u]\} - \{v | v <u \land in[v] < in[u]\})$

这一眼就可以看出来又是二维偏序。因为是max操作就必须建线段树了。然后就写完了

#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <iostream>
#include <iomanip>
#include <cassert>

using namespace std;
const int maxn = 1e5 + 4;
vector<int> e[maxn];
vector<pair<int, int>> w[maxn];
int in[maxn];
int out[maxn];
int lch[maxn];
int rch[maxn];
int ans[maxn];
int a[10000];
vector<int> que;

template<typename T>
/**
 * 静态结构线段树，所有操作不递归，支持对区间[l,r]的查询，其中1<=l<=r<size
 * @tparam T 结点类型，结点需要支持+运算符
 */
struct SegmentTree {
    int size{};
    vector<T> node;

    SegmentTree() : size(0) {}

    void build(int n) {
        size = 1;
        while (size <= n) size <<= 1;
        vector<T>(size * 2).swap(node);// 清空并缩/扩容
    }

    void build(const vector<T> &arr) {
        build(arr.size() - 1);
        ///把数组铺在底层,注意线段树里数组下标从1开始. arr[0]必须无用
        copy(arr.begin() + 1, arr.end(), node.begin() + size + 1);
        for (int i = size - 1; i > 0; i--) {
            node[i] = node[i * 2] + node[i * 2 + 1];
        }
    }

    void modify(int idx, const T &v) {
        assert(0 < idx && idx < size);
        idx += size;
        node[idx] = v;
        while (idx > 1) {
            idx >>= 1;
            node[idx] = node[idx * 2] + node[idx * 2 + 1];
        }
    }

    T &get(int idx) {
        return node[idx + size];
    }

    T query(int l, int r) {
        assert(0 < l && r < size);
        l += size - 1;
        r += size + 1;
        T lans{}, rans{};
        for (; l ^ r ^ 1; l >>= 1, r >>= 1) {
            if (~l & 1) lans = lans + node[l ^ 1];
            if (r & 1) rans = node[r ^ 1] + rans;
        }
        return lans + rans;
    }

    void print() { //打印树结构
        int j = 1, s = size * 4, k, len = 3;///len：每个要输出的数值的长度
        for (int i = 1; i <= 2 * size - 1; i++) {
            if (i == j) {
                cout << endl;
                j <<= 1;
                s >>= 1;
                for (k = 0; k < len * (s / 2 - 1); k++)
                    cout << " ";
            }
            cout << setw(len) << node[i];
            for (k = 0; k < len * (s - 1); k++)
                cout << " ";
        }
        cout << endl;
    }
};

int dfs(int u, int fa) {
    que.push_back(u);
    in[u] = (int) que.size();
    for (auto v: e[u]) {
        if (v != fa) {
            dfs(v, u);
        }
    }
    out[u] = (int) que.size();
    return 0;
}


struct MaxV {
    int v{};

    MaxV() : v(0) {}

    explicit MaxV(int v) { this->v = v; }

    MaxV operator+(const MaxV &other) const {
        return MaxV(max(v, other.v));
    }
};

int sovle() {
    int n, m, i, j, k, x, y;
    SegmentTree<MaxV> max_tree;
    scanf("%d%d", &n, &m);
    max_tree.build(n);
    for (i = 1; i < n; i++) {
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1, 1);
    for (i = 1; i <= n; i++) {
        auto ch = max_tree.query(in[i], out[i]);// 查询子树的最大编号
        if (ch.v) {
            lch[i] = ch.v;
            w[lch[i]].emplace_back(i, 1);
        }
        max_tree.modify(in[i], MaxV(i));
    }
    max_tree.build(n);
    for (i = n; i >= 1; i--) {
        auto ch = max_tree.query(in[i], out[i]);// 查询子树的最小编号
        if (ch.v) {
            rch[i] = n + 1 - ch.v;
            w[i].emplace_back(rch[i], 1);
            if (lch[i]) {
                w[lch[i]].emplace_back(rch[i], -1);
            }
        }
        max_tree.modify(in[i], MaxV(n + 1 - i));
    }
    vector<tuple<int, int, int>> q;
    for (i = 0; i < m; i++) {
        scanf("%d%d", &x, &y);
        if (x == y) {
            ans[i] = 0;
        } else {
            ans[i] = y - x + 1;
            q.emplace_back(x, y, i);
        }
    }

    sort(q.begin(), q.end());
    SegmentTree<int> sum_tree;
    sum_tree.build(n);
    for (i = n; i >= 1; i--) {
        for (auto [r, v]: w[i]) {
            sum_tree.modify(r, sum_tree.get(r) + v);
        }
        while (!q.empty() && get<0>(q.back()) == i) {
            ans[get<2>(q.back())] -= sum_tree.query(1, get<1>(q.back()));
            q.pop_back();
        }
    }
    for (i = 0; i < m; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

int main() {
    int t = 1;
//    scanf("%d", &t);
    while (t--) {
        sovle();
    }
    return 0;

}

题解 | #E-外向树#

牛客练习赛122E-外向树

题意分析

解题思路1()

解题思路2()

解题思路1( ${n\cdot log^2(n)}$ )

解题思路2( ${n\cdot log(n)}$ )