主页 / coding / 问题 / 79310078
Accepted
Donald
Asked: 2024-12-27 01:26:46 +0800 CST

用于轻松找到特定区间内非递减序列的最大长度的数据结构

  • 772

我正在尝试寻找解决这一挑战的方法：

给定 n，即一个由 1 填充的数组的大小。此数组上可以进行两种类型的操作：

  • 增加（x，y，m）：将 m 添加到从位置 x 到 y（包括）的区间内的所有数组元素。1 <= x <= y <= n。
  • 给出（x，y）：返回给定区间上的非减序列的最大长度。

例子：

输入：n = 5：

运营：

  1. 增加 1 2 3 (x = 1, y = 2, m = 3)

    现在我们的数组是[4, 4, 1, 1, 1]

  2. 给出 2 4 (x = 2, y = 4)

    最大长度为 2，因为最大非递减序列为 1, 1。

我寻找一个解决方案，其中每个操作都有 O(log(n)) 的时间复杂度。

我的方法

我注意到我们可以将此数组存储为零数组，其中每个元素表示它比前一个元素大多少。例如，[1, 4, 2, 5]我们有而不是[0, 3, -2, 3]。现在我们只需查看负数就可以轻松找到非递减序列。我曾尝试过这种方式并优化查找负数（例如通过使用集合或树），但在某些情况下，“给予”操作仍然具有 O(n) 复杂度，这不是我想要的。

我的算法是这样工作的：
请注意，如果我们使用一个零数组，我们可以只用两个步骤来改变它（当有增加操作时）：arr[x] += m 和 arr[y + 1] -= m（我假设 arr 是基于 1 的）。一开始我有一个新的空集。在增加操作期间，我执行上述两个步骤，然后：

  1. 如果“+= m”操作后 arr[x] 不小于 0，则从集合中删除 x。

  2. 如果“-= m”操作后 arr[y + 1] 不再等于或大于 0，则将 y + 1 添加到集合中。

在所有增加操作之后，我们将得到一组全负数。正如我上面所写的，这些都是非递减区间。例如，如果我们有n = 6和set = {2, 6}，我们就有 3 个非递减区间：(1, 1)、(2, 5)、(6, 6)。所以我们可以在 O(set.size()) 中执行 Give 操作，这并不好。

如何以 O(logn) 时间复杂度执行每个操作？

algorithm

1 个回答

  1. Best Answer

    这可以使用具有惰性传播的线段树来解决（或者，可以在二叉索引树中单独处理范围增加）。在每个节点中，存储节点所代表的间隔的左右端点的增加总和以及三个最长的非递减子数组的长度：从左端点开始的子数组、以右端点结束的子数组以及节点间隔内任意位置的总最长子数组。对于叶节点，所有三个长度都是 1，我们从每个节点的增量为 0 开始。

    合并两个节点时，考虑是否可以将以左节点右端点为终点的最长非递减子数组与以右节点左端点为起点的最长非递减子数组合并，方法是检查前者右端点的元素在应用增加后是否不大于后者左端点的元素（回想一下，端点上的增加操作的总和已经存储在每个节点中）。合并结果中以左端点为起点的最长非递减子数组的值将与左节点的值相同，除非左节点中的最长非递减子数组覆盖整个节点，在这种情况下它将是左节点和右节点的组合结果（如果可能的话）。以右端点为终点的最长非递减子数组的情况是对称的。

    对于覆盖整个节点的增加操作，所有非递减子数组仍保持非递减，因为所有元素都以相同的量递增。只需将这些作为惰性更新进行跟踪（在遍历线段树时，一旦遇到节点就立即下推更新）。

    查询和更新都可以在 中完成O(log(n))。

    C++ 中的实现：

    #include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
struct Node {
    int left, right, leftIncr, rightIncr, prefixMax, suffixMax, overallMax, lazy;
};
std::vector<Node> tree;
void pushdown(int n) {
    tree[n].leftIncr += tree[n].lazy;
    tree[n].rightIncr += tree[n].lazy;
    if (tree[n].left != tree[n].right) {
        tree[n * 2].lazy += tree[n].lazy;
        tree[n * 2 + 1].lazy += tree[n].lazy;
    }
    tree[n].lazy = 0;
}
Node merge(Node l, Node r) {
    bool canCombine = l.rightIncr <= r.leftIncr;
    return { 
        l.left, r.right, l.leftIncr, r.rightIncr, 
        l.prefixMax + (l.prefixMax == l.right - l.left + 1 && canCombine) * r.prefixMax, 
        r.suffixMax + (r.suffixMax == r.right - r.left + 1 && canCombine) * l.suffixMax, 
        std::max({l.overallMax, r.overallMax, canCombine * (l.suffixMax + r.prefixMax)})
    };
}
Node build(int n, int l, int r) {
    if (l != r) {
        int mid = std::midpoint(l, r);
        tree[n] = merge(build(n * 2, l, mid), build(n * 2 + 1, mid + 1, r));
    } else {
        tree[n].left = tree[n].right = l;
        tree[n].prefixMax = tree[n].suffixMax = tree[n].overallMax = 1;
    }
    return tree[n];
}
void update(int n, int updateLeft, int updateRight, int incr) {
    pushdown(n);
    if (updateLeft <= updateRight)
        if (tree[n].left == updateLeft && tree[n].right == updateRight) {
            tree[n].lazy = incr;
            pushdown(n);
        } else {
            update(n * 2, updateLeft, std::min(updateRight, tree[n * 2].right), incr);
            update(n * 2 + 1, std::max(tree[n * 2 + 1].left, updateLeft), updateRight, incr);
            tree[n] = merge(tree[n * 2], tree[n * 2 + 1]);
        }
}
Node query(int n, int queryLeft, int queryRight) {
    pushdown(n);
    if (tree[n].left == queryLeft && tree[n].right == queryRight) return tree[n];
    if (queryRight <= tree[n * 2].right) return query(n * 2, queryLeft, queryRight);
    if (queryLeft > tree[n * 2].right) return query(n * 2 + 1, queryLeft, queryRight);
    return merge(query(n * 2, queryLeft, tree[n * 2].right), query(n * 2 + 1, tree[n * 2 + 1].left, queryRight));
}
int main() {
    int n;
    std::cin >> n;
    tree.resize(4 * n);
    build(1, 1, n);
    for (int type, l, r, incr; std::cin >> type >> l >> r;) {
        // type = 1 is query; type = 0 is update
        if (type) std::cout << query(1, l, r).overallMax << '\n';
        else {
            std::cin >> incr;
            update(1, l, r, incr);
        }
    }
}
    • 2

相关问题