問題タブ [segment-tree]

私は次のコードを持っています。これは、遅延伝播を使用したセグメント ツリー用で、なんとか書くことができました。このコードは、範囲内のすべての数値に x などの値を掛ける場合には機能しません。update_mult 関数で何か間違ったことをしていると思います。ツリーは、範囲の合計を維持します。

update_mult の問題がわかりませんでした。専門家の皆さん、実装のどこが間違っているのかを見つけるのを手伝ってくれませんか?

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

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

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

更新された新しい値が現在の値より小さい場合にのみ、セグメント ツリーを更新できるかどうか疑問に思っていました。

例えば。a[i]toa[j]は to に x に更新されます

これはどのように行うことができますか？

遅延伝播は、私が目指しているものです。

条件付きで BIT の範囲更新を実行できますか。負と正の周波数 A[] = {1, -3, -4, 5, 9} の配列があるとします。そして、条件を使用して配列の値を範囲更新したかった：更新値（x）が負の場合は負の要素のみを更新し、更新値が正の場合は範囲​​内の正の値のみを更新します。

たとえば、上記の配列で、更新クエリが 2 4 -2 (左右の値) の場合、2 番目 (-3) と 3 番目 (-4) の位置のみを更新します。正の整数であるため、4th(5) の位置を残します。

または、これを達成するために別のデータ構造を使用する必要がありますか?

これを使用して、範囲の更新を学習しました。

N 個のジョブが与えられ、すべてのジョブは次の 3 つの要素で表されます。

1) 開始時間

2) 終了時間。

3) 関連する利益または価値。

サブセット内の 2 つのジョブが重ならないように、ジョブの最大利益サブセットを見つけます。

O（N ^ 2）の複雑さを持つ動的計画法ソリューションを知っています（現在の間隔をマージし、マージがi番目まで最大になる間隔を取る前の要素をチェックする必要があるLISに近い）このソリューションは、バイナリ検索と単純な並べ替えを使用して O(N*log N ) にさらに改善できます。

しかし、私の友人は、セグメント ツリーと二分探索を使用することによっても解決できると教えてくれました。セグメント ツリーをどこで、どのように使用するかについての手がかりがありません。

手伝ってくれますか？

リクエストに応じて、申し訳ありませんがコメントされていません

私がやっていることは、開始インデックスに基づいてソートし、前の間隔とそれらの最大取得可能値をマージして、DP[i] に i まで取得可能な最大値を格納することです!

編集: 私の作業コードは、最終的にデバッグするのに3時間かかりました! さらに、このコードは、定数が大きく、実装が悪いため、バイナリ検索およびソートよりも遅くなります:P (参照用)

これは、セグメント ツリーを使用した rmq です。しかし、正しい出力が得られません。どこが間違っているのか誰か教えてください。
`

`
このコードの出力:
0
1 ～ 2 の範囲の期待される出力は 2 関数 get_min_util return 0 from if 条件 ////////c1 が書かれている場所

だから私は再び助けが必要です.私は最近codechefで中レベルの問題を始めたので、TLEをかなり多く受けています.

したがって、基本的に問題は、質問で指定された複数の最大範囲クエリの合計を見つけることです。最初の範囲が指定され、問題で指定された式によって次の値が計算されます。

この問題を解決するためにセグメント ツリーを使用しましたが、いくつかのサブタスクで TLE を取得し続けています。このコードの最適化を手伝ってください。

問題のリンク - https://www.codechef.com/problems/FRMQ

範囲内の最大要素を見つけるために、このセグメントツリーの実装を行っています:

そして主に私はこのようなことをしています:

しかし、それは間違った結果をもたらします。入力 N=5 および M=1 の場合と同様に、配列は [3,1,3,2,1] であり、クエリ L=1,R=1 の場合は 8 になります。バグを見つけるのを手伝ってください。

私は自分のコードの問題点を見つけることができません:(

コードに示されているように、指定された問題を解決しましたが、間違った答えが返ってきました。セグメント ツリー アプローチを使用しました。node には、max1 (指定された範囲内の最大数) と sum (指定された範囲内の 2 つの最大数の合計) が含まれます。助けてください。