Farmer John Solves 3SUM

题目描述

Farmer John 认为他在算法设计上取得了重大突破：他声称自己找到了一个用于 3SUM 问题的近线性时间算法。3SUM 是一个著名的算法问题，因为目前已知的任何解法都无法在显著优于二次时间内运行。

3SUM 问题的一种表述如下：给定一个由整数构成的数组 $s_1,\dots,s_m$，统计满足 $s_i + s_j + s_k = 0$ 的、由两两不同的下标 $i,j,k$ 组成的无序三元组的数量。

为了检验 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$ 的 $N$ 个元素 $A_1,\dots,A_N$，以空格分隔。接下来的 $Q$ 行中，每行包含两个用空格分隔的整数 $a_i$ 和 $b_i$，表示一个询问。

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

输出格式

输出应包含 $Q$ 行，第 $i$ 行输出一个整数——第 $i$ 个询问的答案。

注意你应使用 64 位整数以避免溢出。

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

2
1
4

提示

评分： 测试点 2-4 满足 $N\le 500.$ 测试点 5-7 满足 $N\le 2000.$ 测试点 8-15 没有额外限制。

对于第一个询问，可能的三元组是 $(A_1,A_2,A_5)$ 和 $(A_2,A_3,A_4).$

题目致谢：Dhruv Rohatgi

标签: USACO|2020|Gold

来源

USACO|2020|Gold