Есеп D. Массив және сұраныстар

Абай сізге аңызсыз қарапайым есеп әкелді. $N$ натурал саннан тұратын $A$ массиві бар. Оған қоса, $L, R$ түріндегі $Q$ сұраныстары берілген. Сұранысқа жауап — бұл $A_L$, $A_{L+1}$, ..., $A_R$ тізбегінін ішінде, $X$, $2X$, $4X$, ..., $2^K \cdot X$ сандарының бәрі кездесетіндей, $X$ натурал саны табылса, $K$ ($K \ge 0$) санының ең үлкен мәні. Ескерту: натурал сан деп нөлден үлкен бүтін сандарды айтамыз. Бірінші жолда екі $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$) сандарымен сипатталған. Әрбір сұраныс үшін $l$-ден $r$-ге дейін, барлық ішжиымдардың $f(a[x...y])^T$ қосындын санау керек. Мұндағы $a[x...y]$ бұл бастапқы жиымның $x$-тан $y$-ға дейінгі бөлімі, яғни [$a_{x}, a_{x+1}, ..., a_y$], ($l <= x <= y <= r$) жиымы. Ұзындығы $k$ болатын $b$ жиымы үшін $f(b)$ функциясы, ол $b$ жиымының префикс-максимумымдарын құрайтын, ұзындығы $k$ болатын $c$ жиымын тауып, содан кейін $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

Бірінші мысалда, кестені әдемі етіп толтыру мүмкін емес. Екінші мысалда, кестені екі жолмен толтыруға болады: