8

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

给定一个最多包含最多元素的数组200000，我的任务是处理最多200000查询，这些查询要么要求我更新数组中的单个值，要么要求我查找 a​​ 和 b 之间位于给定范围内的元素数（例如例如，查询会询问从索引1到有多少元素5在范围内[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，我目前的方法无法有效地解决问题，尽管我认为我对索引压缩有正确的想法。有人可以用我的方法指出我正确的方向吗？

4

3 回答 3

7

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

根据您自己的说法，您面临的问题是在处理查询期间遇到新值时。你是对的; 这会使发生数组失去平衡并导致更新必须及时运行O(N)。此问题的解决方案只是对您当前方法的微小修改。

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

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

将来，请记住，在这些类型的查询回答问题中，在预计算之前读入所有输入可能会很有用。祝你的程序好运。

于 2020-08-17T23:09:23.987 回答
3

首先，考虑幼稚：对于每次更新，更新数组。对于每个查询，扫描整个数组并收集您的答案。该解决方案的复杂性在于O(n)更新、O(n)查询。不好。

我们可以提出一个时间复杂度可能更差的不同解决方案，但它给了我们一个关于最终结果的提示。始终维护源数组，但也要保留 value->frequency 的哈希图。然后，当您更新时，以旧值减少频率并以新值增加频率。现在，对于查询，遍历该查询范围的所有值并将它们相加以获得您的答案。这会导致O(1)更新和O(r-l)查询，因此我们有很好的更新但查询很糟糕。但是，如果我们可以加快这些查询的速度，这个结果可以得到改善！输入段树。

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

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

于 2020-08-17T18:41:30.060 回答
2

您可以使用基于策略的数据结构，它具有一些有用的方法，例如 order_of_key() - 它返回小于给定 num 的项目数。我们可以像 getcnt(b+1) 一样调用它两次 - getcnt(a) - 它给出给定范围之间的项目数。有关这方面的更多信息 - 您可以参考 - https://codeforces.com/blog/entry/11080和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;
}
于 2020-08-17T20:21:00.910 回答