最初に大きなサイズの配列が与えられ、そのあと区間[a, b]の値にXを加えよとか、区間[c, d]の最大値を求めよとか、区間[e, f]の総和を求めよというクエリが大量に飛んできて、しかもそれらの結果を2秒以内に返せという問題は競技プログラミングではよくみかけます。競技プログラミングでなくてもこのような処理が必要になることは案外多いのではないでしょうか？
これに対応するものとして、今回は平方分割を扱います。
平方分割の考え方
長さ N の整数列 A の区間 A[l_i] … A[r_i] の最大の要素の値を K 回求めたいのですが、与えられる区間の要素をいちいち全て調べていては時間計算量にして最大で O(NK) かかってしまいます。
そこでこう考えます。
1. 長さ N の配列が与えられたら、N の平方根を求め、これを切り上げたものを X とします。配列を長さ x の配列に分割して、それぞれの配列について目的の値（最大値とか区間の総和とか）を調べておきます。N の平方根を切り上げたものが分割された配列の長さになるので、分割された最後の配列の長さは x よりも小さくなる場合があります。
2. 調べたい区間に完全に含まれている配列についての 1. で求めた値と、その配列以外の部分の値をすべて調べて目的の値を求める。
もし長さが100の配列 A が与えられたとしましょう。この場合、長さが10で10個の配列に分解されます。それぞれの配列のなかで最大値や総和を計算します。最大値を M[0] ～ M[9]、総和を S[0] ～ S[9] にそれぞれ格納します。もし区間[18, 31]の最大値を求めよというクエリが飛んできたら、A[18] から A[31] までを調べるのではなく、A[18], A[19], M[2], A[30], A[31] の5つのなかから最大値を求めます。これなら計算量を大幅に落とすことができそうです。
平方分割の実践例
たとえばこんな問題が出されたとしましょう。
テストの返却中に暇だった paiza 君は 2人で遊ぶゲームを思いつきました。
2人はそれぞれ生徒番号 1 ～ N の全校生徒 N 人の中から生徒番号が連続するように好きな人数の生徒を選ぶ。その選んだ生徒達の得点の幅が大きい方、すなわちその生徒たちの (最高点 – 最低点) の値が大きい方が勝ち、同じだったら引き分けというものです。
学校の生徒数 N と試合の数 K , 各生徒の得点 S_1 … S_N と、i 番目の試合で対戦した A と B の 2 人が選んだ生徒の最小の生徒番号と最大の生徒番号が与えられます。各試合のジャッジをしてください。
入力される値
N K
S_1
…
S_N
A_{l_1} A_{r_1} B_{l_1} B_{r_1}
…
A_{l_K} A_{r_K} B_{l_K} B_{r_K}1 ≦ N, K ≦ 10,000 ただし N は 平方数である）
0 ≦ S_i ≦ 100,000 (1 ≦ i ≦ N)
1 ≦ Al_i ≦ Ar_i ≦ N (1 ≦ i ≦ K)
1 ≦ Bl_i ≦ Br_i ≦ N (1 ≦ i ≦ K)
あいかわらず paiza 君は変なことばかり考えています。ただ鳩はAtCoderにも取り組んでいるのですが、その問題文のなかに登場する高橋君とすぬけ君コンビの奇行はさらに上を行っているように思えます。
これは平方分割とは関係ないのですが、こんな問題があります。
こんな破壊活動を繰り返していては高橋君はそのうち警察に捕まります。
さて横道にそれた話をもとに戻して、審判役を任されたpaiza君を助けてあげることに全力を傾注しましょう。
平方分割で区間の最大値と最小値を素早く求める
さて N と K が最大で 10,000 なので普通にやっていては間に合いません。そこで平方分割を使います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { // とりあえず標準入力から N, K を取得 int N, K; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; K = vs[1]; } // N の平方根を取得（N は平方数であることが保証されているのでやりやすい） int root = (int)Math.Sqrt(N); // 長さが root の部分配列が root 個できるが、それらの最大値と最小値を格納する配列をつくる int[] rangeMax = new int[root]; int[] rangeMin = new int[root]; // rangeMin[i] を初期化（初期値はintで取りうる最大値とする） for (int i = 0; i < root; i++) rangeMin[i] = int.MaxValue; // S_iの最小値は0であることが保証されているので rangeMax[i] の初期値は0でよい // つまりなにもしなくてよい // 1人1人のテストの成績を取得して 配列 scores に格納する // 同時にこの処理が終わったときに // rangeMax rangeMin にも区間の最大値と最小値が格納されているようにする int[] scores = new int[N]; for (int i = 0; i < N; i++) { int score = int.Parse(Console.ReadLine()); scores[i] = score; rangeMax[i / root] = Math.Max(rangeMax[i / root], score); rangeMin[i / root] = Math.Min(rangeMin[i / root], score); } // 勝敗の結果を示す文字列を格納するリスト List<string> rets = new List<string>(); // 勝敗をジャッジするクエリが K 件 飛んでくるので対応する for (int i = 0; i < K; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = 0; int b = 0; for (int k = 0; k < 2; k++) { int start = k == 0 ? vs[0] - 1: vs[2] - 1; int end = k == 0 ? vs[1] - 1 : vs[3] - 1; // 閉区間[start, end] のうち rangeMax や rangeMin が完全にカバーしている区間であれば // それを活用する。そうでない場合は scores[i] の値をひとつひとつ調べる int cur = start; int min = int.MaxValue; int max = 0; while (cur <= end) { // cur % root == 0 && end >= cur + root - 1 であれば start ～ end は // rangeMax, rangeMin を完全にカバーしていて cur はその区間の先頭である // その場合は cur の次の値は cur ＋ 1 ではなく cur ＋ root である // このループを抜けたときに A君 または B君の選んだ区間の最高点と最低点は取得できている if (cur % root == 0 && end >= cur + root - 1) { max = Math.Max(rangeMax[cur / root], max); min = Math.Min(rangeMin[cur / root], min); cur += root; } else { max = Math.Max(scores[cur], max); min = Math.Min(scores[cur], min); cur++; } } // A君 または B君の選んだ区間の（最高点 - 最低点）を計算する if (k == 0) a = max - min; else b = max - min; } // A君 と B君が選んだ区間の（最高点 - 最低点）の大小関係から勝者がわかるので // 結果を表示するためのリスト内に格納する if (a > b) rets.Add("A"); else if (a < b) rets.Add("B"); else rets.Add("DRAW"); } // 最後に試合の結果を出力するだけ foreach (string ret in rets) Console.WriteLine(ret); } } |
今後の課題
この問題では最初に与えられた配列の値が更新されるというクエリはありませんでした。しかし平方分割はこのようなクエリにも対応できます。また区間の値を更新するときもすべての要素をそのつど更新するのではなく、区間で処理をおこないます。この場合は遅延伝搬というテクニックが必須となります。この件については別の記事で書きます。
