T1
医生厨
神秘贪心题。不会。不懂。
考虑当 \(\max A_i \le x\) 时，可以直接从大往小干。否则需要不断扩大 \(x\) 使得其超过 \(\max A\)。我们考虑在一个时刻，若存在一个 \(a\) 使得 \(a \le x \land 2a \ge x\)，那我们直接把这个 \(a\) 干掉是不劣的，因为你现在干掉这个至多只会拖延一步，但是省下了之后再来干掉这个的一步，因此是不劣的。如果不存在这样的 \(a\) 就每次把 \(x\) 翻倍，会发现这是一定可行的。
T2
数据结构
我们肯定是希望求出一个子树内每个点填的优先级，求出这个就好做了。注意到一个子树内的优先级的相对关系并不会随着这个子树的根上面挂了多少东西而改变，因此可以直接在根处算出每个点的优先级。只需要从根开始先递归子树内编号最小的点，然后继续做即可。过程中需要线段树维护区间最小值及其位置。求出优先级之后就相当于每次把一个点的优先级置为 \(+\infty\) 表示这个点放过了，或者把一个点的优先级恢复表示这个点被拿走了。也是线段树维护。求出一个点最上面的有猫猫的祖先可以直接树上倍增。总复杂度单 \(\log\)。
T3
平面
二分答案，曼哈顿转切比雪夫，只需要判断一堆正的矩形能否完全覆盖一个斜的矩形区域。扫描线维护，注意转换后的坐标系上只有横纵坐标奇偶性相同的点会在原坐标系上存在，因此要对横坐标的奇偶性开两棵线段树维护。或者同一个线段树上维护奇偶位置的最小值也行。然后由于坐标系有 \(1e8\)，只能选取若干特殊的横坐标检查是否覆盖。只需要在每次增删矩形的位置、斜过来的矩形的四个角的位置检查即可，因为这些位置是最容易挂掉的。
T4
无穷图的桥
不会。
标签：优先级,子树内,20241116,线段,一个点,维护,矩形 From： https://www.cnblogs.com/forgotmyhandle/p/18550440