2022 9.6 模拟

这次模拟用了大概一个半点做三道题。

$T1$ 是白送的，就不说了

看 $T2$ 的时候，一开始觉得好像很简单，但想了离散化之后排序搞，但不对。于是卡了能有很长时间吧，去看了 $T3$.

$T3$ 是在 $YbtOJ$ 上面做过的原题。用 $tarjan$ 缩点之后建一个新图，然后根据题意进行更新答案即可。但是交上去之后发现 $TLE$ 了一个点，很神奇，把数组开小之后，竟然 $TLE$ 的点变多了。考完之后去 $luogu$ 上测，发现两份代码都能跑过，就很玄学。

然后回去看 $T2$。教练在群里说了一句，别把题想的太难。我把之前的思路都给放弃了重新看。看到数据范围，正解大概是 $O(n\log n)$ 的做法，而且给的 $l$ 和 $r$ 的范围显然不能建线段树这种东西。

重新想，发现这道题的区间虽然有包含，但是静态的。而且要求第 $k$ 小值，如果在一个数组中，很容易就会想到二分。本题也一样，可以进行二分。每次二分一个 $x$，看 $n$ 个区间所有 $\le x$ 的值有多少，跟 $k$ 比较，这样最后就能二分出答案了。

总结：$T2$ 确实不难，但自己想了很长时间，对于一些基础算法的掌握不扎实，对于模型的建立不够好。以后在做题的时候，要多思考，与之前学过的算法比较，建立解题思路。

最后，一句经典的话非常适合这次考试：$Stop$ $learning$ $useless$ $algorithms$ $,$ $learn$ $now$ $to$ $use$ $binary$ $search!$