Ruins He's house

好吧，昨天被这题虐惨了，照着模板敲漏了一句话，导致 1005 没有时间写了。这题可以算是一个比较经典的 Dancing Links 的题了，我们将问题抽象这如下一个模型。

我们将模型抽象化，有两种方法来解决此类问题。

第一种方法是建立一个有 $2 \times N$ 行，$3 \times N$ 列的矩阵，行代表的是选择哪些人的哪一个形态，前 $2 \times N$ 列代表的是 $N$ 个人的两种形态，后面 $N$ 列表示选择了某个人，这样我们可以这么理解，前 $2 \times N$ 列是我们必须至少覆盖一次的，后 $N$ 列是我么至多覆盖一次的，那么我们就在前 $2 \times N$ 列进行重复覆盖，后面 $N$ 列进行精确覆盖，此外，判断是否得到了一组解，只要判断前 $2 \times N$ 列是否已经被完全覆盖了即可。这个矩阵的规模是 $50 \times 75$ 的。

第二种方法是建立一个 $2 \times N$ 行 $2 \times N$ 列的矩阵，直接跑重复覆盖，此外用一个数组标记某一个人是否被选择过，如果一个人的某一形态被选择过，那么另外一个形态对应的行就不能选择，这个矩阵的规模是 $50 \times 50$ 的。

这个 blog 好久没有上来看了，看到原来写的一些文章，发现现在的代码风格完全变了个样儿，大半年没有写博文了，主要还是比较忙的原因，现在发现对于一些题目的理解，不能只局限于对某一题的做法的理解，要把相似问题转化为模型，这样我们才能在比赛中获得比较好的成绩。

这半年可以说自己的代码风格完全变了，我觉得代码要有可读性，不然的会查起来会很痛苦，和队友磨合了一两个月了，渐渐找到了那种感觉，就是这段时间的状态和队友比起来差了许多，一个主代码的居然沦落到天天比赛打酱油的地步，这是很囧的一件事儿。

这段时间要好好地调整状态了，队友八月初去北京参加百度之星的比赛，那一周队内的主要代码还是要由我来负责了，但愿这几天可以把状态找到吧，不然多校联合会打的很挫很挫。

先把数据结构和计算几何放放，把基础的东西的代码写稳了，虽然自己偏后期， 但是前期一定属于我的，这样我们队的代码基本上要由我来负责，只有我多负责一些代码的实现，两个思维型的队友才能完全发挥出他们特长。

后面有空还是会写一些总结的，不过现在没有贴代码的习惯了，多写写思路和扩展吧。

数据结构专攻告一段落吧，把这段时间和以前做过的 splay 的题目拿出来晒晒，每题都写了一下简单的解题报告，每道题的做法最好要多花时间琢磨琢磨，splay 的题目主要就是中间过程的处理上比较麻烦。为了方便，我对区间操作都是将 $l-1$ 结点 splay 到根，$r+1$ 结点 splay 到根的右子树，定义根的右子树的左子树为关键结点。

常见的 splay 问题的处理

首先是标记，下放标记和上传标记最好分开写，否则的话非常容易出问题，我们下放标记记录的是孩子结点的信息，所以我们如果要对一个结点打标记，我们要先处理好这个结点，比如说这个结点权值加上一个值，左右子树交换等等。

其次是区间操作上的方便性问题，对于平常的区间操作，如果每次询问都是删除 $[l, r]$ 区间，这样我们可以在序列左右两端加上两个哨兵，这样处理起来方便，但是有的题目这样反而不好处理，比如翻转下标小于 x 的所有数，这样左边界不能成为翻转的对象。

最后是比较重要的一点，就是如果减少时间的开销，一般我们对 splay 做 insert 操作的时候，我们要将加入到结点，或者子树的根结点 splay 到根，这样我们可以防止 splay 出现退化的情况，虽然这样还是会退化，但是均摊复杂度是可以接受的。

记录 $dp[i][j]$ 表示以第 $i$ 个元素结尾，有 $j$ 组的时候的最大和，那么有

$$dp[i][j]=\max\{dp[k][j-1]\}+sum[i-l_j+1][i]$$

其中 $k+l_j \leq i$，那么这样的转移是 $O(n)$ 的，为了优化，记录 $s[i][j]$ 表示 $s[0][j]$ 到 $s[i][j]$ 中的最大 dp 值，那么可以在 $O(1)$ 的时间内做到转移，最后可以得到一个转移方程：

$$dp[i][j]=s[i][j-1]+sum[i-l_j+1][i]。$$

注意 $sum$ 数组可以用前 $n$ 项和得到。

我的代码中用 $val$ 直接表示前 $n$ 项和。

单调队列优化的 dp。首先我们先进行预处理，将可以合并的区间合并到一起，这个可以在 $O(n \lg n)$ 的时间内完成。方法是按照 $x$ 排序，然后找相邻的两个区间 $(a, b)$ 和 $(c, d)$ 是否满足 $a < d$ 并且 $b > c$，注意这里必须严格大于才行，因为这里的区间都是开区间，如果存在 $b = c$ 这样的情况，那么 b 这个点就可以分割。

然后进行动态规划转移，令 $dp[i]$ 为前 $i$ 个区间可以划分的最小区间数目，那么就有：

$$dp[i]=\min\{dp[i-2k]\}+1,  A \leq k \leq B$$

如果不存在这样的 $k$ 值，或者 $i$ 是在某个区间内，那么 $dp[i]$ 就为 $\infty$，注意初始化 $dp[0] = 1, dp[1] = \infty$。

运用类似多重背包的方法将 $i$ 划分成 $2$ 的一个剩余类，也就是说我们可以对上式进行变形，变成如下的形式：

$$dp[mod+2j]=\min\{dp[mod+2k]\}+1, A \leq j-k \leq B$$

这里 $dp[mod+2j]$ 是个仅关于 $j$ 的函数，可以用单调队列维护一定区间的最值，最后问题得到解决。

注意这题的一些细节，首先当 $L$ 为奇数的时候 $dp[L]$ 与 $dp[1]$ 属于同一个剩余类，那么 $dp[L]$ 就为 $\infty$，所以直接可以输出 $-1$。其次，对于判断 $i$ 是否在区间内，可以用一个指针 $p$ 动态向后移动的方式来判断，如果第 $p$ 个区间的右边界小等于 $i$，那么 $p$ 就右移，知道 $p$ 等于 $n$ 或者右边界大于 $i$ 为止，这时候判断第 $p$ 个区间的左边界是否比 $i$ 小，如果左边界小于 $i$，那么 $dp[i]$ 就是 $\infty$。最后，如果 $dp[L]$ 等于 $\infty$ 记得输出 $-1$。

这里还有一个很好的技巧，在队列中加一个哨兵 $\infty$，它的 $id$ 也为 $\infty$，这样可以处理如果 $i < A$ 的情况，当然也可以直接预处理出对所有的 $i < A$ 都有 $dp[i] = \infty$，注意这里枚举和 $0$ 的同剩余类的元素要从 $2$ 开始循环！