CSES 范围查询问题：薪资查询

Question

我正在尝试解决这个问题：https://cses.fi/problemset/task/1144/

给定一个最多 200000 个元素的数组，我的任务是处理最多 200000 个查询，这些查询要么要求我更新数组中的单个值，要么要求我找到位于给定运行ge 中的 a 和 b 之间的元素数（例如，查询会询问索引 1 到 5 中有多少元素在运行中ge [2, 3]).

我目前的想法是首先对给定数组中的值使用索引压缩（因为值可以达到10^9，所以保持简单的出现数组将超出存储限制），然后保留另一个数组，其中包含每个压缩数字的出现次数。然后，可以使用和段树来处理和更新查询。

但是，我运行在尝试实施此方法时遇到了问题。我意识到更新单个数组值会迫使我更改压缩数组。

例如，给定一个数组 [1, 5, 3, 3, 2]，我会定义一个压缩函数 C 这样

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;

那么，出现数组将为[1, 1, 2, 1]，并且处理总和查询将是高效的。但是，如果指示我更新一个值，比如说，将第三个元素更改为 4，那么一切都会失去平衡。压缩函数必须更改为

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;

这将迫使我重建我的事件数组，导致 O(N) 更新时间。

由于 N 可以达到 200000，我目前的方法将无法有效地解决问题，尽管我认为我对索引压缩有正确的想法。有人可以用我的方法指出正确的方向吗？

Answer 1

首先，考虑天真的：对于每个更新，更新数组。对于每个查询，扫描整个数组并收集您的答案。此解决方案的复杂性有 O(n) 个更新，O(n) 个查询。不好。

我们可以想出一个时间复杂度可能更差的不同解决方案，但它会提示我们最终结果是什么。时刻保持源数组，同时保持一个value->frequency的hash map。然后，当您更新时，减少旧值的频率并增加新值的频率。现在，对于查询，循环遍历该查询范围的所有值并将它们相加以获得答案。这导致 O(1) 更新和 O(r-l) 查询，因此我们有出色的更新但糟糕的查询。但是，如果我们可以 just 加快这些查询的速度，则可以改进此结果！输入线段树。

传统上，您会在创建时一直构建一个线段树，直到它的叶子。然而，我们名义上想要一个范围从 0-10^9 的线段树，所以我们绝对没有办法生成那么多的内存（而且我们这样做会超时）。但是，如果我们创建一个线段树，但是对于每个节点，如果它们从未被使用过，它的 children 是 implicit 会怎样。也就是说，如果节点中没有元素，不要创建 child 个节点。这个结构被恰当地命名为隐式线段树。这里的想法是像平常一样实现你的线段树，除了跳过构造函数中你初始化左和右 children 的部分。现在，当您由于部分范围查询而需要深入研究 children 时，检查它们是否存在，如果不存在，则创建它们。否则，由于您永远不需要制作它们，因此假设这些节点中的值之和为 0！

最终解决方案如下：创建可查询最大值的线段树（如果您不必交互式回答，请考虑保存并扫描您的查询以找到最大值 r-value，但您不必）。 注意使其成为隐式线段树。每次更新后维护源数组，并在你的树上做 point-updates，这将是 O(log(max value))。查询是常规的线段树范围查询，因此这些将是 O(log(max value))。它就在那里！

Answer 2

您可以使用基于策略的数据结构，它有一些有用的方法，例如 order_of_key() - returns 项的数量少于给定的数量。我们可以调用它两次，如 getcnt(b+1) - getcnt(a) - 给出给定范围内的项目数。有关这方面的更多信息 - 您可以参考 - https://codeforces.com/blog/entry/11080 and also https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html

经过大量研究，我发现这个 STL 在使用基于树的结构时非常有用。

我测试了下面的代码，它通过了所有的测试用例。

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
 
using namespace std;
using namespace __gnu_pbds;
 
template<class T> using cust_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
cust_set<array<int,2>> freq;
 
int getcnt(int x)
{
    return freq.order_of_key({x,0});
}
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    vector<int> emp(n);
    
    int sal;
    for(int i=0;i<n;i++)
    {
        cin >> emp[i];
        freq.insert({emp[i],i});
    }
    char c;
    int x,a,b;
    while(q--)
    {
        cin>> c;
        int ans=0;
        if(c=='?')
        {
            cin>>a>>b;
            cout << getcnt(b+1) - getcnt(a)<<"\n";
        }
        else
        {
            cin>>a>>b;
            --a;
            freq.erase({emp[a],a});
            emp[a] = b;
            freq.insert({emp[a],a});
        }
    }
    return 0;
}

Answer 3

您在使用索引压缩方面的想法是正确的 - 很棒的想法！由于 N 最多为 200000，保留一个出现数组最多需要 200000 个元素作为给定数组的初始值，而不是 10^9 个数组索引。

根据您自己的说法，您面临的问题是在处理查询过程中遇到新值时。你是对的;这将抛出出现数组 off-balance 并导致更新必须在 O(N) 时间内更新到运行。这个问题的解决方案只是对你目前的方法做一个微小的修改。

要解决遇到新值的问题，我们可以确保我们永远不会遇到任何新值。我们可以通过读入所有查询 before 构建和段树来做到这一点。这将导致最多 N + 2*Q 个唯一值，或者在最坏的情况下 600000 个，这足以构建一个具有问题 512MB 存储限制的事件数组。之后，和段树将能够有效地回答这些查询。

所以最终，解决这个问题的策略是输入每一个唯一的数字，然后构造一个索引压缩函数，然后使用求和线段树来高效地处理求和查询。

以后，请记住在这类 query-answering 问题中，在预计算 之前读入所有输入可能会很有用。祝你的程序好运。

CSES 范围查询问题：薪资查询

CSES Range Query Question: Salary Queries

algorithm

data-structures

segment-tree

range-query