https://atcoder.jp/contests/abc365/tasks/abc365_g
公式解説に倣い、$i$番目の高橋くんがオフィスの中にいた時間の区間の集合を$S_i$とする。
クエリの組$(A, B)$について、下記パターンI, Ⅱに分けて考える。
パターンI:
愚直にイベントソートして処理。
高橋くんそれぞれのイベントを予め分けておく。
クエリの組$(A, B)$のイベントをマージ→重複している時間を求める。
クエリ1回あたり$O(C_{})$かかる(イベントは入力でソート済みなのでlogはかからない)。
クエリ$Q$回全部$C$以下があり得るので、クエリ全体で$O(QC)$かかる。
パターンⅡ:
クエリの組$(A, B)$は、
・$C$より大きい高橋くんが$\frac{M}{C}$
・任意の高橋くんが$N$
この2種から1つずつ選ぶので$O(\frac{NM}{C})$個のクエリがパターンⅡに当てはまり得る。
これらクエリを予め計算してキャッシュし、クエリに答えるようにする。
$S_i$が$C$を超える高橋くんを$i$、任意の高橋くんを$x$として、クエリの組$(i, x)$をまとめて前計算する。
前計算1回あたり、イベント全走査して$x$を全通りキャッシュするので、時間計算量$O(N+M)$、空間計算量$O(N)$かかる。
$i$のあり得る個数は$O(\frac{M}{C})$ (イベント個数$M$から閾値$C$が何個取れるか)により、
キャッシュ計算全体で時間計算量$O(\frac{(N+M)M}{C})$
空間計算量$O(\frac{NM}{C})$
$C=O(\sqrt{\frac{NM}{Q}})$
とすることで、
全体$O(\sqrt{NMQ}+M\sqrt{\frac{MQ}{N}})$で解ける。
提出コード
https://atcoder.jp/contests/abc365/submissions/56695169
可能ならクエリの答えをすべて予め計算してキャッシュしたいが時間が掛かりすぎるため、
何個キャッシュを持っておくべきか?
→$\sqrt{N}$くらいキャッシュする
キャッシュで持ちきれない分は都度愚直計算する。
都度愚直計算する負担が少ないものはどういう性質がある?
→$S$が小さいもの
クエリ全部を都度愚直計算で答えるとする。
愚直で答え切れるクエリ1回あたりの限界は?
→$S$が$\sqrt{M}$くらい
範囲外のものは予め計算しておいてキャッシュから答える。
合計が$M$のとき、$Q$個の相異なるペアについて小さい方の和は$O(M\sqrt{Q})$で抑えられる。
クエリ1つ捌くところで計算量を「ペアの小さい方log(ペアの大きい方)」になるように書けば間に合うイメージ。
$O(M√Q)$で抑えられる抑えられる理由のイメージは、
ペア$(A, B)$について、$A$も$B$も$M$への寄与分が同じときが一番きつい。
ペアに登場する要素の種類数が$x$のとき、その全組み合わせは${}_xC_2=O(x^2)$なので
要素の種類数を$\sqrt{Q}$個にして、$M$を$\sqrt{Q}$に均等に割り振るのが最悪ケース。
このとき要素一つあたり$O(\frac{M}{\sqrt{Q}})$、
クエリ$Q$個飛んでくるので$O(\frac{M}{\sqrt{Q}}*Q)=O(M\sqrt{Q})$。
クエリ1つ捌くところで計算量を「ペアの小さい方log(ペアの大きい方)」にするパートは
ABC305D-Sleep Logと同じ。
クエリは相異なるペアである必要があるので、同じクエリが来たときようにキャッシュが必要な点に注意。
提出コード
https://atcoder.jp/contests/abc365/submissions/56669241
類題
https://www.facebook.com/codingcompetitions/hacker-cup/2022/qualification-round/problems/D