Олимпиадный тренинг

Задача . F. Никто не нужен


Задача

Темы: 2-sat дп поиск в глубину и подобное Структуры данных *2500

Олег в подарок на день рождения получил перестановку \(a\) длины \(n\).

Друг Олега Нечипор задает Олегу \(q\) вопросов, каждый вопрос характеризуется двумя числами \(l\) и \(r\), в ответ на вопрос Олег должен сказать количество наборов индексов \((t_1, t_2, \ldots, t_k)\) произвольной длины \(k \ge 1\) таких, что:

  • \(l \le t_i \le r\) для каждого \(i\) от \(1\) до \(k\).
  • \(t_i < t_{i+1}\) для каждого \(i\) от \(1\) до \(k-1\).
  • \(a_{t_{i+1}}\) делится на \(a_{t_i}\) для каждого \(i\) от \(1\) до \(k-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\).

Выходные данные

Для каждого набора входных данных выведите ответы на все вопросы Нечипора.

Примечание

Все подходящие массивы в первом наборе входных данных: (\(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\)).


Примеры
№Входные данныеВыходные данные
1 4
8 8
2 1 6 3 5 4 8 7
1 8
2 8
1 7
1 6
1 3
5 8
4 4
2 3
1 1
1
1 1
3 3
3 2 1
1 2
1 3
2 3
8 1
1 2 3 4 5 6 7 8
1 8 
20 15 18 12 5 5 1 3
1
2 3 2
27

time 6000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет