問題タブ [segment-tree]

http://www.spoj.com/problems/CTRICK/ spojの問題です

マジシャンはカードの小さなパックをシャッフルし、それを裏向きにして、次の手順を実行します。

1. 一番上のカードがパックの一番下に移動します。新しいトップカードが表向きにテーブルに配られます。スペードのエースです。

2. 2 枚のカードを上から下に 1 つずつ移動します。次のカードが表向きにテーブルに配られます。スペードのツーです。

3. 3 枚のカードが 1 つずつ移動されます…</p>

4. これは、n 番目と最後のカードがスペードの n になるまで続きます。

この印象的なトリックは、マジシャンが事前にカードの配置方法を知っている場合 (および偽のシャッフルの方法を知っている場合) に機能します。プログラムは、1 ≤ n ≤ 20000 の指定された数のカードのカードの最初の順序を決定する必要があります。

入力

入力の最初の行は、1 つの正の整数であり、従うべきテスト ケースの数を示します。各ケースは、整数 n を含む 1 行で構成されます。出力

テスト ケースごとに、値 1 から n の正しい順列をスペースで区切って行を出力します。パックの一番上のカードを示す最初の数字など…例

入力: 2

4

5

出力：

2 1 4 3

3 1 4 5 2

今私が考えることができる唯一の解決策は、キューを使用してプロセスをシミュレートすることです。しかし、それはO（n ^ 2）になります。コメントを読んだところ、BITのセグメントツリーを使用することが提案されました。セグメント ツリーと BIT の両方を知っていますが、この質問でそれらを実装する方法を理解できません。これを行う方法を提案してください。ありがとう

セグメント ツリーを理解しようとしています。これは、範囲内の最小値を見つける方法を示す優れたチュートリアルです。ただし、「構築されたセグメント ツリーのすべてのレベルは、最後のレベルを除いて完全に埋められます。また、すべてのレベルで常にセグメントを 2 つに分割するため、ツリーはフル バイナリ ツリーになります。」追加がどのように実行されるかわかりませんか? たとえば、さらに 2 つの要素 6 と 10 を追加した場合、それらはどこに行くべきでしょうか? 右のサブツリーに? はいの場合、バランスがあまり取れていない 5 つがあり、半分は等しくありません。どういうわけかツリーを並べ替えて、計算をやり直す必要がありますか?

このチュートリアルで、関数がノード インデックスを返すだけでなく、最後の 4 行のコードquery()の内容を変更するのはなぜですか?M

彼のアプローチには問題があると思います。変更された M 配列はm[node]、最近のクエリのインデックスを格納するため、将来の RMQ [range minimum Queries] を処理できなくなります。

これが私が話しているコードです：

サイズ N の配列と、同じくサイズ N の間隔の配列があり、それぞれが最初の配列の連続するセグメントである場合、配列の要素を更新し、セグメントの合計を求める Q クエリを処理する必要があります。 2 番目の配列 (iTH 間隔から jTH 間隔までの要素の合計)。

これで、最初のクエリを簡単に処理できます。配列からセグメント ツリーを構築できます。これを使用して、最初の配列 (2 番目の配列の要素) の間隔の合計を計算できます。しかし、O(log n) で 2 番目のクエリを処理するにはどうすればよいですか? 最悪の場合、更新する要素は 2 番目の配列のすべての間隔に含まれます。

O(Q log N) または O(Q (logN)^2) ソリューションが必要です。

セグメント ツリー O(logn) の範囲合計は最悪の場合?? O(n)じゃないの？範囲合計操作中に、アルゴリズムに従って左右のノードの両方をトラバースするとどうなるでしょうか?

N 個の要素と N 個の範囲を持つ配列 A が与えられます。それぞれ [L, R] の形式です。範囲の値を、インデックス L からインデックス R までの A のすべての要素の合計と呼びます。

例 : 配列 A = [2 5 7 9 8] とし、範囲を [2,4] とすると、この範囲の値は 5+7+9=21 になります。

ここで、2 つのタイプのいずれかのクエリごとに Q 個のクエリが与えられます。

例:配列 A = [2 3 7 8 6 5] とし、3 つの範囲があるとします。

次に、3 つのクエリを作成します。

10^5 のクエリがあり、N も 10^5 までの場合の方法。効率的な方法で Queries2 に報告するにはどうすればよいですか?

私のアプローチ：最初のクエリは簡単に処理できます。配列からセグメント ツリーを構築できます。これを使用して、最初の配列 (2 番目の配列の要素) の間隔の合計を計算できます。しかし、O(log n) で 2 番目のクエリを処理するにはどうすればよいですか? 最悪の場合、更新する要素は 2 番目の配列のすべての間隔に含まれます。

O(Qlog N) または O(Q(logN)^2) ソリューションが必要です。

明らかに、各クエリに O(N) を使用することはできません。効率的な方法を取得するのを手伝ってください

私の現在のコード：

コードは正しいですが、大規模なテスト ケースの場合は膨大な時間がかかります。助けてください

【チャレンジ終了】

問題：

正の要素の配列。Deepu 配列の要素を減らしたい。彼は、X より大きい配列内のすべての要素を 1 だけ減らす関数 Hit(X) を呼び出します。

彼はこの配列を何度も呼び出します。Hit(X) を何度も呼び出した後、配列を出力します。

入力：

n----- 配列 10^5 の要素の数。

n 個の要素 ----- 1<=要素<=10^9。

x----- Hit(X) x 要素への呼び出しの数----- 1<=要素<=10^9。

出力：

出力 Hit(X) x 回の呼び出し後の配列。

制限時間・・・5秒。

私の解決策はTime Limit Exceededを与えました。

私のアプローチ：

1. 元の配列を保持
2. 配列要素と配列内のインデックスのペアのベクトルを作成します。ベクトル要素を [昇順] で並べ替えます。
3. C++ STL の LowerBound() を実行して、要素が等しいベクトル内の要素の位置を取得し、要素 x を指定します。
4. この要素から、ペアのインデックスから元の配列の最後まで、x より大きい要素を 1 ずつ減らします。
5. x ごとに手順 3 と 4 を繰り返します。
6. 元の配列を印刷します。

私のソリューションの複雑さは n^2 だと思います。

最適化されたソリューションを教えてください

ありがとう

マイコード