狠狠撸

狠狠撸Share a Scribd company logo

Rmq

?
?
O
oupc
1 of 10
Downloaded 19 times
Range Minimum Query  原案、問題文：宮村  解答：宮村  解説：宮村
問題概要  RMQ( 区間更新アリ ) のクエリ内容が与えられる ので復元が可能かどうか判定せよ。  クエリ数 ≦ 5*10^4
準備  インデックスの範囲が大きいので座標圧縮する。  クエリを [a,?b] のような閉区間で扱うのではなく、 [a,?b+1) の半開区間で考えるようにするとよい。  座標圧縮は a,?b+1 に対して行うようにする。  うっかり座標圧縮しすぎると WA になるので注意。 例えば [40,?55],?[55,?70],?[40,?70] を [1,2],[2,3], [1,3] と同じとみなしてはいけない。
解法 ( アウトライン )  実際に初期値の候補を構成して RMQ をシミュ レーションし、クエリ内容と一致するか判定する。  初期値の候補をどう作るか？
解法 ( 初期値の構成 )  ?min?(X[i])?=?y?(a?≦?i?<?b) という情報から X[i]≧y が得られる。  ?X[i] に何かを代入するとき ( 初回のみ ) は、今得 られている X[i] の下限を X[i] の初期値候補とし て選べばよい。
解法 ( 初期値の構成 )  結局、以下ができるデータ構造があればよい。  1.?z[i]?=?max(z[i],?y)??(a≦i<b) と更新する。  2.?z[i] の値を求める。  これは segment?tree などを使うとどちらのクエリも O(log?N) で処理できる。  平方分割でもよい。
解法 (RMQ)  得られた初期値を元に RMQ をシミュレーションす る。  プログラミングコンテストチャレンジブックなどで紹 介されている RMQ は点に対する更新だけだが、 実は区間に対する更新も効率的に処理できる。
解法 (RMQ, segtree)  区間に対する処理が得意な segment?tree で考えて みる。  区間に対するクエリが複数ある場合は、各ノードが 複数のデータを持つことが多い。  各ノードは「その区間内の最小値」と「その区間内 は全て等しいかどうか」というフラグを持つ。  更新処理の際は、完全に含まれる区間はフラグを オンにする。  最小値を求める際は、フラグがオンになっていたら 即座に最小値を返すようにする。
解法 (RMQ, 平方分割 )  計算量で劣るものの、 segment?tree を使わずに平 方分割を用いても RMQ は実現できる。平方分 割の方がやや記述は楽になる。  各バケットは、「バケット内の最小値」と「そのバケッ トが全て等しいかどうかを表すフラグ」を持つ。  更新処理の際は、完全に含まれるバケットは全て 等しいかどうかを表すフラグをオンにする。  最小値を求める際は、端以外はバケット内の最小 値だけを見て、端はバケットが全て等しいならば バケット内の最小値を返し、そうでないなら真面 目に調べる。
解答例  宮村： C++ ??235 行 4921?byte?(segment?tree) ??236 行 4669?byte?( 平方分割 )

More Related Content

Rmq

  • 1. Range Minimum Query  原案、問題文：宮村  解答：宮村  解説：宮村
  • 2. 問題概要  RMQ( 区間更新アリ ) のクエリ内容が与えられる ので復元が可能かどうか判定せよ。  クエリ数 ≦ 5*10^4
  • 3. 準備  インデックスの範囲が大きいので座標圧縮する。  クエリを [a,?b] のような閉区間で扱うのではなく、 [a,?b+1) の半開区間で考えるようにするとよい。  座標圧縮は a,?b+1 に対して行うようにする。  うっかり座標圧縮しすぎると WA になるので注意。 例えば [40,?55],?[55,?70],?[40,?70] を [1,2],[2,3], [1,3] と同じとみなしてはいけない。
  • 4. 解法 ( アウトライン )  実際に初期値の候補を構成して RMQ をシミュ レーションし、クエリ内容と一致するか判定する。  初期値の候補をどう作るか？
  • 5. 解法 ( 初期値の構成 )  ?min?(X[i])?=?y?(a?≦?i?<?b) という情報から X[i]≧y が得られる。  ?X[i] に何かを代入するとき ( 初回のみ ) は、今得 られている X[i] の下限を X[i] の初期値候補とし て選べばよい。
  • 6. 解法 ( 初期値の構成 )  結局、以下ができるデータ構造があればよい。  1.?z[i]?=?max(z[i],?y)??(a≦i<b) と更新する。  2.?z[i] の値を求める。  これは segment?tree などを使うとどちらのクエリも O(log?N) で処理できる。  平方分割でもよい。
  • 7. 解法 (RMQ)  得られた初期値を元に RMQ をシミュレーションす る。  プログラミングコンテストチャレンジブックなどで紹 介されている RMQ は点に対する更新だけだが、 実は区間に対する更新も効率的に処理できる。
  • 8. 解法 (RMQ, segtree)  区間に対する処理が得意な segment?tree で考えて みる。  区間に対するクエリが複数ある場合は、各ノードが 複数のデータを持つことが多い。  各ノードは「その区間内の最小値」と「その区間内 は全て等しいかどうか」というフラグを持つ。  更新処理の際は、完全に含まれる区間はフラグを オンにする。  最小値を求める際は、フラグがオンになっていたら 即座に最小値を返すようにする。
  • 9. 解法 (RMQ, 平方分割 )  計算量で劣るものの、 segment?tree を使わずに平 方分割を用いても RMQ は実現できる。平方分 割の方がやや記述は楽になる。  各バケットは、「バケット内の最小値」と「そのバケッ トが全て等しいかどうかを表すフラグ」を持つ。  更新処理の際は、完全に含まれるバケットは全て 等しいかどうかを表すフラグをオンにする。  最小値を求める際は、端以外はバケット内の最小 値だけを見て、端はバケットが全て等しいならば バケット内の最小値を返し、そうでないなら真面 目に調べる。
  • 10. 解答例  宮村： C++ ??235 行 4921?byte?(segment?tree) ??236 行 4669?byte?( 平方分割 )