Cutting Bamboos - 题解

标签与难度

标签: 可持久化线段树, 主席树, 数据结构, 二分查找, 区间查询 难度: 2200

题目大意喵~

主人你好呀，这道题是关于砍竹子的一道有趣的题目哦，喵~

我们有一排 n 根竹子，第 i 根的高度是 $h_i$。接下来会有 q 次询问，每次询问会给我们一个区间 [l, r] 和两个数字 x 和 y。

对于每次询问，我们只考虑 [l, r] 这个区间的竹子。我们需要对这些竹子进行 y 次水平切割。这些切割有两个神奇的规则：

1. 每次切割掉的竹子总长度都是相同的。
2. 经过 y 次切割后，所有竹子的高度都将变为 0。

我们的任务是，找出第 x 次切割是在哪个高度进行的，喵~

需要注意的是，每次询问都是独立的，竹子们在一次询问后会魔法般地恢复原状，不会真的被砍掉哦！

解题思路分析

这道题看起来有点复杂，又是切割又是区间的，但别怕，让我来一步步带你解开它的谜底吧，喵~

第一步：理解切割过程

首先，我们来分析一下这个“切割”到底是怎么回事。

假设在区间 [l, r] 内，竹子的总高度是 $S = \sum_{i=l}^{r} h_i$。 题目说要进行 y 次切割，每次切掉的长度相同，最后全部切完。这意味着，总共要切掉的长度就是 S，所以每次切割掉的长度就是 $V = S/y$。

现在，我们来定义一个函数。如果我们在高度 H 进行一次水平切割，所有高于 H 的竹子都会被砍到 H。那么，这次切割后，所有竹子的总长度会变成多少呢？我们可以定义一个函数 f(H) 来表示这个结果：

$$f(H) = \sum_{i=l}^{r} \min(h_i, H)$$

这个函数表示，把区间 [l, r] 内所有竹子的高度都变成 $\min(h_i, H)$ 后的总高度。

那么，“第 x 次切割”是在什么高度呢？ 让我们从结果倒推。经过 x 次切割后，总共切掉了 $x \cdot V = x \cdot S/y$ 的长度。 那么，剩余的竹子总长度应该是 $S - x \cdot S/y = S \cdot \frac{y-x}{y}$。

根据题目的描述和样例的提示，我们可以得出一个关键结论：第 x 次切割的高度，就是那个能使所有竹子被削减后，剩余总长度恰好等于 x 次切割后应有剩余量的那个高度 H。

所以，对于每次询问 (l, r, x, y)，我们的目标就是找到一个高度 $H_x$，使得：

$$f(H_x) = \sum_{i=l}^{r} \min(h_i, H_x) = S \cdot \frac{y-x}{y}$$

其中 $S = \sum_{i=l}^{r} h_i$。

第二步：如何求解 $H_x$

我们现在有了一个方程，左边是关于未知数 $H_x$ 的函数 f(H_x)，右边是一个可以算出来的具体值。我们称之为 target_length。

$$f(H_x) = \text{target\_length}$$

观察函数 f(H)，我们会发现它是一个单调递增函数。也就是说，H 越大，f(H) 的值也越大。这是一个非常好的性质，因为它意味着我们可以通过二分查找来求解 $H_x$！

但是，如果在二分查找的每一步都去暴力计算 f(H)，复杂度是 $O(N)$，对于每个查询来说太慢了。我们需要一种更快速的方法来计算 f(H)。

让我们把 f(H) 拆开来看：

$$f(H) = \sum_{i \in [l,r], h_i \le H} h_i + \sum_{i \in [l,r], h_i > H} H$$

这个式子可以进一步变形为：

$$f(H) = (\text{在区间 [l,r] 内，高度不大于 H 的竹子的高度和}) + H \cdot (\text{在区间 [l,r] 内，高度大于 H 的竹子的数量})$$

问题转化成了：对于一个查询 (l, r) 和一个高度 H，快速求出区间内满足特定高度条件的竹子的数量和高度和。

这是一个经典的二维数点/求和问题（一个维度是数组下标，一个维度是值）。解决这类问题的神器就是可持久化线段树，也就是我们常说的主席树啦，喵~

第三步：主席树大显神威！

我们可以对竹子的高度值域 [0, H_max] 建立一棵线段树。然后，我们遍历原数组 h_1, h_2, ..., h_n，对每个前缀 h_1...h_i 都建立一个版本的主席树。第 i 个版本的主席树是在第 i-1 个版本的基础上，插入了 $h_i$ 的信息。

