Задача D. Массив и запросы

Абай принес вам простую задачу без легенды. Задан массив $A$, состоящий из $N$ натуральных чисел, а также $Q$ запросов вида $L, R$. Ответом на запрос является максимальное целое $K$ ($K \ge 0$), что для него найдется натуральное $X$, при котором числа $X$, $2X$, $4X$, ..., $2^K \cdot X$ встречаются среди чисел $A_L$, $A_{L+1}$, ..., $A_R$. Ваша задача -- посчитать ответ на каждый запрос. Примечание: натуральным называется целое число больше нуля. В первой строке выходных данных заданы два натуральных числа $N$ и $Q$ ($1 <= N, Q <= 5 \cdot 10^5$). Во второй строке задается массив $A$ ($1 <= A_i <= 10^{18}$). Начиная с третьей строки, задаются запросы $L$, $R$ ($1 <= L <= R <= N$). Каждый запрос задан в отдельной строке. Выведите $Q$ строк, в $i$-й строке должен быть ответ на $i$-й запрос. Вход

6 3
6 9 12 24 18 9
2 3
4 6
1 5

Ответ

0
1
2

Пояснение к примеру: В во втором запросе можно выбрать 18 и 9, тогда $K = 1, X = 9$. В третьем запросе -- 6, 12 и 24 ($K = 2, X = 6$).

Задача E. Сложная сумма

Дан массив из $n$ чисел, а также $m$ запросов. Каждый запрос содержит два числа $l$ и $r$ ($1 <= l <= r <= n$). Необходимо для каждого запроса вычислить сумму всех подмассивов $f(a[x...y])^T$ от $l$ до $r$, где $a[x...y]$ - это часть исходного массива, начинающаяся с $x$ и заканчивающаяся $y$ ($l <= x <= y <= r$), то есть массив [$a_{x}, a_{x+1}, ..., a_y$]. Для массива $b$ длины $k$, функция $f(b)$ находит массив $c$ длины $k$, который представляет собой префикс-максимумы массива $b$, а затем считает количество уникальных чисел в массиве $c$. Более формально, пусть $c_i$ = max($b_1, b_2, ..., b_i$). Тогда $f(b)$ равна количеству уникальных чисел в массиве $c$. Например, для массива $b = [3, 1, 4, 1, 5, 9, 2, 6, 5]$, мы получаем массив префикс-максимумов $c = [3, 3, 4, 4, 5, 9, 9, 9, 9]$. Затем мы считаем количество уникальных чисел в $c$, которое равно $4$ ($3, 4, 5$ и $9$). Ваша задача - написать программу, которая будет для каждого запроса будет находить сумму всех его подмассивов. Так как ответ может быть очень большим, выведите его по модулю $10^9 + 7$. В первой строке заданы три целых числа $n$, $m$ и $T$($1 <= n,m <= 5 \cdot 10^5, 1 <= T <= 2$). Во второй строке заданы $n$ целых чисел $a_1, a_2, ..., a_n$($1 <= a_i <= n$). В следующих $m$ строках заданы по два целых числа $l_i$ и $r_i$ ($1 <= l_i <= r_i <= n$). Выведите $m$ целых числа — ответ на каждый запрос по модулю $10^9 + 7$. Вход

5 6 2
1 3 2 1 4
1 5
2 4
3 5
1 3
2 3
4 5

Ответ

41
6
12
12
3
6

Вход

6 5 1
4 3 2 5 4 6
1 4
2 5
3 6
4 6
1 6

Ответ

13
14
16
8
35

Рассмотрим $4$-й запрос первого примера: $l_4 = 1, r_4 = 3$. Получается нам нужно посчитать сумму $f(a[1...1])^2 + f(a[1...2])^2 + f(a[1...3])^2 + f(a[2...2])^2 + f(a[2...3])^2 + f(a[3...3])^2 = 1 + 2^2 + 2^2 + 1 + 1 + 1 = 12$. $f(a[1..3]) = f([a_1, a_2, a_3]) = f(1, 3, 2) = 2$, так как массив префиксных максимумов будет выглядит как $[1, 3, 3]$ и в ней два различных числа.

Задача F. Заполнение таблицы

Таблица размера $2 \times n$ называется красивой если числа в ней возрастают как по строкам, так и по столбцам, более того, все числа в таблице должны образовывать перестановку чисел от $1$ до $2 \cdot n$. Вам дана таблица в которой некоторые клетки заняты, а некоторые свободны. Вы уже умеете заполнять таблицу так, чтобы она стала красивой, и эта задача вам кажется скучной. Поэтому вы хотите узнать сколько есть способов заполнить таблицу таким образом, чтобы она была красивой. Так как ответ может быть очень большим, выведите его по модулю $10^9 + 7$. В первой строке дано одно натуральное число $n$ ($1 <= n <= 2 \cdot 10^5$) — количество столбцов в таблице. Далее следуют $2$ строки, в этих двух строках вам дана сама таблица. Числа в таблице имеют значения от $0$ до $2 \cdot n$, при этом числа от $1$ до $2 \cdot n$ встречаются не более одного раза. Если значение элемента равно $0$, то это клетка считается пустой. Выведите одно число — ответ на задачу по модулю $10^9 + 7$. Вход

3
5 0 6
4 0 0

Ответ

0

Вход

3
0 2 0
3 0 0

Ответ

2

В первом примере нет ни единого способа заполнить таблицу так чтобы она была красивой. Во втором примере есть две красивые таблицы которые могут получиться: