問題タブ [lazy-propagation]

以下は、セグメント ツリーの遅延伝播を使用したhttp://www.spoj.pl/problems/LITE/の実装です。ツリーを分割するのは初めてで、なぜ TLE になるのか理解できません。誰かがそれを見て、私のエラーを修正するのを手伝ってくれませんか?

さて、私はこのCodechef でのコインのフリッピングの問題を解決しようとしていました。セグメントツリーで解決しています。しかし、制限時間を超えています。検索したところ、遅延伝播を使用する必要があることがわかりました。しかし、私には理解できません。私の更新機能は再帰的に（上から下へ）動作します。ヒントを与えるか、例を挙げて説明してください。また、コードを変更する必要がある場所も指摘してください。

コイン投げでは、更新時にノード値が 1 の場合は 0 に、0 の場合は 1 に変更します。

start と end は、元の配列の制限です。tree はセグメント ツリー配列です。

要約された問題: n 要素の配列が与えられました。最初はすべて 0 です。

2 種類のクエリを受け取ります: 0 index1 index2。この場合、範囲 index1 index2(included) 内のすべての要素を 1 ずつ増やす必要があります。

2 番目のタイプ: 1 index1 index2。この場合、index1 と index2 (含まれる) の間の要素が 3 で割り切れる数を表す数値を出力する必要があります。

もちろん、n は非常に大きい (10^6) ため、セグメント ツリーを使用して間隔を格納し、遅延伝播を使用してログ n のツリーを更新することも良い方法です。

しかし、実際には、ここで遅延伝播を適用する方法が本当にわかりません。コインを弾くように2つだけではなく、すべての数字（3k、3k + 1、3k + 2の可能性があります）に対して3つの可能な状態を考慮する必要があるためです。問題。

クエリの間隔に含まれる間隔にフラグを立てた場合、元の配列とその値を見て更新する必要がありますが、この間隔の息子を更新する必要がある場合は、同じことをしなければなりません繰り返しますが、これは時間の無駄です....

もっと良いアイデアはありますか？ネットで検索しましたが、何も見つかりませんでした...

編集:私はあなたの提案に従い、これ(C++)をコーディングし、いくつかの基本ケースで機能しますが、提出すると10/100ポイントしか得られません。何が問題なのですか? (少し長くてコメントが少ないことは承知していますが、遅延伝播を使用した単純なセグメント ツリーです。何かわからないことがあれば教えてください!

注: st[p].zero には、インデックス p に格納された間隔で 0 mod 3 の要素、st[p].one 要素 1 mod 3、および st[p].two 要素 2 mod 3 が含まれます。更新すると、これらの要素 (0->1、1->2、2->0) の位置が 1 つシフトし、lazy を使用します。更新時に、ペア < int 、ペア < int、int > > を返します。これは、3 つの数値を格納する単純な方法です。このようにして、数値 0,1,2 mod 3 の差を返すことができます。

N 個の数字 (すべて正で、4 桁以下) を持つ配列Aが与えられた場合、 2種類のクエリがサポートされます。合計 M 個のクエリがあります。

1. インデックスL,R (両方を含む) で指定された範囲をKで更新します。
2. L,R (両方を含む)で指定された範囲内の最大の要素を返します。

数値をK回更新するということは、数値をK回回転させることを意味します。

たとえば、1234 は 2341 に回転します。

905 は 059 に回転し、059 は 590 に回転します。

注：059と59は別の番号です。59 は 95 に回転します。

指定された配列要素に先行ゼロがありません。

制約:

0 <= AI < 10000

1 <= N <= 800000

1 <= M <= 200000

0 <= K <= 60

ツリーノードが含まれる範囲の回転数を格納するセグメントツリーを考えました。これを遅延伝播で実装しましたが、遅延伝播でもクエリの実装に最悪の場合 O(N) 時間がかかり、TIME LIMIT EXCEEDED につながります。

誰でもより速いアプローチを提案できますか?

配列または構造体の一部のプロパティが不足していますか?

4 つのタイプの多くのクエリに関する質問があります。

1. 範囲に追加します。

2. 範囲を初期化します。

3. 範囲をスカラーで乗算します。

4. ある範囲で現在の合計を見つけます。

膨大な数のクエリがあるため、遅延伝播でセグメント ツリーを使用する必要がありますが、2 種類以上のクエリで遅延伝播を使用する方法に行き詰まっています。後で更新が行われるときに、どのタイプの更新 (つまり、加算、乗算、初期化) が行われるかをどのように識別できますか?

私は spoj から HORRIBLE 問題を試みています。リンクは次のとおりです: http://www.spoj.com/problems/HORRIBLE/ 以下は私が書いたコードです。できるだけ簡潔かつ明確にするように努めました。不明な点があればお知らせください。

提供されたサンプル テストケースは、私のコードで正しい回答を提供しますが、送信すると、間違った回答メッセージが表示されます。コードを何度もチェックしましたが、バグが見つかりません。

どんな助けでも大歓迎です。ありがとう！

セグメント ツリーの遅延伝播の問題に直面しています。私は配列A、長さ N 、より小さい配列 (最大長 20) を持っています。また、配列Aiで現在指しているインデックス i を参照する、インデックスBの配列もあります。

2 つの操作があります。a) 指定された範囲のBのポインターを更新して、次の要素を指すようにします。b) 指定された範囲内でポインターが現在指している値の最大値を出力します。

例えば：-

範囲 1,2 のクエリを作成すると、最大は 8 になります。これは、配列 B のポインターが配列の最初の要素を指しているためです。したがって、1,8 を使用しています。

2,3 max =8; のクエリを作成する場合。これは、値 8,3 を使用しているためです。一般に、

これらは、非常に単純な形式の 2 つの方法です。ただし、入力の制約が大きいため、O(logn) クエリと更新時間が必要です。そのため、セグメント ツリーを使用することを考えました (現在、複雑さは O(n^2) です)。遅延伝播で中間ノードを更新します。

どんな洞察も役に立ちます。また、同様の問題をオンラインでリンクできる場合は、私ができなかったので本当に役に立ちます（これはどのWebサイトからのものでもないため、そのようなものは知りません）。助けてくれてありがとう。

注: その場合は 1b[i]>a[i].lengthに置き換えa[i][b[i]]ます。