まず注意点として、同じ (Ai,Bi) クエリは複数回投げられうる。
同じクエリは再計算されないように、事前にまとめるなどする必要がある。
まず率直に思いつく方法として、イベント順に解くことを考えると、
を用意して、Ti 順に入退室を見ていき、
としていくと、答えとなる。
問題は、「入退室が多く、ペアも多い人」がいると、O(NM) かかってしまう。
(例えば、ほぼ人 i の入退室で M 個の記録が占められ、クエリでも他の N−1 人全てとの答えが求められる場合など)
そういう人は、別処理をする。
入退室の多い1人を p とする。
記録 i から i+1 までの時間を、「時区間 i」とする。
各時区間の長さ Di=Ti+1−Ti を求めておく。
長さ M−1 の数列 X を用意し、時区間 i に人 p が入室しているなら Xi=Di、退室中は Xi=0 とする。
記録 i 0 1 2 3 4 5 6 7 T 3 9 15 17 20 25 26 30 D 6 6 2 3 5 1 4 pの入退室 in out in out X 6 6 0 0 5 1 0
こうしておけば、
人 p の入退室回数を Rp、クエリで p とペアとなる人の数を Pp とする。
イベント順の解法では、p の入退室によって発生する計算量が 「入退室回数 Rp× ペア数 Pp」かかっていたのに比べ、 1人を基準にする解法は最初に X を作る際の「入退室記録数 M」の計算量で済む。
相手 j の入退室によって発生する、p の状態確認 (イベント順なら LastEnter のチェック、1人を基準にする解法なら X の累積和の取得) の計算量は Rj に依存し、こちらはどちらの解法も変わらない。
よって、「Rp×Pp が M を超える場合」に、 イベント順から p を基準に解く解法に変えるのが良い、はず。
(以下、駄文)
なお、クエリ (p,j) の両方とも R∘×P∘ が大きい場合、
基準とする方をどちらか一方に決めなければいけない。
(どちらでもACできるだろうので別に突き詰める必要は無いのだが)どちらを基準とした方がよいか?
「入退室回数 R∘ が多い」方を基準にした方が、(p,j) ペアだけ考えたときの削減効果は大きいが、
基準にされなかった方は、実質的に P∘(※)が1減り、評価値 R∘×P∘ が変動する。
(※イベント順の解法を取ったときに、入退室のたびにチェックする相手数)
評価値 R∘×P∘ が減ることで、結局イベント順の解法にした方がいい、となるかもしれない。
その場合、評価値の削減効果が大きいのも「入退室回数 R∘ が多い」方である。
この最適化って、どうしたらいいんだろうね。