主席树的每个节点需要存储两个信息：

1. count: 落入该节点所代表的高度范围内的竹子数量。
2. sum: 这些竹子的高度总和。

当我们需要查询区间 [l, r] 的信息时，我们只需要用第 r 个版本的主席树的信息减去第 l-1 个版本的主席树的信息，就可以得到只属于区间 [l, r] 的竹子的信息了，是不是很巧妙呀？

有了主席树，我们就可以高效地实现两种策略：

1. 二分答案 + 主席树查询： 对答案 H 进行二分查找。在每次 check(mid_H) 时，利用主席树在 $O(\log H_{max})$ 的时间内查询出 [l,r] 中高度 > mid_H 的竹子数量和 ≤ mid_H 的竹子高度和，从而计算出 f(mid_H)，并与 target_length 比较来调整二分范围。 总复杂度：$O(N \log H_{max} + Q \cdot \log(\text{HeightRange}) \cdot \log H_{max})$。

2. 在主席树上二分！ 这是一个更酷的技巧！既然主席树的结构本身就是二分的，我们为什么不直接在树上进行查找呢？这样可以省掉外面的一层二分查找。 我们可以写一个 query 函数，它在主席树上从根节点开始往下走，来寻找那个满足 f(H) = target_length 的 H。

   • 在一个节点，它代表高度区间 [L, R]，中点是 M。
   • 我们可以计算出如果把切割高度定在 M，那么左子树（高度 ≤ M）的竹子会贡献多少长度（就是它们的和），右子树（高度 > M）的竹子会贡献多少长度（就是它们的数量乘以 M）。
   • 把这两部分加起来，就得到了 f(M)。
   • 比较 f(M) 和 target_length，如果 f(M) 大于目标值，说明我们的切割高度 M 太高了，真正的 H 应该在左子树 [L, M] 中。反之，则在右子树 [M+1, R] 中。
   • 这样一路走下去，最终就能在叶子节点或者递归过程中确定 H 的值。

这个方法的复杂度是 $O(N \log H_{max} + Q \log H_{max})$，比第一种方法更快哦！我将会用这种方法来实现代码~

代码实现

下面就是我精心为你准备的代码啦，注释写得很详细，希望能帮到你，喵~

#include <iostream>
#include <vector>
#include <numeric>
#include <iomanip>

using namespace std;

// 使用 long long 防止求和时溢出
using ll = long long;

const int MAX_N = 200005;
const int MAX_H = 100000;

// 主席树的节点定义
struct Node {
    int left_child = 0, right_child = 0; // 左右子节点的ID
    ll count = 0; // 区间内的竹子数量
    ll sum = 0;   // 区间内竹子的高度和
};

// 用一个大的 vector 来当内存池，避免动态内存分配的开销
vector<Node> tree;
int node_count = 0; // 当前已经使用的节点数量

// 存储每个前缀版本的主席树的根节点
vector<int> roots;

// 初始化，预分配一些空间
void init(int n) {
    // 预估节点数量，N*logH + Q*logH，稍微多给一点
    tree.resize(MAX_N * 22); 
    roots.resize(n + 1, 0);
    node_count = 1; // 0号节点是哨兵，我们从1号开始用
}

// 主席树的插入函数
// prev_node_id: 上一个版本的节点ID
// l, r: 当前节点代表的高度范围
// h: 要插入的竹子的高度
int insert(int prev_node_id, int l, int r, int h) {
    int curr_node_id = node_count++;
    tree[curr_node_id] = tree[prev_node_id];
    tree[curr_node_id].count++;
    tree[curr_node_id].sum += h;

    if (l == r) {
        return curr_node_id;
    }

    int mid = l + (r - l) / 2;
    if (h <= mid) {
        tree[curr_node_id].left_child = insert(tree[prev_node_id].left_child, l, mid, h);
    } else {
        tree[curr_node_id].right_child = insert(tree[prev_node_id].right_child, mid + 1, r, h);
    }
    return curr_node_id;
}

