【3.30】

这道题是判断存在性。判断可以找是否存在实例，或者不存在实例。

本题是判断不存在实例（正难则反）。

知识点：最大最小博弈搜索

两个人对一个对象 $x$ 进行操作，并定义一个权值函数 $f(x)$ 。假设先手想让 $f(x)$ 最大，后手想让 $f(x)$ 最小。那么他们会怎么操作？

自树（图）的底向上思考，对每个节点定义 low ( u ) = min ⁡ { low ( v ) } , high ( u ) = max ⁡ { high ( v ) } \text{low}(u)=\min\{\text{low}(v)\}, \text{high}(u) = \max\{\text{high}(v)\} low(u)=min{low(v)},high(u)=max{high(v)} 。在先手操作的那一层，先手会选择后继节点中 $f(x)$ 最大的那个方向移动，后手则相反。那么操作过程就是 $\text{low}\to \text{high}\to \text{low}\cdots$ 。 那么最终答案为 $ans=\text{high}(root)$ 。

最大最小博弈搜索代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68498422

$O(1)$ 正解证明见：https://blog.nowcoder.net/n/b5cbb112c2c84fa59abc3067ea1778d8

这三行代码最重要，要仔细思考：

	sum += cnt / id[c].size();cnt %= id[c].size();p = id[c][cnt];

AC代码：https://atcoder.jp/contests/abc346/submissions/51751785

这题比较巧妙的思路是把所有的区间 $(L,R),1\le L\le R\le n$ 作为二维点映射到了二维坐标系上。对于一个区间 $(L,R)$ ，需要判断是否存在数字使得其在区间内。存在性可以作并集，映射到矩阵的话就是扫描线求矩阵并集的大小。

需要注意的是，通常的扫描线的坐标是坐标系上的坐标，而非该题中的网格坐标。需要将矩阵的网格坐标 $(xL,yL),(xR,yR)$ 映射为 $(xL,yL),(xR+1,yR+1)$ 即可。

AC代码：https://atcoder.jp/contests/abc346/submissions/51752235