Задача №114770. Странная сумма
Сегодня Лёша решил сесть за подготовку к экзамену по физике. План на сегодня — выучить последовательность \(a\) из \(n\) целочисленных физических констант. К сожалению, поскольку в физике Лёша совсем ничего не понимает, он постоянно отвлекается на какие-то странные занятия. Например, он фиксирует некоторый подотрезок последовательности \(a_l, a_{l+1}, \ldots, a_r\), и считает для него странную сумму следующим образом:
- Лёша перебирает все пары \(x, y\), такие что \(l \le x \le y \le r\).
- Для каждой пары \(x, y\) Лёша добавляет в странную сумму расстояние Хэмминга между отрезками последовательности \(a_x, a_{x+1}, \ldots, a_y\) и \(a_l, a_{l+1}, \ldots a_{l+(y-x)}\).
Расстоянием Хэмминга между последовательностями \(p_1, p_2, \ldots, p_k\) и \(q_1, q_2, \ldots, q_k\) называется число индексов \(i\), таких что \(p_i \ne q_i\).
Ваша задача — помочь Лёше поскорее посчитать странные суммы для всех интересующих его отрезков \([l, r]\), чтобы он поскорее вернулся к учёбе.
В первой строке даны два числа \(n\) и \(q\) (\(1 \leq n, q \leq 2 \cdot 10 ^ 5\)) — длина последовательности и количество отрезков, для которых нужно посчитать странную сумму.
В следующей строке записаны числа \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^6\)) — имеющуюся у Лёши последовательность.
После этого следует \(q\) строк запросов, в каждой строке находятся числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le n\)), означающие, что для отрезка с \(l_i\)-го по \(r_i\)-й символ включительно Лёше нужно посчитать странную сумму.
В \(i\)-й строке выведите число, равное странной сумме на отрезке из запроса под номером \(i\).
Рассмотрим последний запрос в первом примере. В нём последовательность Лёши равна \([1, 2, 1, 3]\), а также выбран подотрезок с \(1\) до \(4\).
Обозначим за \(h\) расстояние Хэмминга. Тогда ответом является сумма следующих величин:
- \(h([1, 2, 1, 3], [1, 2, 1, 3]) = 0\)
- \(h([1, 2, 1], [1, 2, 1]) = 0\)
- \(h([2, 1, 3], [1, 2, 1]) = 3\)
- \(h([1, 2], [1, 2]) = 0\)
- \(h([2, 1], [1, 2]) = 2\)
- \(h([1, 3], [1, 2]) = 1\)
- \(h([1], [1]) = 0\)
- \(h([2], [1]) = 1\)
- \(h([1], [1]) = 0\)
- \(h([3], [1]) = 1\)
Итоговая сумма равна \(8\).
Тесты к этой задаче состоят из семи групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Дополнительные ограничения | |||||
| Группа | Баллы | \(n, q\) | \(a_i\) | Необх. группы | Комментарий |
| 0 | 0 | Тесты из условия. | |||
| 1 | 10 | \(n, q \leq 100\) | – | 0 | |
| 2 | 15 | \(n, q \leq 1000\) | – | 0, 1 | |
| 3 | 15 | \(n, q \leq 10\,000\) | – | 0, 1, 2 | |
| 4 | 15 | \(n, q \leq 100\,000\) | \(a_i \leq 2\) | – | |
| 5 | 15 | \(n, q \leq 100\,000\) | \(a_i \leq 50\) | 0, 4 | |
| 6 | 15 | \(n, q \leq 100\,000\) | – | 0–5 | |
| 7 | 15 | – | – | 0–6 | |
4 4 1 2 1 3 1 1 2 3 2 4 1 4
0 1 4 8
7 5 2 1 5 6 6 2 3 1 4 4 7 4 4 1 3 3 5
10 7 0 4 3