Задача №114703. Тир
Мальчик Витя любит играть с огнестрельным оружием. Это увлечение и привело его в ближайший тир.
Если посмотреть на тир сверху, то он имеет форму прямоугольник размера \(n \times m\), где в центре каждого единичного отрезка на верхней стороне прямоугольника, имеющей длину \(m\), находится пистолет, а в центре каждого единичного отрезка на нижней стороне находится мишень. Каждый раз, когда Витя покупает жетон, он получает \(m\) пуль и стреляет из каждого пистолета ровно по одному разу. Витя — отличный стрелок, поэтому пуля после выстрела летит строго перпендикулярно верхней стороне. Поскольку между пистолетом и мишенью нет препятствий, пуля всегда попадает в мишень.
Вите надоело каждый раз попадать во все \(m\) мишеней, поэтому он решил усложнить задачу. Для этого он планирует поставить перегородки в некоторые клетки. Перегородки располагаются под углом \(45^{\circ}\) и соединяют один из углов клетки с противоположным. Когда летящая пуля ударяется об перегородку, она отражается в соответствии с законами физики, то есть поворачивает на \(90^{\circ}\) влево или вправо в зависимости от расположения перегородки. Пуля продолжает лететь до тех пор, пока не попадёт в мишень или не вылетит за пределы тира.
После выставления перегородок пули, выпущенные из некоторых пистолетов, могут не долетать до мишеней, поэтому Вите интересно, во сколько мишеней он попадёт хотя бы единожды.
Чтобы усложнить вам задачу, Витя будет добавлять и удалять перегородки и после каждого изменения спрашивать, во сколько мишеней он попадёт хотя бы один раз, если выстрелит сейчас из каждого пистолета.
Изначально в тире нет ни одной перегородки.
В первой строке заданы три числа \(n\), \(m\), \(q\) (\(1 \le n, m, q \le 200\,000\)) — высота тира, ширина тира и число запросов, соответственно.
В следующих \(q\) строках описываются изменения.
Каждое изменение задано тройкой чисел \(a_i\) \(x_i\) и \(y_i\) (\(0 \le a_i \le 2\), \(1 \le x_i \le n\), \(1 \le y_i \le m\)).
- Если \(a_i = 0\), то в \(i\)-м запросе требуется удалить перегородку, находящуюся в \(x_i\)-й строке и \(y_i\)-м столбце. Гарантируется, что на момент \(i\)-го запроса она там есть.
- Если \(a_i = 1\), то в \(i\)-м запросе требуется добавить перегородку из левого верхнего в правый нижний угол клетки, находящейся на пересечении \(x_i\)-й строки и \(y_i\)-го столбца. Гарантируется, что на момент \(i\)-го запроса там нет перегородки.
- Если \(a_i = 2\), то в \(i\)-м запросе требуется добавить перегородку из левого нижнего в правый верхний угол клетки, находящейся на пересечении \(x_i\)-й строки и \(y_i\)-го столбца. Гарантируется, что на момент \(i\)-го запроса там нет перегородки.
Строки пронумерованы от 1 до \(n\) сверху вниз, столбцы пронумерованы от 1 до \(m\) слева направо.
Выведите \(q\) чисел, \(i\)-е из них должно быть равно числу мишеней, в которые попадёт Витя после \(i\)-го изменения.
Тесты к этой задаче состоят из восьми групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\), \(m\), \(q\) | \(a_i\) | Необх. группы | Комментарий |
| 0 | 0 | - | – | – | Тесты из условия. |
| 1 | 9 | \(n, m, q \le 500\) | \(a_i \le 1\) | ||
| 2 | 11 | \(n, m, q \le 500\) | – | 0, 1 | |
| 3 | 11 | \(n, m, q \le 10\,000\) | \(a_i \le 1\) | 1 | |
| 4 | 12 | \(n, m, q \le 10\,000\) | – | 0–3 | |
| 5 | 13 | \(n, m, q \le 60\,000\) | \(a_i \le 1\) | 1, 3 | |
| 6 | 15 | \(n, m, q \le 60\,000\) | – | 0–5 | |
| 7 | 13 | – | \(a_i \le 1\) | 1, 3, 5 | Offline-проверка. |
| 8 | 16 | – | – | 0–7 | Offline-проверка. |
5 5 7 1 1 1 1 1 5 1 5 5 1 5 3 0 5 5 1 4 1 0 1 1
4 4 3 3 3 3 2
3 5 9 2 1 2 1 1 5 2 3 5 1 3 2 1 3 1 0 3 2 2 3 2 1 1 4 2 3 3
4 3 3 3 3 3 3 3 3
5 5 11 1 5 1 2 5 5 1 1 5 2 1 2 2 5 2 0 5 2 1 3 2 2 1 1 0 1 2 1 1 3 2 5 3
4 3 3 3 3 3 2 2 2 2 2