問題タブ [segment-tree]

私はこの問題を解決しようとしています:

少女には n 個の要素の配列があります (配列の要素には 1 から始まるインデックスが付けられます)。

また、"q" 個のクエリがあり、それぞれが一対の整数li, ri (1 ≤ li ≤ ri ≤ n)によって定義されます。クエリごとに、li から ri までのインデックスを持つ配列の要素の合計を見つける必要があります。

少女はその問題がかなりつまらないことに気づきました。彼女は、クエリ応答の合計が可能な限り最大になるように、クエリに応答する前に配列要素を並べ替えることにしました。あなたの仕事は、この最大合計の値を見つけることです。

入力：

最初の行には、スペースで区切られた 2 つの整数 n (1 ≤ n ≤ 10^5) と q (1 ≤ q ≤ 10^5) が含まれています。これは、配列内の要素の数とクエリの数です。

次の行には、スペースで区切られた n 個の整数 ai (1 ≤ ai ≤ 10^5) — 配列要素が含まれます。

次の q 行のそれぞれには、スペースで区切られた 2 つの整数li と ri (1 ≤ li ≤ ri ≤ n) — i 番目のクエリが含まれます。

出力：

1 行に 1 つの整数 (配列要素が並べ替えられた後のクエリ応答の最大合計) を出力します。

私はセグメント ツリーの知識を持っているので、セグメント ツリーを介して遅延伝播アプローチを適用しました。

私の努力コード:

これに対する私のアプローチは、セグメントツリーを使用して前述のように実行し、最後に答えを出力するだけの簡単なものでした。

私の質問は、これのためのより単純なアルゴリズムはありますか? または、セグメント ツリー コードを最適化する必要がありますか?

更新および範囲クエリ用の一般的なセグメント ツリー クラスを作成しようとしています。

要素が単なる整数であり、要素の範囲に対して実行される操作がそれらの合計または積であると仮定する代わりに、ユーザーに要素の型 T と関数を提供してもらい、それをcomposeと名付けました。

この関数は、型 T の 2 つのパラメーターを受け取り、同じ型 T の値を返します。この戻り値は、目的の操作が 2 つの要素の範囲で実行されたときの結果です。これを使用して、任意の範囲で同じ操作を実行できます。要素数。

クラスは次のとおりです。

このクラスを使おうとすると、パラメータとして取り込んだcompose関数が使われておらず、逆にbinary_function_unitypeクラスの関数が使われていることがわかりました。

ユーザーからの関数定義がクラス binary_function_unitypeの関数定義をオーバーライドし、作業が完了することを期待していました。しかし、そうはなりませんでした。このクラスを使用したプログラムは次のとおりです。

誰かが私のアプローチの欠陥を教えてもらえますか、または C++ での継承またはテンプレートの使用に関する基本的な概念を誤解したかどうかを教えてもらえますか?

ありがとう。

私は10個の数字supprse A [10] = {1,2,3,4,5,6,7,8,9,10}への配列を持っており、特定の範囲で数字の乗算を計算する必要がありますが、得られません正解、私はセグメントツリーを使用していますが、クエリ操作の使用方法がわかりません これが私のコードです:

配列に対して製品範囲クエリを実行するためのコードを作成しました。

注: この質問はMultiplication in a rangeの重複ではありません。私の問題は何か違う

このためのコードを書きましたが、

私が選択した R は、いくつかのテストケースに失敗していると確信しています。^{R も 10 18}で試しました。しかし、それでも同じ問題です。なぜこれが起こっているのか分かりませんか？

私の質問は、RI が選択した問題なのか、それとも各テスト ケースで異なる M が渡される問題なのかということです。

注: 本当に解決策を期待しているのではなく、手がかりを期待しているだけです

よろしく

以下を達成するための適切な方法を決定しようとしています。

