eolymp
bolt
Try our new interface for solving problems
Məsələlər

Фермер Джон решает 3SUM

Фермер Джон решает 3SUM

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 512 MiB

Фермер Джон верит, что он сделал великое открытие в проектировании алгортимов: он открыл почти линейный алгоритм для известной проблемы 3SUM, про которую никто не знает решение, работающее быстрее, чем за квадратичное время. Одна из формулировок проблемы 3SUM такова: задан массив целых чисел s[1],..., s[m], требуется посчитать количество таких неупорядоченных троек с различными индексами i, j, k, что s[i] + s[j] + s[k] = 0.

Чтобы проверить алгоритм ФД, Бесси подготовила массив A из n целых чисел. Бесси совершит q запросов задав пару индексов a[i], b[i] (1a[i]b[i]n). Для каждого такого запроса ФД должен решить задачу 3SUM на подмассиве A[a[i] ... b[i]].

ФД просит Вас пройти тест Бесси.

Giriş verilənləri

Первая строка содержит два целых числа n (1n5000) и q (1q10^5). Вторая строка содержит элементы A[1], ..., A[n] массива A. Каждая из следующих q строк содержит два натуральных числа a[i] и b[i], представляющих запрос.

Гарантируется, что −10^6A[i]10^6 для каждого элемента массива A[i].

Çıxış verilənləri

Выведите q строк. Cтрока i содержит одно целое число - ответ на i-ый запрос.

Пример

Для первого вопроса возможны тройки (A[1], A[2], A[5]) и (A[2], A[3], A[4]).

Nümunə

Giriş verilənləri #1
7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7
Çıxış verilənləri #1
2
1
4
Mənbə 2020 USACO Январь, Золото