P6006 [USACO20JAN] Farmer John Solves 3SUM G

Farmer John believes he has made a major breakthrough in algorithm design: he claims to have found a near-linear-time algorithm for the 3SUM problem, a famous algorithmic problem for which no solution significantly faster than quadratic time has been found so far. One version of the 3SUM problem is: given an integer array $s_1,\ldots,s_m$, compute the number of unordered triples of distinct indices $i,j,k$ such that $s_i+s_j+s_k=0$ ($i$, $j$, and $k$ are all different). To test Farmer John’s claim, Bessie provides an array $A$ of $N$ integers ($1 \leq N \leq 5000$). Bessie will also ask $Q$ queries ($1 \leq Q \leq 10^5$), where each query 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 \ldots b_i]$. Unfortunately, Farmer John has just discovered a bug in his algorithm. He is confident he can fix it, but in the meantime, he asks you to help him pass Bessie’s tests first.

The first line contains two space-separated integers $N$ and $Q$. The second line contains the elements of $A$, namely $A_1,\ldots,A_N$, separated by spaces. Each of the next $Q$ lines contains two space-separated integers $a_i$ and $b_i$, describing a query. It is guaranteed that for each array element $A_i$, we have $-10^6 \leq A_i \leq 10^6$.

Output $Q$ lines. The $i$-th line contains one integer, the answer to the $i$-th query. **Note that you need to use a 64-bit integer type to avoid overflow.**

### Sample Explanation For the first query, all valid triples are $(A_1,A_2,A_5)$ and $(A_2,A_3,A_4)$. ### Subtasks - Test cases $2 \sim 4$ satisfy $N \leq 500$. - Test cases $5 \sim 7$ satisfy $N \leq 2000$. - Test cases $8 \sim 15$ have no additional constraints. Translated by ChatGPT 5