Codeforces Round 881 (Div. 3) |
---|
Закончено |
Это сложная версия задачи. Единственное отличие между простой и сложной версией состоит в том, что в этой версии $$$u$$$ может принимать любые возможные значения.
Как известно, Омск — столица Берляндии. Как и в любой столице, в Омске есть хорошо развитая система метрополитена. Метрополитен Омска представляет из себя некоторое количество станций, соединённых туннелями, причём между любыми двумя станциями есть ровно один путь, проходящий по каждому из туннелей не более одного раза. Иными словами, метрополитен представляет собой дерево.
Для развития метрополитена и привлечения жителей в Омске используется следующая система. Каждая станция имеет свой вес $$$x \in \{-1, 1\}$$$. Если станция имеет вес $$$-1$$$, то при посещении станции с жителя Омска взимается плата в $$$1$$$ бурль. Если же вес станции равен $$$1$$$, то житель Омска вознаграждается $$$1$$$-м бурлем.
Пока что есть только одна станция с номером $$$1$$$ и весом $$$x = 1$$$. Каждый день происходит одно из следующих событий:
Вы являетесь другом Лёши, поэтому Ваша задача — ответить на вопросы Лёши.
$$$\dagger$$$Подотрезок — непрерывная последовательность элементов.
В первой строке находится число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора входных данных дано число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество событий.
Далее следует $$$n$$$ строк, описывающих события. В $$$i$$$-й строке возможен один из вариантов:
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого вопроса Лёши выведите «Yes» (без кавычек), если описанный в условии подотрезок существует, иначе выведите «No» (без кавычек).
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
18+ 1 -1? 1 1 2? 1 2 1+ 1 1? 1 3 -1? 1 1 1? 1 3 2? 1 1 0
NO YES NO YES YES YES
17+ 1 -1+ 2 -1+ 2 1+ 3 -1? 5 2 2? 3 1 -1? 5 4 -3
NO YES YES
Пояснение к первому примеру.
Ответ на второй вопрос «Yes», так как существует путь $$$1$$$.
В четвертом вопросе мы можем снова выбрать путь $$$1$$$.
В пятом запросе ответ «Yes», так как есть путь $$$1-3$$$.
В шестом запросе мы можем выбрать пустой путь, так как сумма весов на нем равна $$$0$$$.
Нетрудно показать, что нет путей, удовлетворяющих первому и третьему запросу.
Название |
---|