Distinct Sum

$f(l, r) > 0$ 、すなわち $a_l, a_{l+1}, a_{l+2}, ..., a_r$ がすべて異なる時、$l \leq i \leq r$ で $f(l, i) > 0$ とわかります。

$1 \leq l \leq N$ に対して最大の $r$ を求めることを考えます。 これは尺取り法により、$O(N)$ で全ての $l$ に対して $r$ を求めることができます。

次に、$\displaystyle \sum_{l \leq i \leq r} f(l, i)$ を求めることを考えます。

式変形をすると、

$\displaystyle \sum_{l \leq i \leq r} f(l, i) = (a_l) + (a_l + a_{l+1}) + (a_l + a_{l+1} + a_{l+2}) + \cdots + (a_l + a_{l+1} + a_{l+2} + \cdots + a_r)\\ = a_l \times (r - l + 1) + a_{l+1} \times (r - l) + a_{l+2} \times (r - l - 1) + \cdots + a_r$

となります。

$\displaystyle S_0 = 0, 1 \leq i \leq N$ で $S_i = \sum_{1 \leq j \leq i} a_i\\$ $\displaystyle T_0 = 0, 1 \leq i \leq N$ で $T_i = \sum_{1 \leq j \leq i} a_i \times (N - i + 1)$

のような $S, T$ を用意しておくことで、

$\displaystyle \sum_{l \leq i \leq r} f(l, i) = T_r - T_{l-1} - (Sr - S_{l-1}) \times (n - r)$

と計算することで、$O(1)$ で求めることができます。

全体の計算量は $O(N)$ なので、十分間に合います。