// 在主席树上查找切割高度的函数
// r_root, l_root: 分别是前缀r和前缀l-1的树根
// l, r: 当前节点代表的高度范围
// target_remaining_sum: 目标剩余总长度
// count_above: 在当前处理范围之上（更高）的竹子数量
double find_cut_height(int r_root, int l_root, int l, int r, double target_remaining_sum, ll count_above) {
    if (l == r) {
        // 到达叶子节点，此时可以计算出最终的高度
        // target_remaining_sum = H * (总数量)
        // H = target_remaining_sum / (总数量)
        ll total_count = (tree[r_root].count - tree[l_root].count) + count_above;
        if (total_count == 0) return 0.0; // 避免除以零
        return target_remaining_sum / total_count;
    }
    
    int mid = l + (r - l) / 2;

    // 计算在区间[l, r]中，位于左子树（高度<=mid）的竹子的总高度
    ll sum_in_left = tree[tree[r_root].left_child].sum - tree[tree[l_root].left_child].sum;
    
    // 计算在区间[l, r]中，位于右子树（高度>mid）的竹子的数量
    ll count_in_right = tree[tree[r_root].right_child].count - tree[tree[l_root].right_child].count;
    
    // 如果把切割高度设为mid，那么剩余总长度 = 左子树的和 + (mid * 右边竹子的数量)
    // 注意，这里的右边竹子也包括了高度大于当前节点范围r的竹子
    double remaining_if_cut_at_mid = sum_in_left + (double)mid * (count_in_right + count_above);

    if (target_remaining_sum <= remaining_if_cut_at_mid) {
        // 目标值更小或相等，说明真实切割高度 H <= mid，应该去左子树里找
        // 传给下一层的 count_above 就是当前层的右子树数量 + 上层传下来的 count_above
        return find_cut_height(tree[r_root].left_child, tree[l_root].left_child, l, mid, target_remaining_sum, count_in_right + count_above);
    } else {
        // 目标值更大，说明真实切割高度 H > mid，应该去右子树里找
        // 左子树的竹子全部保留，它们的贡献是 sum_in_left
        // 我们需要在右子树里凑够 target_remaining_sum - sum_in_left
        return find_cut_height(tree[r_root].right_child, tree[l_root].right_child, mid + 1, r, target_remaining_sum - sum_in_left, count_above);
    }
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    init(n);

    for (int i = 1; i <= n; ++i) {
        int h;
        cin >> h;
        roots[i] = insert(roots[i - 1], 0, MAX_H, h);
    }

    cout << fixed << setprecision(9);

    for (int i = 0; i < q; ++i) {
        int l, r, x, y;
        cin >> l >> r >> x >> y;

        // 计算区间[l,r]内的竹子总高度
        ll total_sum = tree[roots[r]].sum - tree[roots[l - 1]].sum;
        if (total_sum == 0) { // 特殊情况：区间内没有竹子或竹子都为0
            cout << 0.0 << "\n";
            continue;
        }

        // 计算第x次切割后，应该剩余的总长度
        double target_remaining_sum = (double)total_sum * (y - x) / y;

        // 在主席树上寻找答案
        cout << find_cut_height(roots[r], roots[l - 1], 0, MAX_H, target_remaining_sum, 0) << "\n";
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(N \log H_{max} + Q \log H_{max})$

  • 建树: 我们需要遍历 N 根竹子，每次插入操作会在主席树上走过一条从根到叶子的路径，深度为 $O(\log H_{max})$，其中 $H_{max}$ 是竹子的最大高度。所以建树的总时间复杂度是 $O(N \log H_{max})$。
  • 查询: 对于 Q 次查询，每次查询我们都在主席树上进行一次二分查找，深度也是 $O(\log H_{max})$。所以查询的总时间复杂度是 $O(Q \log H_{max})$。
  • 两部分加起来就是 $O((N+Q) \log H_{max})$。

• 空间复杂度: $O(N \log H_{max})$

  • 主席树每次插入操作会创建 $O(\log H_{max})$ 个新节点。N 次插入后，总的节点数量级为 $O(N \log H_{max})$。

知识点总结

这道题是一道非常好的数据结构练习题，融合了问题转化和主席树的高级技巧，喵~

1. 问题转化: 解决问题的关键是第一步，正确地将复杂的“切割”过程转化为一个清晰的数学方程 $f(H) = k$。这是算法竞赛中非常重要的一项能力。

2. 主席树 (可持久化线段树): 它是解决区间第k大/小、区间值域查询等问题的有力工具。通过保存历史版本，可以巧妙地处理区间上的查询。

3. 在数据结构上二分: 本题的最优解法展示了一个非常漂亮的思想：当答案具有单调性，并且其定义和一个树形数据结构的查询过程高度相关时，可以尝试将二分查找的过程直接融合到数据结构的查询中，从而优化掉一个 log 因子。

希望这篇题解能帮助你更好地理解这道题目和它背后的算法思想！继续加油哦，主人！喵~