Farmer John believes he has made a major breakthrough in algorithm design: he
claims to have found a nearly linear time algorithm for the 3SUM problem, an
algorithmic problem famous for the fact that no known solution exists running
in substantially better than quadratic time. One
formulation of the 3SUM problem is the following: given an array \(s_1,\dots,s_m\)
of integers, count the number of unordered triples of distinct indices \(i,j,k\)
such that
\(s_i + s_j + s_k = 0\).

To test Farmer John's claim, Bessie has provided an array \(A\) of \(N\) integers
(\(1 \leq N \leq 5000\)). Bessie also asks \(Q\) queries (\(1 \leq Q \leq 10^5\)),
each of which consists of two indices \(1 \leq a_i \leq b_i \leq N\). For each
query, Farmer John must solve the 3SUM problem on the subarray
\(A[a_i \dots b_i]\).

Unfortunately, Farmer John has just discovered a flaw in his algorithm. He is
confident that he can fix the algorithm, but in the meantime, he asks that you
help him pass Bessie's test!

Problem credits: Dhruv Rohatgi

SCORING

• Test cases 2-4 satisfy \(N\le 500.\)
• Test cases 5-7 satisfy \(N\le 2000.\)
• Test cases 8-15 satisfy no additional constraints.

Problem credits: Dhruv Rohatgi

The first line contains two space-separated integers \(N\) and \(Q\). The second
line contains the space-separated elements \(A_1,\dots,A_N\) of array \(A\). Each of
the subsequent \(Q\) lines contains two space-separated integers \(a_i\) and \(b_i\),
representing a query.

It is guaranteed that \(-10^6 \leq A_i \leq 10^6\) for every array element \(A_i\).

The output should consist of \(Q\) lines, with each line \(i\) containing a single
integer---the answer to the \(i\)-th query. **Note that you should use 64-bit
integers to avoid overflow. **

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > January > Gold