ARC 098 E - Range Minimum Queries

• 問題
• AC

数列$A_1, A_2,...$を昇順に並べ替えたものを$A'_1 \le A'_2 \le ...$とする。最大値-最小値をすべて試すなら、だいたい次のようになるはずだ。

1. 数列$(A_i)$の小さいほうから$Q$個取り除いて最大値-最小値を求める。
2. $A'_1$を残したままにしつつ$(A_i)$からできるだけ小さい数を取り除いてゆき、$Q$個取り除けたら最大値-最小値を求める。
3. $A'_1, A'_2$を残したままにしつつ$(A_i)$からできるだけ小さい数を取り除いてゆき、$Q$個取り除けたら最大値-最小値を求める。
4. …

これは高々${\mathcal O}(N)$ステップで済むので、ひとつひとつのステップが${\mathcal O}(N)$か${\mathcal O}(N \log N)$くらいで実行できればよい。

小さい数を取り除いていく具体的な手順を与えるために、上のステップ3について考えてみる。$A'_1 = A_p, A'_2 = A_q$とする。

$A_1, A_2, ..., A_{p-1} \ | \ A_{p+1}, A_{p+2}, ..., A_{q-1} \ | \ A_{q+1}, A_{q+2},..., A_N$

$A_p$, $A_q$を残したまま数を取り除いていくというのは、上の数列の縦線をまたがないように連続した$K$個を選んで、その最小値を除いていくということにほかならない。なぜなら$A_p, A_q$はほかの数より小さいので、縦線をまたぐと$A_p, A_q$が取り除かれてしまうからだ。つまり、$(A_i)$を複数の独立した数列に分割してそれぞれの最小値を見ればよさそうだ。

さて、「複数の独立した数列」をどう管理すればよいかが問題である。上の３つの部分列を${\mathcal A_1}, {\mathcal A_2}, {\mathcal A_3}$とする。これらの数列から小さい数を除いていくとき、数列の最小値と長さにしか興味がないので、${\mathcal A_1}, {\mathcal A_2}, {\mathcal A_3}$はそれぞれ（昇順の）優先度付きキューで表すことができる。さらに、${\mathcal A_1}, {\mathcal A_2}, {\mathcal A_3}$自身も優先度付きキュー${\mathcal Q}$にいれることにし、${\mathcal Q}$の順序は${\mathcal A} \le {\mathcal A}' : \Leftrightarrow$ ${\mathcal A}$の最小値$\le$${\mathcal A}'$の最小値 とする。

一般に、$l$個の部分列から$Q$個の数を取り除く操作を書き下すと、次のようになる。

• ${\mathcal A_1}, {\mathcal A_2}, ..., {\mathcal A_l}$の中で長さが$K$以上であるものだけ${\mathcal Q}$に入れて、残りは捨てる。
• 次のステップを最大$Q$回繰り返す。
  1. ${\mathcal Q}$の先頭から数列${\mathcal A}$を取り出す。
  2. ${\mathcal A}$の最小値を取り出す。
  3. ${\mathcal A}$の長さがまだ$K$以上なら${\mathcal Q}$に戻し、$K$未満なら捨てる。
• ${\mathcal Q}$が空になる前に$Q$個の数を取り出せたなら、その最大値-最小値を求める。

以上で答えが求まる。全体の計算量は${\mathcal O}(N^2 \log N)$。

---

問題を読んだときは$N$が小さいので何をやってもできそうな気がしたけど、具体的な手順を与えるのに膨大な時間をかけてしまった。