Республиканская олимпиада по информатике. 2018 год

Задача B. Охрана природы

Ограничение по времени:

2 секунды

Ограничение по памяти:

512 мегабайт

Темирулан — активист охраны природы и защиты животных округа Каспий. Недавно во время прогулки по родному краю он обнаружил редкое растения типа ЖранУ. Растения ЖранУ являются особенными. Они растут только в тени под большими, старыми деревьями. Темирулан проверил $n$ подряд идущих деревьев, и для каждого из них узнал можно ли под ним посадить растение ЖранУ. Темирулану растение ЖранУ сильно понравилось, и он решил, что каждый год в течении следующих $q$ лет будет делать посадку этого растение. При посадке растения он выбирает некоторое количество подряд идущих деревьев от $l$ до $r$, и под каждым деревом делает посадку растение ЖранУ если можно посадить. После посадки растения их обязательно нужно полить, каждый год Темирулан поливает все растения посаженные в этот год. Для поливки растения Темирулан взял с собой ведро размера $k$, которым можно полить все растения ЖранУ которые растут под $k$ подряд идущими деревьями. Темирулан хочет полить каждое посаженное растение хотя бы один раз. Какое минимальное количество ведер воды для поливки всех новых посаженных растении? Обратите внимание, каждый год Темирулан поливает растения не учитывая предыдущий год.

Формат входного файла

Первая строка входных данных содержит два целых числа $n$ и $t$ $(1 \le n \le 2\cdot10^5, 0 \le t \le 1)$ — количество деревьев и константное число для чтения входных данных. Далее следующие $n$ чисел описывает $i$-е дерево — если $i$-е число 0, то нельзя посадить растение под $i$-м деревом, иначе можно. Деревья нумеруются с нуля. В следующей строке число $q$ $(1 \le q \le 2\cdot10^5)$ — количество посадок растений. Затем в следующих $q$ строках даны по три целых числа: $a_i$ $b_i$ $c_i$ $(0 \le a_i, b_i, c_i \le 10^9)$ Обратите внимание, что концы отрезков $[l_i, r_i]$ и число $k_i$ закодированы, и чтобы их получить нужно выполнить соответствующие преобразования: { \center $l_i = (a_i \oplus (t*lastans)) \mod n, \quad r_i = (b_i \oplus (t*lastans)) \mod n, \quad k_i = ((c_i \oplus (t*lastans)) \mod n) +1 $ \center
} где $lastans$ — последний ответ на запрос (изначально $lastans$ равен $0$). Если значение $l_i$ получилось больше значения $r_i$, то нужно поменять местами значения $l_i$ и $r_i$. Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как <<$\string^$>>, в Pascal — как <>. Операция $a \mod b$ означает взятие остатка от деления $a$ на $b$.

Формат выходного файла

Выведите $q$ строк. В $i$-й строке выведите одно число — ответ для $i$-го запроса.

Система оценки

Данная задача содержит пять подзадач, в каждой подзадаче выполняются ограничения из условий:

1. $n \le 100$, $k_i = 1$, $t = 0$. Оценивается в $7$ баллов.
2. $n \le 2000$, $q \le 2000$. Оценивается в $12$ баллов.
3. $n \le 10^5$, $q \le 10^5$, $k_i \le 10$, $t = 0$ . Оценивается в $21$ баллов.
4. $n \le 2\cdot10^5$, $q \le 2\cdot10^5$, $t = 0$ . Оценивается в $23$ баллов.
5. Ограничения из условия задачи. Оценивается в $37$ баллов.

Пример:

Вход

7 0
0 1 1 0 1 1 0
6
0 2 1
0 6 0
0 6 1
1 4 2
0 6 5
1 5 5

Ответ

1
4
2
2
1
1

( Aidos Nurmash )