次のリンクで質問2を効率的に解決する方法がわかりません：http： //www.iarcs.org.in/inoi/2012/inoi2012/inoi2012-qpaper.pdf
質問する
493 次
1 に答える
2
これは、On log n）時間で実行できます。（または、本当に気になる場合は線形です。）まず、非常に大きな負の数を使用して、入力配列を2の次の累乗にパディングします。次に、区間木のようなデータ構造を構築します。配列を半分に分割することにより、配列を再帰的に分割します。ツリーの各ノードは、長さが2の累乗で、その長さの倍数の位置から始まるサブアレイを表し、各非リーフノードには「左半分」の子と「右半分」の子があります。
0,1,2,3,...ツリー内のノードごとに、そのサブ配列に追加して最大要素を取得するとどうなるかを計算します。これは、長さ1のサブ配列を表す葉では自明であることに注意してください。内部ノードの場合、これは単に長さ/2+右の子を持つ左の子の最大値です。したがって、このツリーを線形時間で構築できます。
次に、このツリーで一連のnクエリを実行し、回答を出力します。クエリの形式は「k,k+1,k+2,...n,1,...,k-1配列に追加して最大値を報告するとどうなりますか？」です。
そのシーケンスを配列全体に追加すると、nと1の間の区切りが最初/最後で発生するか、中央でスマックするか、左半分のどこか、または右半分のどこかで発生することに注意してください。したがって、配列をk,k+1,k+2,...,nパーツとパーツに分割し1,2,...,k-1ます。2つのシーケンスのいずれかに完全に含まれるサブアレイを表すツリー内のすべてのノードを特定するが、その親が存在しないか、ブレークポイントにまたがる場合、O（log n）ノードがあります。それらの値を確認し、さまざまな定数を追加して、最大値を取得する必要があります。したがって、各クエリにはO（log n）時間がかかります。
于 2012-12-29T18:23:38.953 に答える