算法:计算每个更新查询的不同排序子序列的最小数量

Question

这个问题是在面试中问我的:
包含相邻值的不同排序子序列 定义为其长度为一 或它仅包含排序时的相邻数字。每个元素只能属于 1 个这样的子序列。我有 Q 个查询，每个更新 A 中的一个值，我必须为每个查询回答，如果部分数量最小化，A 的分区中有多少部分会分成不同的排序子序列。

例如，A = [1,2,3,4,3,5] 的部分数可以通过以下两种方式划分来最小化，这两种方式都只包含两个部分:

1) [1,2,3] && [4,3,5] ==> answer 2 (4,3,5 sorted is 3,4,5 all adjacent values)

2) [1,2,3,4,5] && [3] ==> answer 2 

我尝试过的方法:散列和形成集合，但由于超时，所有测试用例都没有被清除。

问题陈述 PDF: PDF

约束:
1<= N,Q <= 3*10^5
1< A(i)< 10^9

Answer 1

预处理

首先，您可以在所有查询之前预处理 A 并生成一个表(比如 times_of)，这样当给定一个数字 n 时，可以通过times_of[n]等表达式，高效获取n在A中出现的次数。在以下示例中，假设 A 的类型为 int[N]，我们使用 std::map 来实现该表。它的构建花费了O(NlogN)时间。

auto preprocess(int *begin, int *end)
{
    std::map<int, std::size_t> times_of;
    while (begin != end)
    {
        ++times_of[*begin];
        ++begin;
    }
    return times_of;
}

设min 和max 分别是A 的最小和最大元素。然后应用以下引理:

The minimum number of distinct sorted subsequences is equal to max{0, times_of[min] - times_of[min-1]} + ... + max{0, times_of[max] - times_of[max-1]}.

严格的证明有点技术性，所以我从这个答案中省略了它。粗略地说，从小到大考虑数字。如果n出现的次数多于n-1，则必须带上额外的times_of[n]-times_of[n-1]个子序列。

有了这个引理，我们可以在 O(N) 时间内计算不同排序子序列 result 的最小数量(通过遍历 times_of，而不是从 迭代code>min 到 max)。以下是示例代码:

std::size_t result = 0;
auto prev = std::make_pair(min - 1, static_cast<std::size_t>(0));
for (auto &cur : times_of)
{
    // times_of[cur.first-1] == 0
    if (cur.first != prev.first + 1) result += cur.second;
    // times_of[cur.first-1] == times_of[prev.first]
    else if (cur.second > prev.second) result += cur.second - prev.second;

    prev = cur;
}

查询

为了处理查询A[u] = v，我们首先更新times_of[A[u]] 和times_of[v] 这花费了 O(logN) 时间。然后根据引理，我们只需要重新计算常量(即 4)相关项来更新 result。每次重新计算都花费 O(logN) 时间(以查找 times_of 中的上一个或下一个元素)，因此查询总共花费 O(logN) 时间。