#PU994. USACO 2020 January Contest, Gold — Problem 2. Farmer John Solves 3SUM

    ID: 1532 传统题 文件IO:threesum 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan20来源:usaco.orgscoring:equal_test_cases双指针哈希

USACO 2020 January Contest, Gold — Problem 2. Farmer John Solves 3SUM

USACO 2020 January Contest, Gold — Problem 2. Farmer John Solves 3SUM

题目描述

Farmer John believes he has made a major breakthrough in algorithm design: he claims to have found a nearly linear time algorithm for the 3SUM problem, an algorithmic problem famous for the fact that no known solution exists running in substantially better than quadratic time. One formulation of the 3SUM problem is the following: given an array s1,…,sms_1,\dots,s_m of integers, count the number of unordered triples of distinct indices i,j,ki,j,k such that si+sj+sk=0s_i + s_j + s_k = 0. To test Farmer John's claim, Bessie has provided an array AA of NN integers (1≤N≤50001 \leq N \leq 5000). Bessie also asks QQ queries (1≤Q≤1051 \leq Q \leq 10^5), each of which consists of two indices 1≤ai≤bi≤N1 \leq a_i \leq b_i \leq N. For each query, Farmer John must solve the 3SUM problem on the subarray A[ai…bi]A[a_i \dots b_i]. Unfortunately, Farmer John has just discovered a flaw in his algorithm. He is confident that he can fix the algorithm, but in the meantime, he asks that you help him pass Bessie's test!

输入格式

The first line contains two space-separated integers NN and QQ. The second line contains the space-separated elements A1,…,ANA_1,\dots,A_N of array AA. Each of the subsequent QQ lines contains two space-separated integers aia_i and bib_i, representing a query. It is guaranteed that −106≤Ai≤106-10^6 \leq A_i \leq 10^6 for every array element AiA_i.

输出格式

The output should consist of QQ lines, with each line ii containing a single integer---the answer to the ii-th query.

数据范围

Test cases 2-4 satisfy N≤500.N\le 500. Test cases 5-7 satisfy N≤2000.N\le 2000. Test cases 8-15 satisfy no additional constraints.

样例

样例 1

7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7
2
1
4
For the first query, the possible triples are $(A_1,A_2,A_5)$ and
$(A_2,A_3,A_4).$
Problem credits: Dhruv Rohatgi

提示

integers to avoid overflow.