Intersection Floor Sum

解説

$S_i$ と $S_j$ の共通部分に点 $(x,y)$ が存在するための条件は、

$$(j-i)x\le A_i+A_j,\qquad (j-i)x\ge -(A_i+A_j)$$

である。よって、 $S_i$ と $S_j$ の共通部分に含まれる点の $x$ 座標の最大値は

$$f(i, j) = \dfrac{A_i+A_j}{j-i}$$

である。したがって、求める答えは

$$\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}{\left\lfloor{\dfrac{A_i+A_j}{j-i}}\right\rfloor}$$

となる。

各組 $(i, j)$ について、

$${\left\lfloor{\dfrac{A_i+A_j}{j-i}}\right\rfloor}$$

は、 $k(j-i) \le A_i+A_j$ を満たす正整数 $k$ の個数に等しい。

主客転倒より、各整数 $k$について、 $k(j-i) \le A_i+A_j$ を満たす組 $(i, j)$ の個数を求め、それらを合計すればよい。

適当な正整数 $B$ を定め、 $k$ を $k \le B$ と $k \gt B$ に分けて考える。

• $k \le B$

  $k(j-i) \le A_i+A_j$ が成り立つことと、区間 $[ki-A_i, ki+A_i], [kj-A_j, kj+A_j]$ が共通部分を持つことは同値である。したがって、各 $i$ に対する区間の両端の値をソートし、共通部分を持つ区間の組の個数を数えれば良い。

  計算量は $O(BN\log{N})$ である。

• $k \gt B$

  このとき、$k(j-i) \le A_i+A_j$ を満たす $k \gt B$ が存在するならば、 $(B+1)(j-i) \le A_i+A_j \le 2N$ が成り立つ。よって、 $j-i \le \dfrac{2N}{B+1}$ を満たす $i, j$ について考えれば良い。

  $i, j$ に対して条件を満たす $k \gt B$ の個数は $\max\left(0,\left\lfloor\frac{A_i+A_j}{j-i}\right\rfloor-B\right)$ であるので、これらを足せば良い。

  計算量は $O\left(\dfrac{N^2}{B}\right)$ である。

以上より、計算量は $O\left(BN\log{N} + \dfrac{N^2}{B}\right)$ となる。

$B = \Theta\left(\sqrt{\dfrac{N}{\log{N}}}\right)$ とすることで、 $O(N\sqrt{N\log{N}})$ でこの問題を解くことができる。