| Условие задачи | | Прогресс |
|
Темы:
Алгоритм Мо
Вам дан массив целых чисел А длиной n.
Необходимо ответить на m запросов вида "сообщите количество различных чисел подотрезка массива А от элемента с индексом l до элемента с индексом r" (обе границы подотрезка включены, массив нумеруется с единицы).
Входные данные:
В первой строке дано два числа: n - количество элементов массива и m - количество запросов (1 <= n, m <= 105).
Во второй строке дано n целых чисел Ai - элементы массива (0 <= Ai <= 106).
Далее дано m строк, в каждой по два числа l и r - границы подотрезка для каждого запроса (1 <= l <= r <= n).
Выходные данные:
В единственной строке выведите через пробел m чисел - для каждого запроса количестве различных чисел на соответствующем подотрезке.
Пример:
| Входные данные |
Выходные данные |
7 5
1 3 1 2 2 4 1
1 3
4 5
3 7
2 4
7 7 |
2 1 3 3 1 |
| |
![]()
|
|
Темы:
Алгоритм Мо
Вывод формулы
Имеется массив натуральных чисел a1, a2, ..., an. Рассмотрим некоторый его подмассив al, al + 1, ..., ar, где 1 ≤ l ≤ r ≤ n, и для каждого натурального числа s обозначим через Ks число вхождений числа s в этот подмассив. Назовем мощностью подмассива сумму произведений Ks·Ks·s по всем различным натуральным s. Так как количество различных чисел в массиве конечно, сумма содержит лишь конечное число ненулевых слагаемых.
Необходимо вычислить мощности каждого из t заданных подмассивов.
Входные данные
Первая строка содержит два целых числа n и t (1 ≤ n, t ≤ 200000) — длина массива и количество запросов соответственно.
Вторая строка содержит n натуральных чисел ai (1 ≤ ai ≤ 106) — элементы массива.
Следующие t строк содержат по два натуральных числа l и r (1 ≤ l ≤ r ≤ n) — индексы левого и правого концов соответствующего подмассива.
Выходные данные
Выведите t строк, где i-ая строка содержит единственное натуральное число — мощность подмассива i-го запроса.
Примеры:
| Входные данные |
Выходные данные |
3 2
1 2 1
1 2
1 3 |
3
6 |
8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7 |
20
20
20 |
| |
![]()
|
|
Темы:
Алгоритм Мо
Префиксные суммы(минимумы, ...)
У Эвана есть любимое число k и массив ai длины n. Теперь он просит вас ответить на m запросов.
Для каждого запроса, задаваемого парой чисел l и r, требуется найти количество пар целых чисел i и j таких, что l ≤ i ≤ j ≤ r и xor чисел ai, ai + 1, ..., aj равен k.
Входные данные:
В первой строке даны целые числа n, m и k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ 106) — длина массива, количество запросов и любимое число Эвана соответственно.
Во второй строке записаны n целых чисел ai (0 ≤ ai ≤ 106) — имеющийся у Эвана массив.
Дальше идут m строк. В i-й строке записаны числа li и ri (1 ≤ li ≤ ri ≤ n), определяющие i-й запрос.
Выходные данные:
Выведите m строк, ответы на запросы в порядке их появления во входных данных.
Примеры:
| Входные данные |
Выходные данные |
6 2 3
1 2 1 1 0 3
1 6
3 5 |
7
0 |
5 3 1
1 1 1 1 1
1 5
2 4
1 3 |
9
4
4 |
| |
![]()
|
|
Темы:
Алгоритм Мо
Дерево отрезков, RSQ, RMQ
Дана перестановка из n элементов.
Ответьте на m запросов про число инверсий для подотрезка перестановки от l до r.
Инверсией называется пара индексов i, j такая, что i < j и ai > aj, где ai - это i-й элемент перестановки.
Входные данные:
В первой строке задано число n (1 <= n <= 105).
Во второй строке задана перестановка из n элементов (элементы перестановки - попарно различные целые числа от 1 до n).
В третьей строке задано число m (1 <= m <= 105).
В последующих m строках содержится по два числа l и r - границы запроса (1 <= l, r <= n).
Выходные данные:
Выведите m строк - ответы на данные запросы.
Примеры:
| Входные данные |
Выходные данные |
5
4 5 2 3 1
3
1 3
3 5
1 5 |
2
2
8 |
6
5 2 4 3 1 6
3
4 6
2 5
1 5 |
1
4
8 |
| |
![]()
|