連載しょぼんコーダー 3 イベントソート

第3回では, イベントソートと呼ばれる, 時刻・位置順にイベント（変化する点）をソートして, イベントを時刻・位置順に走査することで, 目的のクエリについて答えていくテクニックについて書きます.

問題1

例題3 ABC248 D - Range Count Query (Diff: 793)
長さ $N$ の数列 $A = (A_1, \cdots, A_N)$ が与えられます。
以下の形式で与えられる $Q$ 個のクエリに答えてください。

整数 $L,R,X$ が与えられる。 $A_L , \cdots, A_R$ のうち、値が $X$ に等しいものの個数を求めよ。

時間制限：2秒、メモリ制限：1024 MB
制約

$1 \leq N \leq 2 \times 10^5$

$1 \leq A_i \leq N$

$1 \leq Q \leq 2 \times 10^5$

各クエリについて、 $1 \leq L_i \leq R_i \leq N, 1 \leq X \leq N$

$1 \leq X_i \leq 10^9$

入力はすべて整数

考察

$A_1, \cdots, A_m$ の中の $x$ の個数を $\text{count}(m, x)$ とすると, 各クエリは, $\text{count}(R, X) - \text{count}(L-1, X)$ を求めればよいことになります.
$\text{count}(m, x)$ をすべて記録しようとすると, 時間もメモリも足りません. しかし, $A_1, A_2, \cdots$ と順番に数列 $A$ を見ていくと, 各 $m=1,2,\cdots, N$ について $\text{count}(m-1, x)$ から $\text{count}(m, x)$ への更新は, たった1つの $A_m$ について $1$ 増えて, あとは変わらないので $O(1)$ で出来ます. ここで, 瞬間的に任意の $x$ について $\text{count}(m, x)$ が求まります.
このタイミングで, どこかのクエリの $R, L-1$ が引っ掛かったら, $\text{count}(R,X), \text{count}(L-1,X)$ を足したり引いたりすれば理想的です.
そこで, それぞれの『位置』 $R, L-1$ とクエリ番号を記録したものを, 『位置』でソートして, 数列を見ていって『位置』が引っかかれば操作をすることを考えます.
「それぞれの『位置』 $R, L-1$ とクエリ番号を記録したもの」をeventとして, eventを位置でソートします. これがイベントソートです. 計算量は $2Q$ ある数列のソートがボトルネックになり, $O(Q \log Q)$ です.
ソースコードのpivotは, eventを『位置』pivotまで見たという指標です. eventの『位置』は単調増加なので, pivotも1ずつ増えていき, 結局pivotを増やす操作は $2Q$ 回しか行わないため, 後半部分では $O(N+Q)$ です.

n = int(input())
a = list(map(int,input().split()))
q = int(input())

count = [0] * (n+1)
event = []
ans = [0] * q
for i in range(q):
	l,r,x = map(int,input().split())
	event.append((l-1, 0, x, i)) #位置, L-1 or R, 値, ansの番号
	event.append((r, 1, x, i))

event.sort()
pivot = 0
for i in range(n+1):
	while pivot < 2 * q:
		if event[pivot][0] == i:
			if event[pivot][1] == 0:
				ans[event[pivot][3]] -= count[event[pivot][2]]
			else:
				ans[event[pivot][3]] += count[event[pivot][2]]
		else:
			break
		pivot += 1
	if i == n:
		break
	count[a[i]] += 1

for i in range(q):
	print(ans[i])

上では $A_i$ を見るfor文の中にwhile文でeventを処理していましたが, 実は「 $A_i$ を見る処理」と「クエリに答える処理」をひとまとまりにして両方eventと扱うことで, より簡潔に書くことができます. こちらはソートする数列の長さが $N+2Q$ となるので, $O( (N+Q) \log (N+Q) )$ で, さきほどとは計算量はやや劣りますが, 非常に簡潔です.
先にしたい処理からeventのtupleの2つ目を昇順をすることで, 同じ『位置』のときに処理の順番を決めることができます.

