经典种树

· · 题解

本题其实就是 P1484 种树。

因为需要进行到询问包含结点区间或者与结点区间相离，所以每一个区间询问 [l,r] 都相当于将至多三个区间 [1,l-1]、[l,r]、[r+1,n] 分成若干个结点区间的并——这些结点就是访问到的结点——且每个区间分成的并中都不包含任何一对兄弟结点（这些结点不会是访问到的结点，因为访问会在它们的某个祖先结点处终止）。

线段树中，如果有从未访问到的结点，那么就一定是那些在任何询问中，都处于同一个区间中的下标构成的区间。所以，为了讨论访问到的结点的最小深度，不妨将这些从不分离的连续的下标段看作是一个下标。做了这样的简化后，线段树中所有结点都会访问到，且结点的总数目就是简化后的下标数目。

要让最深的结点深度最浅，只能是尽量构造为满二叉树。

设简化后，下标数目为 c，能存下这些下标的二叉树深度为 d，那么，最深一层应该有 m=c-2^{d-1} 对叶子结点。

访问一对叶子节点 a 和 a+1 时，就意味着前文所述三个区间中相邻的某两个中，左侧那个的右端点和右侧那个的左端点分别为 a 和 a+1。

不妨将讨论的对象设为 a 和 a+1 之间的连接处。有 m 对叶子结点意味着需要访问 m 个这样的连接处。总共有 c-1 个可能的连接处。每选择一个连接处的成本就是前文计算出的它的访问次数乘以二。选择出的两个连接处不能相邻。这基本就是 P1484 种树 的结构。

然后，模拟费用流、反悔贪心、WQS 二分，随便选，最终复杂度是 O(q+n\log n) 的。对数里的项可能会随着具体的方法而不同，不过总是对数的。

提供一个 WQS 二分的核心代码：

// Find the maximum of unimodel function F.
// The domain of F must be consecutive integer values.
template <std::integral T, typename F> 
auto golden_section_search(T ll, T rr, F func) {
    constexpr long double phi = (std::sqrt(5.0l) - 1) / 2;
    T ml = ll + (rr - ll) * (1 - phi);
    T mr = ll + (rr - ll) * phi;
    auto fl = func(ml), fr = func(mr);
    while (ml < mr) {
        if (fl > fr) {
            rr = mr;
            mr = ml;
            fr = fl;
            ml = ll + (rr - ll) * (1 - phi);
            fl = func(ml);
        } else {
            ll = ml;
            ml = mr;
            fl = fr;
            mr = ll + (rr - ll) * phi;
            fr = func(mr);
        }
    }
    for (auto i = ll; i <= rr; ++i) {
        auto fi = func(i);
        if (fi > fr) {
            fr = fi;
            mr = i;
        }
    }
    return std::pair(mr, fr);
};

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n + 1);
    for (; q; --q) {
        int l, r;
        std::cin >> l >> r;
        ++a[l - 1];
        ++a[r];
    }
    int cnt = 0;
    for (int i = 1; i < n; ++i) {
        cnt += a[i] > 0;
    }
    if (!cnt) {
        std::cout << 0 << ' ' << a[0] << std::endl;
    } else {
        int d = 0;
        for (; (1 << d) < cnt + 1; ++d);
        int m = cnt + 1 - (1 << (d - 1));
        std::vector c(cnt + 1, 0);
        for (int i = 1, j = 0; i < n; ++i) {
            if (a[i]) {
                c[++j] = a[i];
            }
        }
        n = cnt;
        auto solve = [&](int k) -> long long {
            long long dp[2] = { 0, 0x3f3f3f3f3f3f3f3f };
            for (int i = 1; i <= n; ++i) {
                std::tie(dp[0], dp[1]) = std::make_pair(
                    std::min(dp[0], dp[1]),
                    dp[0] + c[i] - k
                );
            }
            return std::min(dp[0], dp[1]);
        };
        auto [k, v] = golden_section_search(0, 10000000, [&](int k) -> long long {
            return solve(k) + (long long)k * m;
        });
        std::cout << d << ' ' << (v << 1) << std::endl;
    }
    return 0;
}