P17852 「RiOI-(-2)」houran 和音游

houran 正在试着打音游。 具体地，houran 有两只手，每只手都可以以每秒一个单位的速度移动。 谱面由 $n$ 个音符组成。将判定线视为数轴，第 $i$ 个音符可以用二元组 $(x_i,t_i)$ 表示其于 $t_i$ 时刻落在 $x_i$ 上。houran 在 $0$ 时刻可以将双手放在任意位置，当他的某只手与某个音符重叠时，这个音符就可以被接住。 有 $m$ 个操作，每次修改形如 $k,x,t$，表示将第 $k$ 个音符改为 $(x,t)$。请你在所有操作前与每次操作后，输出：houran 是否能接住所有音符。

第一行两个正整数 $n,m$。 接下来 $n$ 行，每行两个非负整数，表示 $(x_i,t_i)$。 接下来 $m$ 行，每行三个非负整数 $k,x,t$，表示一次操作。

输出 $m+1$ 行，每行一个字符串 `Yes` 或 `No`，表示答案。

下发文件过大，故没有上传。 ### 【样例 $1$ 解释】 最开始时，音符序列为 $(1,1),(2,1),(3,1)$。同一时刻有三个音符落下，两只手不可能全部接住。 第一次修改后，音符序列为 $(1,1),(2,2),(3,1)$。此时可以用左手接住 $(1,1),(2,2)$，右手接住 $(3,1)$。 第二次修改后，音符序列为 $(1,1),(2,2),(3,3)$，用一只手即可全部接住。 ### 【样例 $2$】 见选手目录下的 `phigros/phigros2.in` 与 `phigros/phigros2.ans`。 该样例满足测试点 $2$ 的约束条件。 ### 【样例 $3$】 见选手目录下的 `phigros/phigros3.in` 与 `phigros/phigros3.ans`。 该样例满足测试点 $3$ 的约束条件。 ### 【样例 $4$】 见选手目录下的 `phigros/phigros4.in` 与 `phigros/phigros4.ans`。 该样例满足测试点 $4,5$ 的约束条件。 ### 【样例 $5$】 见选手目录下的 `phigros/phigros5.in` 与 `phigros/phigros5.ans`。 该样例满足测试点 $6,7$ 的约束条件。 ### 【样例 $6$】 见选手目录下的 `phigros/phigros6.in` 与 `phigros/phigros6.ans`。 该样例满足测试点 $8,9$ 的约束条件。 ### 【样例 $7$】 见选手目录下的 `phigros/phigros7.in` 与 `phigros/phigros7.ans`。 该样例满足测试点 $10\sim13$ 的约束条件。 ### 【样例 $8$】 见选手目录下的 `phigros/phigros8.in` 与 `phigros/phigros8.ans`。 该样例满足测试点 $14\sim16$ 的约束条件。 ### 【样例 $9$】 见选手目录下的 `phigros/phigros9.in` 与 `phigros/phigros9.ans`。 该样例满足测试点 $17\sim19$ 的约束条件。 ### 【样例 $10$】 见选手目录下的 `phigros/phigros10.in` 与 `phigros/phigros10.ans`。 该样例满足测试点 $20\sim22$ 的约束条件。 ### 【样例 $11$】 见选手目录下的 `phigros/phigros11.in` 与 `phigros/phigros11.ans`。 该样例满足测试点 $23\sim25$ 的约束条件。 ### 【数据范围】 对于所有测试数据，均有： - $1\le n,m\le 10^6$； - 在任意时刻，对于所有 $1\le i\le n$，均有 $1\le x_i,t_i\le10^9$。 ::cute-table{tuack} | 测试点编号 | $n,m\le$ | $x_i,t_i\le$ | 特殊性质 | |:-:|:-:|:-:|:-:| | $1$ | $5$ |$10^9$ | 无 | | $2$ | $18$ | ^ | ^ | | $3$ | $500$ | $500$ | ^ | | $4,5$ | ^ | $10^9$ | ^ | | $6,7$ | $2000$ | ^ | ^ | | $8,9$ | $10^4$ | ^ | ^ | | $10\sim13$ | $2\times 10^5$ | ^ | ^ | | $14\sim16$ | $10^6$ | ^ | $A$ | | $17\sim19$ | $5\times 10^5$ | ^ | $B$ | | $20\sim22$ | ^ | ^ | 无 | | $23\sim25$ | $10^6$ | ^ | ^ | 特殊性质 $A$：保证在操作过程中，对于所有 $1\le i\le n$，$|x_i-t_i|\le 1$。 特殊性质 $B$：保证在操作过程中，对于所有 $1\le i\le n$，不同的 $x_i$ 的数量不超过 $16$。 本题读入量巨大，我们下发了一个基于 `fread` 的快读模板。选手可以查看下发文件中的 `phigros/fastIO.cpp`，其中的 `read()` 函数可以用于读入一个非负整形变量。 ```cpp #include char buf[1 = '0' && c