n = int(input())
a = list(map(int,input().split()))
q = int(input())

count = [0] * (n+1)
ans = [0] * q
event = []

for i in range(n):
	event.append((i, 2, a[i], -1)) #位置, 数列処理は最後, 値, (使わない)

for i in range(q):
	l,r,x = map(int,input().split())
	event.append((l-1, 0, x, i)) #位置, L-1 or R, 値, ansの番号
	event.append((r, 1, x, i))

event.sort()
for ind, t, val, qind in event:
	if t == 0:
		ans[qind] -= count[val]
	elif t == 1:
		ans[qind] += count[val]
	else:
		count[val] += 1

for i in range(q):
	print(ans[i])

$A_i$ もクエリもひっくるめてはいハッピーって感じです. 計算量は劣りますが, 非常に書きやすい書き方になっております.
今回, $1 \leq A_i \leq N$ という条件があるので, 各 $m$ について操作をするもの全体のリストを作ることができて, こっちだと（イベントソートに近い操作ですが）ソートする必要がなく, $O(N+Q)$ で実現可能です. これはバケットソートと呼ばれているそうです.
バケットソートによる解法で良いユーザー解説があったので, 詳しくはこちらをご覧ください.
Editorial - UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248）

計算量的には劣るかもしれませんが, もし, 数列 $A_i$ ではなく, 数直線上のとびとびの点の集合であったら, 後者の全部ひっくるめるイベントソートがよく使えます.

次の例題を見てみます.

問題2

例題4 (想定Diff : 1000)
喫茶店しょぼんに, ある日 $1, 2, \cdots, N$ の番号が振られた $N$ 人が店にちょうど1回出入りしました.
人 $i$ は, 年齢が $A_i$ で, 時刻 $L_i$ ちょうどに店に入り, 時刻 $R_i$ ちょうどに店を出ました.
さて, 店長であるしょぼんは時刻によって店内の年齢層がどれほど違うか調べたいと思い, 特定の時刻に店内にいた人の年齢の平均値を求めたいと思いました.
そこで, 各 $i = 1, 2, \cdots, Q$ について, 時刻 $X_i + 0.5$ に店内に居た人の年齢の平均値を出力してください. ただし, 時刻 $X_i + 0.5$ に店内に誰も居なかった場合は $-1$ を出力してください.
時間制限：4秒、メモリ制限：1GB
制約

$1 \leq N \leq 2 \times 10^5$

$1 \leq A_i \leq 10^9$

$1 \leq L_i < R_i \leq 10^9$

$1 \leq Q \leq 2 \times 10^5$

$1 \leq X_i \leq 10^9$

入力はすべて整数

入力は次のようになります.
N
A_1 L_1 R_1
A_2 L_2 R_2
...
A_N L_N R_N
Q
X_1
X_2
...
X_Q
出力は $Q$ 行で, $i$ 行目( $i=1,2,\cdots, Q$ )には時刻 $X_i + 0.5$ に店内にいた人の年齢の平均値（店内にいた人が0人であった場合は $-1$ ）を出力してください. ただし, 相対誤差は $10^{-9}$ まで許容されます.
SAMPLE
入力
3
22 7 12
25 8 22
29 2 7
3
5
8
31415926
出力
29.0
23.5
-1
1行目：時刻 $5.5$ には, 年齢 $29$ の人 $3$ のみが店内にいるので $29$ を出力してください.
2行目：時刻 $8.5$ には, 年齢 $22$ の人 $1$ と, 年齢 $25$ の人 $2$ が店内にいるのでその平均である $23.5$ を出力してください.
3行目：時刻 $31415926.5$ には, 誰も店内にいないので $-1$ を出力してください.

考察

