Codeforces Global Round 27 |
---|
Закончено |
Это сложная версия задачи. Различия между версиями заключаются в ограничениях на $$$n$$$ и сумму $$$n$$$. В этой версии $$$n \leq 3\cdot 10^5$$$, а сумма $$$n$$$ не превосходит $$$10^6$$$. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Так-так-так, посмотрим, как Бесси распоряжается своими финансами. Похоже, она в финансовой яме! К счастью, чтобы решить эту проблему, она устраивается на работу в Moogle. Собеседования в Moogle требуют глубокого знания непонятных алгоритмов и сложных структур данных, но Бесси получила от легендарного гроссмейстера наводку на то, что именно ей нужно изучить.
Бесси написала следующий код для бинарного поиска определенного элемента $$$k$$$ в возможно несортированном массиве $$$[a_1, a_2,\ldots,a_n]$$$ с $$$n$$$ элементами.
let l = 1
let h = n
while l < h:
let m = floor((l + h) / 2)
if a[m] < k:
l = m + 1
else:
h = m
return l
Бесси отправила свой код в задачу фермера Джона с $$$m$$$ ($$$1 \leq m \leq n$$$) тестами. $$$i$$$-й тест имеет вид $$$(x_i, k_i)$$$ ($$$1 \leq x, k \leq n$$$). Гарантируется, что все $$$x_i$$$ различны и все $$$k_i$$$ различны.
Тест $$$i$$$ корректен, если выполняются следующие условия:
Возможно, не все $$$m$$$ тестов будут корректны на одном и том же массиве, поэтому фермер Джон удалит некоторые из них, чтобы Бесси могла пройти все тесты. Пусть $$$r$$$ — это минимальное количество тестов, которое нужно удалить, чтобы существовал массив $$$[a_1, a_2,\ldots,a_n]$$$, в котором $$$1 \leq a_i \leq n$$$, чтобы все оставшиеся тесты были корректными.
Помимо нахождения $$$r$$$, фермер Джон хочет, чтобы вы подсчитали количество массивов $$$[a_1, a_2,\ldots,a_n]$$$, в которых $$$1 \leq a_i \leq n$$$, таких, что существует способ удалить ровно $$$r$$$ тестов так, чтобы все оставшиеся тесты были корректными. Поскольку это число может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq m \leq n \leq 3 \cdot 10^5$$$), обозначающих длину массива и количество тестов.
Следующие $$$m$$$ строк содержат по два целых числа, описывающих тесты. В $$$i$$$-й строке содержится два целых числа $$$x_i$$$ и $$$k_i$$$ ($$$1 \leq x_i, k_i \leq n$$$), обозначающих индекс и значение данного теста. Гарантируется, что все $$$x_i$$$ различны и все $$$k_i$$$ различны.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите два целых числа: $$$r$$$ — минимальное количество удаленных тестов, чтобы существовал массив, в котором все оставшиеся тесты корректны; и количество массивов, для которых можно удалить $$$r$$$ тестов, чтобы все оставшиеся тесты были корректны, по модулю $$$998\,244\,353$$$.
25 41 12 24 35 45 45 42 51 23 3
0 1 1 3
36 61 32 53 14 25 46 630 819 226 1212 128 273 414 2529 1411 15300000 15 10
3 78 3 839271911 0 702730519
Рассмотрим первый пример.
В первом наборе входных данных массив $$$[1,2,2,3,4]$$$ удовлетворяет всем $$$m$$$ тестам, поэтому минимальное количество тестов, которые должна удалить Бесси, равно $$$0$$$. Обратите внимание, что это также единственный массив, который удовлетворяет всем $$$m$$$ тестам.
Во втором наборе входных данных минимальное количество тестов, которое Бесси должна удалить, равняется $$$1$$$. Единственный тест, который Бесси может удалить, это $$$(2,5)$$$. Если Бесси удалит тест $$$(2,5)$$$, то массивами, удовлетворяющими оставшимся $$$m-1$$$ тестам, будут $$$[2,2,3,1,4]$$$, $$$[2,2,3,2,4]$$$, $$$[2,2,3,3,4]$$$.
Название |
---|