CSES範囲クエリの質問：給与クエリ
私はこの問題を解決しようとしています： 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]、合計クエリの処理が効率的になります。ただし、値を更新するように指示された場合、たとえば3番目の要素をに変更すると、4すべてのバランスが崩れます。圧縮機能は次のように変更する必要があります
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;
これにより、オカレンス配列を再構築する必要があり、O(N)更新時間が発生します。
以来N、最大にすることができ200000、私はインデックス圧縮と正しい考えを持っていると思うが、私の現在のアプローチは、効率的に問題を解決するには十分機能しません。誰かが私の方法で私を正しい方向に向けることができますか？
回答
インデックス圧縮を使用することについて、あなたは正しい考えを持っています-素晴らしい考えです！Nのみ最大で200000発生アレイはせいぜいが必要とする維持、200000代わりに、与えられた配列の初期値のための要素を10^9配列インデックス。
あなた自身によると、あなたが直面する問題は、クエリの処理中に新しい値に遭遇したときです。あなたが正しい; これにより、オカレンス配列のバランスが崩れ、更新をO(N)時間内に実行する必要があります。この問題の解決策は、現在のメソッドを少し変更するだけです。
新しい値に遭遇する問題を解決するために、私達はちょうど私たちがだろうことを確認することができなかった新しい値に遭遇していません。これを行うには、合計セグメントツリーを構築する前にすべてのクエリを読み込みます。これにより、最大のN + 2*Q一意の値が生成されます。600000最悪の場合、問題の512MBのストレージ制限でオカレンス配列を構築するのに十分な値になります。その後、合計セグメントツリーはこれらのクエリに効率的に答えることができます。
したがって、最終的に、この問題を解決するための戦略は、すべての一意の数値を入力し、インデックス圧縮関数を構築し、合計セグメントツリーを使用して合計クエリを効率的に処理することです。
将来的には、この種のクエリ回答の質問では、事前計算の前にすべての入力を読み取ることが役立つ場合があることを覚えておいてください。あなたのプログラムで頑張ってください。
まず、素朴なことを考えてみましょう。更新ごとに、アレイを更新します。クエリごとに、配列全体をスキャンして回答を収集します。このソリューションの複雑さには、O(n)更新、O(n)クエリがあります。ダメ。
おそらく時間計算量がさらに悪い別の解決策を考え出すことができますが、それは私たちの最終結果が何であるかについてのヒントを与えてくれます。ソース配列を常に維持しますが、値->頻度のハッシュマップも維持します。次に、更新するときに、古い値で周波数をデクリメントし、新しい値で周波数をインクリメントします。ここで、クエリの場合、そのクエリ範囲のすべての値をループし、それらを合計して回答を求めます。これにより、O(1)更新とO(r-l)クエリが発生するため、優れた更新がありますが、クエリはひどいものになります。しかし、この結果は、我々ができるかどうかにより改善することができるだけでこれらのクエリをスピードアップ！セグメントツリーを入力します。
従来は、作成時に葉に至るまでセグメントツリーを構築していました。ただし、名目上はからの範囲のセグメントツリーが必要な0-10^9ので、それほど多くのメモリを生成する方法は絶対にありません（そうすることでタイムアウトになります）。ただし、セグメントツリーを作成した場合はどうなりますが、ノードごとに、その子は使用されたことがない場合は暗黙的です。つまり、要素が含まれていない場合は子ノードを作成しないでください。この構造は、適切には、暗黙のセグメントツリーと呼ばれます。ここでの考え方は、左右の子を初期化するコンストラクターの部分をスキップすることを除いて、通常どおりセグメントツリーを実装することです。ここで、部分的な範囲クエリのために子を詳しく調べる必要がある場合は、子が存在するかどうかを確認し、存在しない場合は作成します。それ以外の場合は、作成する必要がないため、これらのノードの値の合計が0であると想定してください。
最終的な解決策は次のとおりです。クエリ可能な最大値のセグメントツリーを作成します（インタラクティブに回答する必要がない場合は、クエリを保存してスキャンして最大r値を見つけることを検討してください。ただし、そうする必要はありません）。これを暗黙のセグメントツリーにすることに注意してください。更新のたびにソース配列を維持し、ツリーでポイント更新を実行しますO(log(max value))。クエリは通常のセグメントツリー範囲クエリであるため、これらはになりますO(log(max value))。そして、それがあります！
ポリシーベースのデータ構造を使用できます。これには、order_of_key（）などの便利なメソッドがいくつかあります。これは、指定された数より少ないアイテムの数を返します。getcnt（b + 1）-getcnt（a）-のように、これを2回呼び出すことができます。これにより、指定された範囲内のアイテムの数がわかります。これに関する詳細については-あなたは参照することができます-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;
}