感觉能做的题目变多了，大概会做的题的比率跟 年差不多。

对比之下， 年还是较为阴间的。

D1T1 建筑装饰 4

题意：https://loj.ac/p/3271

不好评价，对着 的 DP 看了约一天，花了大部分的下课时间，没有发现可行转移点是个区间的性质，真是可惜。

以上是本篇题解，相信读者可以完成其余的部分。

D1T2 汉堡肉

题意： https://loj.ac/p/3272

之前听杂题的时候听过，要不然应该是没啥想法的。

首先考虑，如果是 维情况，将右端点排序之后贪心即可。

考虑什么时候 维会退化为 维，这当且仅当某一维上所有矩形的投影的交非空。

此时我们在这一维上全选交集，另一维就是一维问题。

如果没有这种情况的话，我们考虑这四条分界线： 。

那么有 。

对于最优解来说，答案里一定有 个点（可重合）满足 。

也就是说，考虑直线 和直线 围成的矩形，那么答案一定在这个矩形的边界上。

首先考虑如果有点在这个矩形的角上，我们可以枚举其在矩形的哪个角上，然后把与这个点有交的矩形删掉，再去找到新的 ，确定别的点。这就是个搜索的过程，时间复杂度 。

在 时跑这个搜索就做完了。在 时也可以先跑这个搜索。

如果搜索找不到答案，那么 个点一定在矩形的四条边上。考虑一个点在某个位置时，其对另一个点的位置（准确的说是其对面的点的位置）有一个范围的限制，即其一定要在某个前缀或某个后缀中。使用 2-SAT 刻画问题，容易在大常数 的时间复杂度中解决。

代码咕了，感觉好难写。

D1T3 扫除

题意： https://loj.ac/p/3273

离正解就差一个线段树分治。不知道是不是因为这题的思考时间都是零散的，导致最后一步没想出来。

首先考虑 Sub 3，即满足 。感受一下就是一串蜿蜒向右下的点，容易证明在进行一次操作之后，这些点仍然满足这个性质。那么我们做每次操作时，二分出会受到影响的点的区间，进行一个区间赋值即可。这个操作可以使用线段树完成。

然后考虑 Sub 4，即没有中途插入点的情况。直觉告诉我们这个点跟 Sub3 关系紧密。事实上，如果有两个点 满足 ，那么如果一次操作扫到了点 ，那么 肯定也会被扫到， 就会满足 了。由此可以得出结论，对于那些被扫过一次的节点，它们互相之间是满足 Sub 3 的性质的。

那么我们对没被扫到过和被扫到过的节点分别维护即可。我们需要找到每个节第一次被扫到的时间，这个可以用一棵普通线段树比较方便地处理。对于那些被扫到过的节点，因为我们要往其中插入元素，故把原来的线段树改成平衡树即可。

考虑正解。此时 Sub 4 中推出的性质不一定满足，因为点的插入有了时间差别，但如果我们进行一个线段树分治，把点的存在时间拆为 个线段树节点，然后对于每个线段树节点来说，问题就和 Sub 4 没有区别了。

时间复杂度 。

虽然不知道为啥 出 然后放 。

代码：https://loj.ac/s/1780245