すべての時刻を $-0.5$ 平行移動すると, 各クエリは $X_i$ と整数値になって, 人 $i$ は時刻 $L_i - 0.5$ から時刻 $R_i - 0.5$ まで店内にいるので, 整数の区間を考えると店内にいる時刻の区間は $[ L_i, R_i )$ となります. 以降, すべての時刻は $-0.5$ 平行移動したことにします.
$X_i$ に店にいる $k$ 人を $p_1, p_2, \cdots, p_k$ とすると, 年齢の平均値は $(A_{p_1} + A_{p_2} + \cdots + A_{p_k}) / k$ となります. よって, $X_i$ に店内にいる人数と, $X_i$ に店内にいる人の年齢の合計を個別に求めれば平均値を求められます.
まず, 各 $X_i$ について人 $1,2,\cdots, N$ が店内にいるかどうかを調べるという方法は, 簡単に実装できますが $O(NQ)$ かかり間に合いません.
そこで, イベントソートを使いましょう. 店内にいる人の人数を $x$ , 店内に居る人の年齢の合計を $y$ とします.
各人 $i$ について, $L_i$ になった瞬間, $x$ を $+1$ , $y$ を $+A_i$ して, $R_i$ になった瞬間, $x$ を $-1$ , $y$ を $-A_i$ します.
これを時系列順にやればよいのですが, まず $L_i, R_i$ をeventに追加します.
また, $X_i$ の時刻での $x / y$ の値を求めないといけないので, $X_i$ もごちゃまぜでeventに追加します.
あとはeventをソートすればokです！！ $X_i$ の処理を後に行う必要があることと, $X_i$ の番号通りに出力する必要があることに注意してください.
計算量は $O( (N+Q) \log (N+Q) )$ で, 間に合います.

n = int(input())

a = [0] * n
event = []
for i in range(n):
	at, l, r = map(int,input().split())
	a[i] = at
	event.append((l, 0, i)) #時刻, タイプ, 番号
	event.append((r, 1, i))

q = int(input())
ans = [0] * q

for i in range(q):
	x = int(input())
	event.append((x, 2, i))

event.sort()

X = 0
Y = 0
for time, t, ind in event:
	if t == 0:
		X += 1
		Y += a[ind]
	elif t == 1:
		X -= 1
		Y -= a[ind]
	else:
		if X == 0:
			ans[ind] = -1
		else:
			ans[ind] = Y/X

for i in range(q):
	print(ans[i])

imos法

いまやっていた操作（走査）, imos法と似ていませんでしたか？
そうです. 今の問題が数列だったら, imos法が使えていました. しかし, 数直線上飛び飛びのデータなので, ただ単にimos法を適用するのは難しいのです.
でも, 数直線上飛び飛びのデータを数列にする方法は存在します. 座標圧縮です. こちらも重要なテクニックです.
一部のイベントソートは, 座標圧縮＋imos法で同じことができます. 今回の問題は座標圧縮＋imos法で書くことができます.
座標圧縮のコードについては, こちらをコピペしました.
座標圧縮 - yaketake08's 実装メモ

def compress(arr):
	*XS, = set(arr)
	XS.sort()
	return {cmp_e: cmp_i for cmp_i, cmp_e in enumerate(XS)}

n = int(input())

people = [] * n
detekuru = []
for i in range(n):
	a, l, r = map(int,input().split())
	people.append((a, l, r))
	detekuru.append(l)
	detekuru.append(r)

q = int(input())
query = []

for i in range(q):
	x = int(input())
	detekuru.append(x)
	query.append(x)

c = compress(detekuru)

size = len(c)
X = [0] * size
Y = [0] * size

for a, l, r in people:
	X[c[l]] += 1
	X[c[r]] -= 1
	Y[c[l]] += a
	Y[c[r]] -= a

for i in range(size-1):
	X[i+1] += X[i]
	Y[i+1] += Y[i]

for x in query:
	if X[c[x]] == 0:
		print(-1)
	else:
		print(Y[c[x]] / X[c[x]])

どんなときに使えるか

区間の端点・またはある一点のみで状況が変化して, その点を時系列順に処理すると各時刻の状況が簡単に分かるとき, このイベントソートはよく使えます.
そのとき, 各時刻の状況をすべてメモ化すると場合によっては時間・空間計算量が膨大になりますが（問題1の $\text{count}$ 関数）, それをしなくてもよいことが特徴です.