问题 C: 三元数对

问题 C: 三元数对

时间限制: 1 Sec  内存限制: 512 MB
提交: 73  解决: 8
[提交] [状态] [讨论版] [命题人:]

题目描述

三元数对的性质如下：给定一个整数数组 a1,…,am，统计出不同索引 i,j,k组成的无序三元对的数量，使得 ai+aj+ak=0。进行 Q 次询问（1≤Q≤105），每个询问由两个整数 1≤ai≤bi≤N 组成。对于每个询问， 回答在子数组 A[ai…bi] 上符合三元对的数量。

输入

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

输出

输出包含 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)。
数据范围
测试点
满足
 1-3
 N≤500
 4-6 
N≤2000
7-14
N≤5000




[提交][状态]