Farmer John Solves 3SUM

题目描述:

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

为了测试 Farmer John 的断言，Bessie 提供了一个 N 个整数组成的数组 A（1≤N≤5000）。Bessie 还会进行 Q 次询问（1≤Q≤105），每个询问由两个索引 1≤ai≤bi≤N 组成。对于每个询问，Farmer John 必须在子数组 A[ai…bi] 上求解 3SUM 问题。

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

测试点性质：

• 测试点 2-4 满足 N≤500。
• 测试点 5-7 满足 N≤2000。
• 测试点 8-15 没有额外限制。

输入格式:

输入的第一行包含两个空格分隔的整数 N 和 Q。第二行包含空格分隔的数组 A 的元素 A1,…,AN。以下 Q 行每行包含两个空格分隔的整数 ai 和 bi，表示一个询问。

保证对于每个数组元素 Ai 有 −10⁶≤Ai≤10⁶。

输出格式:

输出包含 Q 行，第 i 行包含一个整数，为第 i 个询问的结果。注意你需要使用 64 位整数型来避免溢出。

样例输入:

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

样例输出:

2
1
4

提示:

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

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2020 JAN Gold