페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4145

Farmer John Solves 3SUM 2초 512MB

문제

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 s_1,\dots,s_m of integers, count the number of unordered triples of distinct indices i,j,k such that s_i + s_j + s_k = 0.

To test Farmer John's claim, Bessie has provided an array A of N integers (1 \leq N \leq 5000). Bessie also asks Q queries (1 \leq Q \leq 10^5), each of which consists of two indices 1 \leq a_i \leq b_i \leq N. For each query, Farmer John must solve the 3SUM problem on the subarray 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!

SCORING:

  • Test cases 2-4 satisfy N\le 500.

  • Test cases 5-7 satisfy N\le 2000.

  • Test cases 8-15 satisfy no additional constraints.

Problem credits: Dhruv Rohatgi


입력

The first line contains two space-separated integers N and Q. The second line contains the space-separated elements A_1,\dots,A_N of array A. Each of the subsequent Q lines contains two space-separated integers a_i and b_i, representing a query.

It is guaranteed that -10^6 \leq A_i \leq 10^6 for every array element A_i.


출력

The output should consist of Q lines, with each line i containing a single integer---the answer to the i-th query. Note that you should use 64-bit integers to avoid overflow.


예제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).


출처

USACO 2020 January Gold

역링크 공식 문제집만