P8473 [Aya Round 1 H] Broken History

Gensokyo has met its destruction, and the carrier of fantasy has already faded into fantasy. Fortunately, the residents of Gensokyo have survived by chance, and they are trying to restore Gensokyo’s history. However, there are countless big and small events in history, and people can only remember some major events. Perhaps, based on those important events, the minor events can be deduced?

On the positive half-axis of the number line, there are $n$ distinct special integer points colored black or white, with positions from left to right being $p_1,p_2,\cdots,p_n$. Maintain a **multiset** of segments $S$, initially empty. There are $q$ operations. There are several types of operations, in the following formats: - `1 l r`: Add to $S$ all segments $[x,y]$ such that $l \le x \le y \le r$ and both endpoints are special integer points. - `2 x`: Revoke the segments added by the $x$-th operation. Initially and after each operation, assume you may perform any number (possibly zero) of coloring actions. Each time, choose a segment $[x,y]$ from $S$ such that the special integer points at $x$ and $y$ are both black, then color all white special integer points inside this segment to black. Determine whether there exists at least one valid coloring method that makes all special integer points on the positive half-axis black (i.e., no white special integer points remain). **Note: all queries are “hypothetical”, meaning different queries are independent and will not cause any actual modification to the number line.**

- The first line contains two integers $n,q$. - The second line contains $n$ integers $p_1,p_2,\cdots,p_n$, representing the positions of the $n$ special integer points from left to right. - The third line contains $n$ integers $a_1,a_2,\cdots,a_n$, representing the colors of the special integer points. Here $a_i=0$ means white, and $a_i=1$ means black. - The next $q$ lines each contain two or three integers, describing one operation.

- Output a total of $(q+1)$ lines. - Initially and after each operation, output one line with one string: - `yes` means there exists a valid coloring method. - `no` means there does not exist a valid coloring method. - You may output the strings in any letter case. For example, `yes`, `Yes`, and `YES` are all accepted as indicating that a valid coloring method exists.

### Sample Explanation The positions/colors of the six special points on the positive half-axis are shown in the figure.  It is easy to see that not all points are black. Therefore, before any operation, output $\verb!NO!$. After the first operation, three segments are added to $S$ in total: $[5,5],[8,8],[5,8]$ (segments with overlapping endpoints are omitted in the figure). It is easy to see that no action can be performed at this time, so it is impossible to make all points black. Output $\verb!NO!$.  After the second operation, another $20$ segments are added into $S$. After removing segments with overlapping endpoints, $S$ is shown in the figure. (To distinguish them, the edges added in the previous operation are marked in dark blue.)  One can find a plan to turn all special points in the figure black. Specifically, first choose the segment $[1,5]$ in $S$ (it is easy to see that the special points at $1$ and $5$ are both black, so coloring is allowed), then the points at $2$ and $3$ can be colored.  Now you can choose the segment $[3,13]$ in $S$ (in the previous step, point $3$ became black, so $[3,13]$ satisfies the condition) and color point $8$ black.  Now all points are black, so output $\verb!YES!$. Again, the queries are independent of each other, and this only asks whether a coloring plan exists; it will not actually color the special integer points.  The third operation revokes all segments added into $S$ by the second operation. Therefore, it returns to the state where only the first operation exists. There is no plan that can color all points black, so output $\verb!NO!$. ### Constraints For all testdata, $1 \le n,q \le 5 \times 10^5$, $a_i \in \{0,1\}$, $1 \le l< r \le 10^9$, $1 \le p_i \le 10^9$. It is guaranteed that $p_i$ is strictly increasing, operation type $2$ only revokes operation type $1$, and each operation is revoked at most once. Translated by ChatGPT 5