Codeforces Round 936 (Div. 2) |
---|
Закончено |
Олег в подарок на день рождения получил перестановку $$$a$$$ длины $$$n$$$.
Друг Олега Нечипор задает Олегу $$$q$$$ вопросов, каждый вопрос характеризуется двумя числами $$$l$$$ и $$$r$$$, в ответ на вопрос Олег должен сказать количество наборов индексов $$$(t_1, t_2, \ldots, t_k)$$$ произвольной длины $$$k \ge 1$$$ таких, что:
Помогите Олегу и ответьте на все вопросы Нечипора.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 10^6$$$) — длина перестановки и количество вопросов Нечипора.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — сама перестановка $$$a$$$.
В каждой из следующих $$$q$$$ строк каждого набора входных данных содержатся два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — очередной вопрос Нечипора.
Гарантируется, что сумма значений $$$n$$$ и сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите ответы на все вопросы Нечипора.
48 82 1 6 3 5 4 8 71 82 81 71 61 35 84 42 31 111 13 33 2 11 21 32 38 11 2 3 4 5 6 7 81 8
20 15 18 12 5 5 1 3 1 2 3 2 27
Все подходящие массивы в первом наборе входных данных: ($$$1$$$), ($$$2$$$), ($$$3$$$), ($$$4$$$), ($$$5$$$), ($$$6$$$), ($$$7$$$), ($$$8$$$), ($$$1, 3$$$), ($$$1, 6$$$), ($$$1, 7$$$), ($$$1, 6, 7$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 5$$$), ($$$2, 6$$$), ($$$2, 7$$$), ($$$2, 8$$$), ($$$2, 6, 7$$$), ($$$6, 7$$$).
Все подходящие массивы в четвертом наборе входных данных: ($$$1$$$), ($$$2$$$), ($$$3$$$), ($$$4$$$), ($$$5$$$), ($$$6$$$), ($$$7$$$), ($$$8$$$), ($$$1, 2$$$), ($$$1, 3$$$), ($$$1, 4$$$), ($$$1, 5$$$), ($$$1, 6$$$), ($$$1, 7$$$), ($$$1, 8$$$), ($$$1, 2, 4$$$), ($$$1, 2, 6$$$), ($$$1, 2, 8$$$), ($$$1, 2, 4, 8$$$), ($$$1, 3, 6$$$), ($$$1, 4, 8$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$2, 8$$$), ($$$2, 4, 8$$$), ($$$3, 6$$$), ($$$4, 8$$$).
Название |
---|