3342. [USACO20 Jan Gold]Farmer John Solves 3SUM

【题目描述】

Farmer John 相信他在算法设计上实现了一个重大突破：他声称他发现了一个 3SUM 问题的近似线性时间算法，这是一个有名的算法问题，尚未发现比运行速度比平方时间明显更优的解法。3SUM 问题的一个形式是：给定一个整数数组 $s_1,\dots,s_m$，计算不同索引组成的无序三元对 $i,j,k$ 的数量，使得 $s_i + s_j + s_k = 0$。

为了测试 Farmer John 的断言，Bessie 提供了一个 $N$ 个整数组成的数组 $A$（$1 \leq N \leq 5000$）。Bessie 还会进行 $Q$ 次询问（$1 \leq Q \leq 10^5$），每个询问由两个索引 $1 \leq a_i \leq b_i \leq N$ 组成。对于每个询问，Farmer John 必须在子数组 $A[a_i \dots b_i]$ 上求解 3SUM 问题。

不幸的是，Farmer John 刚刚发现了他的算法中的一个错误。他很自信他能修复这个算法，但同时，他请你帮他先通过 Bessie 的测试！

【输入格式】

输入的第一行包含两个空格分隔的整数 $N$ 和 $Q$。

第二行包含空格分隔的数组 $A$ 的元素 $A_1,\dots,A_N$。

以下 $Q$ 行每行包含两个空格分隔的整数 $a_i$ 和 $b_i$，表示一个询问。

保证对于每个数组元素 $A_i$ 有 $-10^6 \leq A_i \leq 10^6$。

【输出格式】

输出包含 $Q$ 行，第 $i$ 行包含一个整数，为第 $i$ 个询问的结果。

【样例输入】

7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7

【样例输出】

2
1
4

【样例解释】

对于第一个询问，所有的三元对为$ (A1,A2,A5) $和$ (A2,A3,A4)$。

【提示】

对于$ 27\% $的测试数据(测试点$ 1\sim4 $)，满足$ N ≤ 500 $。

另有$ 20\% $的测试数据(测试点$ 5\sim7 $)，满足$ N ≤ 2,000 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

注意：你需要使用 64 位整数型来避免溢出。

【来源】

USACO 一月公开赛 Gold 组