[VOI Training] Bài toán 3-SUM

Xem PDF

Nộp bài


Điểm: 15 (thành phần)
Thời gian: 1.2s
Bộ nhớ: 512M

Tác giả:
Dạng bài

Bài toán 3-SUM được phát biểu đơn giản như sau: cho dãy số nguyên \(s_1\), \(s_2\),..., \(s_m\), hãy đếm số bộ ba chỉ số \(i<j<k\) sao cho \(s_i+s_j+s_k=0\).

Bạn hãy viết chương trình đọc vào mảng \(A\) gồm \(N\) số nguyên và \(Q\) truy vấn. Truy vấn thứ \(i\) cho biết hai chỉ số \(l_i\), \(r_i\) \((1\leq l_i\leq r_i\leq N)\) và bạn phải giải quyết bài toán 3-SUM trên đoạn con \(A[l_i...r_i]\).


Input

Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1\leq N\leq 5000\), \(1\leq Q\leq 10^5\)).

Dòng tiếp theo chứa \(N\) số nguyên \(A_1\), \(A_2\),..., \(A_N\) \((-10^6\leq A_i\leq 10^6)\).

Dòng thứ \(i\) trong \(Q\) dòng tiếp chứa hai số nguyên dương \(l_i\) và \(r_i\).


Output

In ra \(Q\) dòng, mỗi dòng chứa một số nguyên là câu trả lời cho câu hỏi tương ứng.


Ví dụ

Sample input
7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7
Sample output
2
1
4
Giải thích

Với truy vấn đầu tiên, hai bộ số thỏa mãn là \((A_1, A_2, A_5)\) và \((A_2, A_3, A_4)\).