Google Code Jam 2019 Round 1B C. Fair Fight

問題

N種類の異なる武器が2つずつ並べてある。
あなたは審判で、まず(L,R)の範囲を指定する。
対戦者のCharlesとDelilaは、その範囲内の武器の一つを選んで対戦を行う。
また、それぞれ人の武器の熟練度がCiおよびDiで与えられ、それぞれ範囲内で一番熟練度が高い武器を使って戦うことがわかっている。

審判として、フェアな戦いとなるようにしたいので、選んだ武器の熟練度の差が高々Kとなるような(L,R)の選び方をしたい。そのような範囲の選び方はいくつあるか？

制約

• 1 <= T <= 100
• 0 <= K <= 10^5
• 0 <= Ci, Di <= 10^5
• 制限時間は30秒以内
• 8ケースがN = 10^5、それ以外は1 <= N <= 1000

解法

あるiが必ず含まれるような範囲を考える。
このとき、範囲はざっくりと以下のような形になっている。

[条件を満たさないLの範囲][条件を満たすLの範囲][条件を満たさないL,Rの範囲(iを含む)][条件を満たすRの範囲][条件を満たさないRの範囲]

各範囲は、0個かもしれないことに注意。

このとき、iを必ず含むような範囲の個数は「(条件を満たすLの範囲)の個数 * (条件を満たすRの範囲)の個数」で求められる。

すべてのiについて求めることを考えると、上記の範囲をO(logN)程度以下で求めたい。
そこで、二分探索で上記のそれぞれの範囲の境界を見つけることを考える。

LとRはそれぞれ同等の方法で求められるので、Rについて考える。
次のように3つの条件に分けて考える。
(1) max(Ci, ..., Cj) <= Ciを満たす範囲
(2) max(Di, ..., Dj) <= Ci+Kを満たす範囲
(3) max(Di, ..., Dj) < Ci-Kを満たす範囲

iからjの累積和をsum(0,j)-sum(0,i-1)で求める様な感じで、「(2)かつ(1)の範囲」から「(3)かつ(1)の範囲」を引くことで、上記の「条件を満たすRの範囲」の個数を求めたいが、それぞれのmax値はセグメント木などでO(logN)で求められるので、十分高速に求められる。

また、Ciが同じ値の場合などで重複してカウントしてしまう可能性があるので、(1)で範囲を求めるときに、すでに計算を行った領域を使わないようにしたい。
これは、Ciが大きい順からiを処理していき、Ciが同じ場合は、iが小さい順から処理して、Lの(1)の計算時に前のところを含まないようにしてあげればよい。