{"problem":{"name":"[Aya Round 1 H] 破碎的历史","description":{"content":"数轴的正半轴上有 $n$ 个互不相同的被黑白染色的特殊整点，位置从左到右依次为 $p_1,p_2,\\cdots,p_n$。维护初始为空的**可重**线段集合 $S$。 $q$ 次操作。操作分若干种，具体格式如下： - `1 l r`：将所有满足 $l \\le x \\le y \\le r$ 且两端点均为特殊整点的线段 $[x,y]$ 加入 $S$。 - `2 x`：撤回第 $x$ 次操作添加的线","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8473"},"statements":[{"statement_type":"Markdown","content":"数轴的正半轴上有 $n$ 个互不相同的被黑白染色的特殊整点，位置从左到右依次为 $p_1,p_2,\\cdots,p_n$。维护初始为空的**可重**线段集合 $S$。\n\n$q$ 次操作。操作分若干种，具体格式如下：\n\n- `1 l r`：将所有满足 $l \\le x \\le y \\le r$ 且两端点均为特殊整点的线段 $[x,y]$ 加入 $S$。\n- `2 x`：撤回第 $x$ 次操作添加的线段。\n\n在初始时和每次操作后，假设你可以进行任意次（可以是零次）染色。每次从 $S$ 中选出一条线段 $[x,y]$，满足位于点 $x$ 和点 $y$ 的特殊整点均为黑色，然后将所有在线段内的白色特殊整点染黑。试判断是否存在至少一种合法染色方式使得正半轴上的所有特殊整点均被染黑（即，不存在白色特殊整点）。**注意：所有的询问均为「假设」，即各组询问之间独立，不会造成对数轴的实际修改。**\n\n## Input\n\n- 第一行输入两个整数 $n,q$。\n- 第二行输入 $n$ 个整数 $p_1,p_2,\\cdots,p_n$，表示 $n$ 个特殊整点从左到右的位置。\n- 第三行输入 $n$ 个整数 $a_1,a_2,\\cdots,a_n$，表示特殊整点的颜色。其中 $a_i=0$ 表示白色，$a_i=1$ 表示黑色。\n- 接下来 $q$ 行，每行二至三个整数，表示一次操作。\n\n## Output\n\n- 输出共 $(q+1)$ 行。\n- 在初始时和每次操作后，输出一行一个字符串：\n  - `yes` 代表存在合法染色方式。\n  - `no` 代表不存在合法染色方式。\n- 你可以输出字符串的任意大小写形式。例如：字符串 `yes`、`Yes`、`YES` 均会被视为表示存在合法染色方式。\n\n[samples]\n\n## Background\n\n幻想乡迎来了它的毁灭，幻想的载体也已经遁入了幻想。\n\n所幸的是，幻想乡中的乡民们还侥幸存活着，她们在尝试恢复幻想乡的历史。然而历史之中的大大小小的事情不计其数，人们只能记得起一些大事情罢了。\n\n或许，根据那些重要的事情，可以把次要的事件推导出来呢？\n\n## Note\n\n### 样例解释\n\n六个特殊点的位置/颜色在数轴正半轴上如图所示。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/i1hfjrk8.png)\n\n容易发现，并非所有点都是黑点。因此在进行操作前，输出 $\\verb!NO!$。\n\n第一次操作后，一共往 $S$ 加入了三条线段：$[5,5],[8,8],[5,8]$（图中省略了端点重叠的线段）。容易发现，此时无法进行任何操作，因此没法将所有点变成黑点。输出 $\\verb!NO!$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ayeijyli.png)\n\n第二次操作后，又往 $S$ 中加入了 $20$ 条线段。除去端点重叠的选段，在 $S$ 中如图所示。（以示区别，上一次操作加入的边标成了深蓝色）。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/icw9ar9m.png)\n\n可以找出一种方案，将图上所有特殊点变成黑点。具体而言，首先选择 $S$ 中 $[1,5]$ 线段（容易发现位于 $1$ 和 $5$ 的特殊点均为黑点，因此可以进行染色），那么可以把位于 $2$ 和 $3$ 的点染色。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/3k1uvul0.png)\n\n此时又可以选择 $S$ 中 $[3,13]$ 线段（在上一轮操作中，$3$ 号点变为了黑点，因此 $[3,13]$ 符合条件），将点 $8$ 染为黑色。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/7ebafj63.png)\n\n此时所有点都为黑色，因此输出 $\\verb!YES!$。再次强调，询问之间互相独立，且只是询问是否存在染色方案，而不会对特殊整点进行实际上的染色操作。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/pjqpqvtr.png)\n\n第三个操作撤回了第二个操作往 $S$ 里加入的所有线段。因此退回到了只有第一个操作的情况。不存在一种方案将所有点染黑，因此输出 $\\verb!NO!$。\n\n### 数据范围\n\n对于所有数据，$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$。保证 $p_i$ 单调递增，$2$ 操作撤销的只会是 $1$ 操作，且每个操作最多被撤销一次。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8473","tags":["线段树","二分","洛谷原创","Special Judge","O2优化","洛谷月赛"],"sample_group":[["6 3\n1 2 3 5 8 13\n1 0 0 1 0 1\n1 5 10\n1 1 15\n2 2\n","No\nNo\nYes\nNo"]],"created_at":"2026-03-03 11:09:25"}}