範囲が必要です->特定の範囲内でルックアップを設定します（[0x0 - 0xffffffff]など）。値は範囲の範囲に挿入されます (したがって、T = 一意の文字列を使用している場合)、insert("beef3490", [0x1234, 0xFFFF]); また、1 つの ID に複数の挿入が含まれる場合があり、それらは重複する場合と重複しない場合があります。さらに、重複する他の値が挿入される可能性があり、それらが重複する場所では、結果として一意の文字列のセットを受け取る必要があります。最後に、値を範囲から削除することもできます (必ずしも一致する必要はありませんが、通常は最初の挿入範囲内に含まれます)。

簡単な使用例を次に示します。

これは私にとって多くの質問につながります：

1. この種の問題の一般化された名前、または洞察を見つけることができる同様のタイプの問題はありますか?

2. 次の制約を考えると、理想的な実装は何ですか:

   • 高速/非常に高速なルックアップ時間
   • メモリ使用量が膨れ上がることはありません (つまり、次の操作は同等のフットプリントを持ちます)。
   • • [10,20] を挿入、[20,30] を挿入、[14,24] を削除
   • • [10,15] を挿入、[25,30] を挿入
   • 最後と同様に、データ構造は長時間稼働するシステムで安定している必要があります
   • 挿入/削除時間は絶対にひどいわけではありません (ルックアップほど速くする必要はありません)。

3. 理想的な実装が与えられた場合、それを C++ で使用するためのアドバイスはありますか

すべての応答とヘルプに感謝します。

2D 平面上のN (N <= 10 ⁶ ) 点と整数 D (N <= 10 ⁶ ) が与えられた場合、2 つの点 p1,p2 (p1 の右側にある p2) を見つけて、p1.yでp2.yあり、少なくとも D であり、p2.x - p1.x最小化されます。

x 軸と y 軸の範囲は 0..10 ⁶

これはUSACO の過去のコンテストの問題です。

ここにそれを解決するための私の試みがあります:
MAXY = N ポイント間の最大 y 軸。
p1 を知っていると仮定すると、p2 は非常に簡単に見つけることができます。p1.y+Dy 軸がMAXY から MAXY までの範囲または 0 から までの範囲にあるすべてのポイントをp1.y-D取得し、最小の x 軸が より大きいポイントを取得しますp.x。これは、p2 に最適な選択です。

しかし、p1 がわからないので、p1 のすべてのポイントを試す必要があるため、p2 の最適な選択を効率的に見つける必要があります。

そのためにセグメントツリーを使用しました。ツリー内のすべてのノードは、対応する範囲内のすべてのポイントを x 軸のソート順に格納します。クエリ中に、ノードがクエリ範囲内にある場合、配列でバイナリ検索を行い、p1.xそれよりも大きい最小の要素を返します。

p1 を選択するたびに、範囲 0,p1.yD と p1.y+D,MAXY を使用してツリーを 2 回クエリし、返された 2 つのポイントの中で最も良いものを取得します。

ツリーの構築は O(NlogN) 時間で実行できます。すべてのクエリには O(logN*logN) 時間がかかり、N 個のクエリを作成するため、合計所要時間は (Nlogn*logn) であり、2 秒の時間制限内で実行されない可能性があります。(10 ⁶ *20*20)。また、使用されるメモリは O(NlogN) になり、これは約 80 mb (100000*20*4 kb) であり、制限が 64 mb であるため多すぎます。

クエリをより速く、より少ないスペースで実行するにはどうすればよいでしょうか?

この問題は、変更されたマージソートを使用して解決できることを知っており、同じようにコーディングしました。ここで、 Segment Treeを使用してこの問題を解決したいと考えています。基本的に、配列を右から左にトラバースする場合、「現在の値よりも大きい値の数」をカウントする必要があります。このことは、セグメント ツリーによってどのように達成できますか?

セグメント ツリー ノードに格納する必要があるのは、どのような種類の情報ですか?

可能であればコードを提供してください。