[USACO20JAN] Farmer John Solves 3SUM G
题目描述
Farmer John 相信他在算法设计上实现了一个重大突破:他声称他发现了一个 3SUM 问题的近似线性时间算法,这是一个有名的算法问题,尚未发现比运行速度比平方时间明显更优的解法。3SUM 问题的一个形式是:给定一个整数数组 $s_1,\ldots,s_m$,计算不同索引组成的无序不重三元对 $i,j,k$ 的数量,使得 $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 \ldots b_i]$ 上求解 3SUM 问题。
不幸的是,Farmer John 刚刚发现了他的算法中的一个错误。他很自信他能修复这个算法,但同时,他请你帮他先通过 Bessie 的测试!
输入输出格式
输入格式
输入的第一行包含两个空格分隔的整数 $N$ 和 $Q$。
第二行包含空格分隔的数组 $A$ 的元素 $A_1,\ldots ,A_N$。
以下 $Q$ 行每行包含两个空格分隔的整数 $a_i$ 和 $b_i$,表示一个询问。
保证对于每个数组元素 $A_i$ 有 $-10^6 \leq A_i \leq 10^6$。
输出格式
输出包含 $Q$ 行,第 $i$ 行包含一个整数,为第 $i$ 个询问的结果。**注意你需要使用 64 位整数型来避免溢出。**
输入输出样例
输入样例 #1
7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7
输出样例 #1
2
1
4
说明
### 样例解释
对于第一个询问,所有的三元对为 $(A_1,A_2,A_5)$ 和 $(A_2,A_3,A_4)$。
### 子任务
- 测试点 $2 \sim 4$ 满足 $N \leq 500$。
- 测试点 $5 \sim 7$ 满足 $N \leq 2000$。
- 测试点 $8 \sim 15$ 没有额外限制。