初めに
競技プログラミングにおいて、よく「平面走査」というテクニックが登場します。これは AtCoder 水or青以降ではよく要求される知識ですが、これについて詳細に書かれた記事は（ほかの同程度の難易度のテクニックと比べ）少なく、書いておく必要があると感じました。
前提知識として、BIT(Fenwick Tree)、セグメント木、座標圧縮について使い方を知っていることを前提とします。わからない場合は、インターネット上によい記事がたくさんあるので、適宜調べてください。
平面走査で解ける問題の例
平面走査は、2次元平面上で表現されるなんらかに対するクエリを処理するために、座標でソートしてうまい感じにやるテクニックの総称です。具体例を見ながら考えていきましょう。平面走査で解ける問題の例を挙げます。
問題1. 転倒数
$(1, 2, \dots, N)$ を並べ替えた列 $P_i = (P_1, P_2, \dots, P_N)$ が与えられます。$i < j$ かつ $P_i > P_j$ であるような $(i, j)$ の個数を求めてください。$(1 \leq N \leq 100000)$
ジャッジ: https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_j
この問題の難しいポイント
愚直な方法では、時間計算量は $\Theta(N^2)$ になるでしょう。これでは制約上時間制限に間に合わないです。
この問題の難しいポイントは、$(i, j)$ と $(P_i, P_j)$ という2種類のパラメータを同時に扱わなければならない点です。これをどうにかして1種類に減らせないだろうか？というのが平面走査の基本アイデアです。
j の昇順で解決！
$j$ を固定して $j$ の昇順に答えを計算してみます。$i < j$ を満たす $i$ すべてに対する $P_i$ の値を記録した配列 $A$ をつくります。$A$ に入る要素はすべて $i < j$ を満たすので、転倒数は、$A$ に含まれる $P_j$ より大きい値の個数の総和となります。
$P = (5, 1, 4, 2, 3)$ の場合を考えましょう。
- $j = 1$ のとき、 $i < j$ を満たす $i$ はないので $A = ()$ よって、$P_1 = 5$ より大きい数の個数も $0$ 個
- $j = 2$ のとき、 $A = (5)$ よって、$P_2 = 1$ より大きい数の個数は $1$ 個
- $j = 3$ のとき、 $A = (5, 1)$ よって、$P_3 = 4$ より大きい数の個数は $1$ 個
- $j = 4$ のとき、 $A = (5, 1, 4)$ よって、$P_4 = 2$ より大きい数の個数は $2$ 個
- $j = 5$ のとき、 $A = (5, 1, 4, 2)$ よって、$P_5 = 3$ より大きい数の個数は $2$ 個
よって、転倒数は $1 + 1 + 2 + 2 = 6$ と計算できました。
数列 $A$ から $P_j$ より大きい数の個数を数える部分は、普通にやってしまうと $\Theta (|A|)$ の計算量がかかるので、これを愚直にやってしまうと結局計算量は変わらず $\Theta (N^2)$ です。なんとか高速化を考えます。
データ構造で高速化
$j$ が増えたとき、$A$ に要素が $1$ つ追加されることがわかります。よって、次の形式の問題Xが解ければ十分です。
問題X
空の数列 $A = ()$ がある。以下の形式のクエリを順に処理せよ。
- クエリ1: $A$ に $x$ $(1 \leq x \leq N)$を追加する。
- クエリ2: $A$ に含まれる $x$ より大きい値の個数を答える。
問題Xの解法
この問題は、BITを使って解くことができます。
BITは、長さ $N$ の数列 $B$ に対して、次の操作がそれぞれ操作ごとに $O( \log N)$ でできるデータ構造でした。
- 操作1: $B_i$ に $x$ を足す。つまり、$B_i \leftarrow B_i + x$
- 操作2: $B$ の $r$ 項目までの総和を求める。 つまり、$\sum_{i = 1}^{r} B_i$ を求める。
これを使うことで、問題Xを高速に解くことができます。長さ $N$ の配列 $B = (0, 0, \dots, 0)$ を用意します。
クエリ1に対しては $B_x \leftarrow B_x + 1$ をして、クエリ2に対しては $\sum_{i = 1}^{n} B_i - \sum_{i = 1}^{x} B_i$ を計算すればよいです。先述のとおり、これらはBITで高速に計算できます。
よって、問題Xはクエリ数を $Q$ 個として、計算量 $O(Q \log N)$ で解くことができます。
問題Xが解けたので、同じようにすることで転倒数を $O(N \log N)$ で求めることができることもわかりました。
平面走査まとめ
今回は転倒数を例にとって説明しました。$j$ の昇順で処理を行うことによって、2種類のパラメータを1つにまとめることに成功し、データ構造で高速化できる形式となったため、高速に解けました。一般に、平面走査においてソートして処理順を決めると次の形の問題に帰着されることが多いです。
問題X（一般化）
数列 $A$ がある。以下の形式のクエリを順に処理せよ。
- クエリ1: $A$ に $x$ を追加する。
- クエリ2: $l \leq A_i \leq r$ を満たす $A_i$ すべてに対する何らかの演算の結果を求めよ。
この何らかの演算の結果がBITやセグメント木で高速に計算できるものであれば、次の解法が有効になります。
問題Xの解法（一般化）
クエリ1で与えられる値 $x$ の最大値を $N$ とする。長さ $N$ の配列 $B$ を用意し、BIT（セグメント木）で管理する。クエリ1に対しては $B_x$ の値を適切に更新し、クエリ2に対してはBIT（セグメント木）の区間演算を用いて答える。
この一般化は平面走査ではほぼ共通した部分なので、フレームワークとして覚えておいてもよいかもしれません。
また、平面走査は基本的にソートやクエリ先読みを必要とするので、オフラインでの処理が前提となります。
問題演習
平面走査で解ける問題を2つ紹介します。非常に有名な問題なので、一度考えてみてください。ヒントを詳しめに書いておくので、ネタバレが嫌な人は問題名だけ見てください。
問題2. LIS
順列 $P$ が与えられます。最長狭義単調増加列(LIS)の長さを求めてください。
ジャッジ: https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_h
ヒント: 各 $j$ について $P_j$ が末尾である増加列の長さの最大値 $\mathrm{dp}_j$ がわかれば十分です。$\mathrm{dp}_j$ は、$i < j$ かつ $P_i < P_j$ を満たす $i$ に対する $\mathrm{dp}_i$ の最大値 $\mathrm{maxi}$ がわかれば、$\mathrm{dp}_j = \mathrm{maxi} + 1$ として求めることができます。これは、問題Xの最大値バージョンなので、セグメント木で高速に計算できます。
問題3. Rectangle Sum
2次元平面上に重み付きの点が $N$ 個ある。 $i$ 個目の点は座標 $(x_i, y_i)$ にあり、重みは $w_i$ である。
以下の形式のクエリが $Q$ 個与えられるので答えよ。$(1 \leq N, Q \leq 200000)$
- $l, r, u, v$ : $l \leq x_i < r, u \leq y_i < v$ を満たす点すべてに対する $w_i$ の総和を求めよ。
ジャッジ: https://judge.yosupo.jp/problem/rectangle_sum
ヒント: クエリ $(l, r, u, v)$ は、$(0, r, u, v) - (0, l, u, v)$ として計算できます。よって、$l = 0$ の場合が解ければ十分です。$x_i$ でソートして、$x_i$ の昇順に処理すると、問題Xと同様の形式となります。座標の値が大きいので、事前に座標圧縮する必要があります。