G. Запутывание следов

Codeforces

IDCF10220G

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Поиски книг о космическом анализе привлекли много внимания, и двое патрульных попытались задержать Рика и Мирлина Теренса. К счастью, на помощь к ним пришла Валлона, и, оглушив нейрохлыстом патрульных, наши герои сбежали обратно в Нижний город. Незамедлительно за ними был выслан целый отряд патрульных, но в Нижнем городе нашелся человек, котрый был готов спрятать беглецов от патрульных. Транторианский агент Матт Хоров укрыл Рика и Валлону в своей пекарне, а Теренс тем временем отправился домой — отсутствие резидента в течение дня могли заметить, а привлекать лишнее внимание Теренс не хотел. На следующее утро Матт решил отправить Рика и Валлону с Флорины, где им угрожала опасность, на какую-нибудь другую планету. Хоров выдал им поддельные паспорта и билеты на корабль до Вотекса, но оставалась нерешенная проблема — огромное количество патрульных в Верхнем городе. Но Матт Хоров мог использовать других агентов, чтобы доставить Рика и Валлону в космопорт. Чтобы не привлекать излишнего внимания, Матт решил, что поднимутся они не у самого космопорта, а в каком-либо из $8$ кварталов Верхнего города, затем проедут по некоторым из этих кварталов, вероятно, не по одному разу, а затем из последнего посещенного квартала отправятся прямо в космопорт. Сопровождать Рика и Валлону будут некоторые из $n$ агентов Хорова. Для каждого агента известно, из каких кварталов в какие он может перемещаться. Путешествие проходит следующим образом: Рик с Валлоной поднимаются в одном из кварталов, где их встречает первый агент. За один доступный ему переезд он добирается до некоторого следующего квартала, где его ждет второй агент, который везет их до следующего квартала, и так далее до последнего квартала перед космопортом. Чтобы сбежать от возможной погони, Матт хочет рассмотреть разные маршруты. Он уже придумал $m$ планов, каждый состоит из стартового квартала $s_i$, конечного квартала $t_i$, а также чисел $l_i$ и $r_i$ — Рика и Валлону будут сопровождать агенты с $l_i$-го по $r_i$-го включительно, в порядке следования их номеров. Таким образом, в квартале $s_i$ их встречает $l_i$ агент и перемещается с ними в некоторый следующий квартал, где их поджидает $l_{i + 1}$ агент, который помогает им переместиться в другой квартал, и так далее. Наконец $r_i$ агент должен доставить Рика и Валлону в квартал $t_i$. При этом Матт выбирал агентов обдуманно, по этому никакой из отрезков $[ l_i \; r_i ]$ не вложен в другой. Формально, не существует таких $i$ и $j$, таких что $l_i < l_j <= r_j < r_i$. Для каждого из планов Матт хочет узнать число различных путей, которыми данные агенты могут доставить из стартового квартала в конечный, по модулю $998244353$. Пути считаются различными, если существует номер $l <= k <= r$, такой что после поездки с $k$-м агентом по этим путям Рик с Валлоной добрались бы до разных кварталов. Обратите внимание, что для запутывания следов они могут посещать один квартал несколько раз, в том числе подряд. В первой строке содержатся целые числа $n$ и $m$ — число агентов и число запросов соответственно $(1 <= n <= 10^5, 1 <= m <= 2 dot.op 10^5)$. В следующих $n$ строках заданы целые числа от $0$ до $2^(64) -1$, задающие бинарные матрицы $8 times 8$ перемещения агентов. Матрица получается следующим образом: число записывается в двоичной системе счисления, дополняется ведущими нулями до 64 знаков, после чего его цифры слева направо записываются как элементы матрицы. Заполнение идет по строкам слева направо, начиная с верхней и заканчивая нижней. В полученной матрице элемент $i$-й строки $j$-го столбца $a_{i j} = 1$, если и только если соответствующий агент может проехать от $i$-го квартала до $j$-го. Далее идут $m$ строк, по четыре числа в каждой: $l_i, r_i$ - номера первого и последнего агентов, затем $s_i, t_i$ - номера стартового и конечного кварталов $(1 <= l_i <= r_i <= n \; 1 <= s_i, t_i <= 8)$. Выведите $m$ строк, в $i$-й строке — ответ на $i$-й запрос по модулю $998244353$. Переведем данные числа в двоичную систему счисления, дополнив ведущими нулями при необходимости. Получим следующий результат: $9241386504218214000_{10} = 1000000001000000000000000001000000001000000001000000001000000001_2,$ $4692768438333080000_{10} = 0100000100100000000100000000100000000100000000100000000110000000_2$, $4620710844295152000_{10} = 0100000000100000000100000000100000000100000000100000000110000000_2$. Теперь составим из полученных чисел матрицы $8 times 8$: В первом запросе необходимо попасть из третьего квартала в четвертый, используя помощь первого и второго агентов. Но первый агент не может переместиться никуда из третьего квартала. Таким образом осуществить побег не удастся. Во втором запросе нужно попасть из первого квартала в третий, используя помощь первого, второго и третьего агентов. Возможный маршрут лишь один: $1 arrow.r 2 arrow.r 3$. В третьем запросе требуется попасть из первого квартала во второй с помощью третьего агента. Это можно сделать ровно одним способом. ## Входные Данные В первой строке содержатся целые числа $n$ и $m$ — число агентов и число запросов соответственно $(1 <= n <= 10^5, 1 <= m <= 2 dot.op 10^5)$.В следующих $n$ строках заданы целые числа от $0$ до $2^(64) -1$, задающие бинарные матрицы $8 times 8$ перемещения агентов. Матрица получается следующим образом: число записывается в двоичной системе счисления, дополняется ведущими нулями до 64 знаков, после чего его цифры слева направо записываются как элементы матрицы. Заполнение идет по строкам слева направо, начиная с верхней и заканчивая нижней. В полученной матрице элемент $i$-й строки $j$-го столбца $a_{i j} = 1$, если и только если соответствующий агент может проехать от $i$-го квартала до $j$-го.Далее идут $m$ строк, по четыре числа в каждой: $l_i, r_i$ - номера первого и последнего агентов, затем $s_i, t_i$ - номера стартового и конечного кварталов $(1 <= l_i <= r_i <= n \; 1 <= s_i, t_i <= 8)$. ## Выходные Данные Выведите $m$ строк, в $i$-й строке — ответ на $i$-й запрос по модулю $998244353$. ## Пример Входные данные3 3 9241386504218214000 4692768438333080000 4620710844295152000 1 2 3 4 1 3 1 3 3 3 1 2 Выходные данные0 1 1 ## Примечание Переведем данные числа в двоичную систему счисления, дополнив ведущими нулями при необходимости. Получим следующий результат: $9241386504218214000_(10) = 1000000001000000000000000001000000001000000001000000001000000001_2,$$4692768438333080000_(10) = 0100000100100000000100000000100000000100000000100000000110000000_2$,$4620710844295152000_(10) = 0100000000100000000100000000100000000100000000100000000110000000_2$.Теперь составим из полученных чисел матрицы $8 times 8$: $mat(delim: "(", 1, 0, 0, 0, 0, 0, 0, 0; 0, 1, 0, 0, 0, 0, 0, 0; 0, 0, 0, 0, 0, 0, 0, 0; 0, 0, 0, 1, 0, 0, 0, 0; 0, 0, 0, 0, 1, 0, 0, 0; 0, 0, 0, 0, 0, 1, 0, 0; 0, 0, 0, 0, 0, 0, 1, 0; 0, 0, 0, 0, 0, 0, 0, 1)$ $mat(delim: "(", 0, 1, 0, 0, 0, 0, 0, 1; 0, 0, 1, 0, 0, 0, 0, 0; 0, 0, 0, 1, 0, 0, 0, 0; 0, 0, 0, 0, 1, 0, 0, 0; 0, 0, 0, 0, 0, 1, 0, 0; 0, 0, 0, 0, 0, 0, 1, 0; 0, 0, 0, 0, 0, 0, 0, 1; 1, 0, 0, 0, 0, 0, 0, 0)$ $mat(delim: "(", 0, 1, 0, 0, 0, 0, 0, 0; 0, 0, 1, 0, 0, 0, 0, 0; 0, 0, 0, 1, 0, 0, 0, 0; 0, 0, 0, 0, 1, 0, 0, 0; 0, 0, 0, 0, 0, 1, 0, 0; 0, 0, 0, 0, 0, 0, 1, 0; 0, 0, 0, 0, 0, 0, 0, 1; 1, 0, 0, 0, 0, 0, 0, 0)$ В первом запросе необходимо попасть из третьего квартала в четвертый, используя помощь первого и второго агентов. Но первый агент не может переместиться никуда из третьего квартала. Таким образом осуществить побег не удастся.Во втором запросе нужно попасть из первого квартала в третий, используя помощь первого, второго и третьего агентов. Возможный маршрут лишь один: $1 arrow.r 2 arrow.r 3$.В третьем запросе требуется попасть из первого квартала во второй с помощью третьего агента. Это можно сделать ровно одним способом. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $, $ A = (A_1, A_2, \dots, A_N) $ be a permutation of $ \{1, 2, \dots, N\} $. For each index $ i \in \{1, \dots, N\} $, let $ \mathrm{LIS}_i $ denote the length of the longest increasing subsequence (LIS) of $ A $ that includes $ A_i $. Let $ \mathrm{LIS}^* = \max_{i} \mathrm{LIS}_i $ denote the length of the global LIS of $ A $. **Constraints** $ 1 \leq N \leq 250000 $, and all $ A_i $ are distinct integers in $ [1, N] $. **Objective** For each $ i \in \{1, \dots, N\} $, compute: $$ f(i) = \left| \left\{ j \in \{1, \dots, N\} \setminus \{i\} \mid \mathrm{LIS}_i^{(j)} < \mathrm{LIS}_i \right\} \right| $$ where $ \mathrm{LIS}_i^{(j)} $ is the length of the longest increasing subsequence of the sequence $ A $ with element $ A_j $ removed, that still includes $ A_i $.

API Response (JSON)

{
  "problem": {
    "name": "G. Запутывание следов",
    "description": {
      "content": "Поиски книг о космическом анализе привлекли много внимания, и двое патрульных попытались задержать Рика и Мирлина Теренса. К счастью, на помощь к ним пришла Валлона, и, оглушив нейрохлыстом патрульных",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10220G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Поиски книг о космическом анализе привлекли много внимания, и двое патрульных попытались задержать Рика и Мирлина Теренса. К счастью, на помощь к ним пришла Валлона, и, оглушив нейрохлыстом патрульных...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $, $ A = (A_1, A_2, \\dots, A_N) $ be a permutation of $ \\{1, 2, \\dots, N\\} $.  \nFor each index $ i \\in \\{1, \\dots, N\\} $, let $ \\mathrm{LIS}_i $ denote the l...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments