Задача №114973. Грибные пары
Недавно столичный Центр Помощи Мигрантам открыл свою школу. Школа эта очень странная — занятия идут не по 45 минут, ученики пропускают уроки, а ведет их учитель по прозвищу ГРИБ. В один момент это надоело всем (кроме учеников, конечно же), из-за чего учитель решил проучить всех прогульщиков.
ГРИБ дал ученикам следующую задачу: Дан массив \(a\), состоящий из \(n\) целых чисел. К этому массиву приходят \(m\) запросов, состоящих из двух чисел \(x_i\) и \(y_i\). Для каждого запроса требуется максимизировать произведение числа вхождений \(x_i\) до некоторой позиции на количество вхождений \(y_i\) начиная с этой позиции. Более формально, можно ввести следующие три функции:
- \(lcnt(j, x)\) — количество вхождений числа \(x\) на префиксе массива \(a\) до позиции \(j\) включительно.
- \(rcnt(j, x)\) — количество вхождений числа \(x\) на суффиксе массива \(a\) начиная с позиции \(j\) включительно.
- \(f(i, x, y) = lcnt(i - 1, x) \cdot rcnt(i, y)\)
Для каждого запроса необходимо по всем \(j\) от \(2\) до \(n\) найти максимум \(f(j, x_i, y_i)\). Так как ученики пропустили все занятия, они не могут решить задачу ГРИБ'а. Помогите ученикам школы Центра Помощи Мигрантам решить эту задачу и избежать отчисления из школы.
В первой строке даны два целых числа \(n\) и \(m\) \((2 \le n \le 100\,000, 1 \le m \le 100\,000\)) — количество чисел в массиве и число запросов.
Во второй строке даны \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\) — числа в массиве.
В следующих \(m\) строках описаны запросы. В каждой из них даны два целых числа \(x_i\) и \(y_i\) \((1 \le x_i, y_i \le 10^9)\) — значения из \(i\)-го запроса. Гарантируется, что числа \(x_i\) и \(y_i\) присутствуют в массиве.
В \(m\) строках выведите ответы на запросы, по одному в строке.
Рассмотрим первый пример.
Первый запрос — 1 2:
- \(f(2, 1, 2) = 2\)
- \(f(3, 1, 2) = 1\)
- \(f(4, 1, 2) = 1\)
- \(f(5, 1, 2) = 0\)
Таким образом, ответ на первый запрос равен \(2\).
Второй запрос — 2 2:
- \(f(2, 2, 2) = 0\)
- \(f(3, 2, 2) = 1\)
- \(f(4, 2, 2) = 1\)
- \(f(5, 2, 2) = 0\)
Таким образом, ответ на второй запрос равен \(1\).
Третий запрос совпадает с первым, и ответ на него равен \(2\).
Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | \(a_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 14 | \(n \le 100\) | \(m \le 100\) | – | 0 | |
| 2 | 19 | \(n \le 5000\) | \(m \le 5000\) | – | 0, 1 | |
| 3 | 22 | – | – | \(a_i \le 1000\) | – | |
| 4 | 12 | – | – | – | – | \(x_i = y_i\) во всех запросах |
| 5 | 33 | – | – | – | 0 – 4 | Offline-проверка |
5 3 1 2 3 2 1 1 2 2 2 1 2
2 1 2
5 4 1 1 1 2 2 1 1 1 2 2 2 2 1
2 6 1 0