2 月做题记录

0205T1 正方形

T1 来源：CF1500D IN Lv.14

这道题赛时想了一个常数极大的做法，以至于我第二个子任务都没有分。

思路是这样的：我们最暴力的方法就是容易想的，枚举矩形起点两个，再枚举矩形大小加入点两个，就是。我们发现枚举矩形起点的操作已经是没办法优化的了。那么就优化接下来的操作。

容易发现，假如你以某一个点为正方形右下角顶点，边长为，这个正方形满足要求，那么里面的边长为的就也一定满足要求，那么就相当于是只用找以某一个点为正方形右下角顶点，所可以向左上角延伸最大的正方形的边长。省去了不少时间。

但是我们如何统计颜色？这道题有一个特殊的性质：。于是我们就可以统计以点到的所有点中与切比雪夫距离最小的种颜色。记这些颜色的集合为。

切比雪夫距离：点到点的切比雪夫距离为。假设在点的右下方，且它们的切比雪夫距离为，那么以为右下角端点的，边长为的正方形刚好能碰到。

上文说到，统计切比雪夫距离最小的种颜色，就可以得出它的最大正方形边长。因为我们可以把这个第种颜色和的拎出来，那么就可以确定最大正方形边长了。若颜色个数没到，那最大正方形边长就是了。

而转移也是非常好想的：。只不过之前的集合的这些颜色的要加上。然后最后取最多个即可。

这道题就做完了。

代码（合并的时候要使用快速一点的算法）：here

0205T2 牛

T2 来源 - QOJ 9961

我的代码即题解：2K多注释+画图，长度1K变3.7K，非常牛逼

代码里没写的地方：主函数功能为二分答案 t，求得最小所花费时间。

本来是波兰语题解，QOJ 博客上有人给翻译为了中文。

Bing 搜索结果：

没有与此相关的结果: QOJ9961

检查拼写或尝试其他关键字

顺带一提，T3 的名字就叫 Bing。但我不会做，看题解吧。

T3 来源：CF1967E2

Tfs：——“你觉得你会 DP 吗？”

490DX：——“显然吧，DP 什么的不是很基础吗？”

在 2 月 4 日 490DX T1 爆零之前，Tfs 和 490DX 的对话。

P10614 Hero meet devil IN Lv.13

这道题我们首先考虑如何求两个串的最长 LCS。

显然，可用 DP 求得，设为考虑串和串时，两个串的 LCS。容易得出转化式子：

$dp_{i,j} = \left\{ \begin{aligned} &dp_{i-1, j-1} + 1 &(t_i = s_j) \\ & \max(dp_{i-1, j}, dp_{i, j-1}) &(t_i \neq s_j) \end{aligned} \right.$

但是现在只是知道了当和已知的情况。而现在不知道。

那么我们可以再套一层 DP。设为考虑串，使现在数组的维度数组（即现在的 LCS 数组）为的方案数。

根据前面推的那个式子，可以求出之前 LCS 数组状态为，现在字符串新插入一个字符时 LCS 数组会变成什么新数组。我们令其为。求的过程就是一个内层 DP。

那么就可以枚举的种情况，求出种情况下的的，然后使。这个过程就是外层 DP。而这道题涉及的算法自然就是 DP 套 DP 了。

但是正常情况下的数组的状态会比较难枚举，因为这些数的范围都最多到。但是再看那个转化式子，和的差最多也就是。所以我们可以将其转化为差分数组，这样状态数就大大减小到了，时间复杂度可以接受。

最后的就是求每一个状态的 popcount，这个值其实就是这个状态对应的 LCS 的长度。然后统计答案即可。

Double Exp：ABC391G Many LCS IN Lv.12

P4590 游园会 IN Lv.13

这道题和上一道题唯一的不同之处就是：这里不能以 NOI 作为子串。

那么我们就给数组加上一个第三维：。这里的表示现在串末尾和 NOI 的最长公共后前缀的长度。

然后加的时候就分类讨论：

int o = i&1;
for(int stat=0;stat<(1<<k);stat++){
    if(f[o][stat][0]){
        add(f[o^1][nxtst[stat][1]][1], f[o][stat][0]); // 加 N
        add(f[o^1][nxtst[stat][2]][0], f[o][stat][0]); // 加 O...
        add(f[o^1][nxtst[stat][3]][0], f[o][stat][0]);
        f[o][stat][0] = 0;
    }
    if(f[o][stat][1]){
        add(f[o^1][nxtst[stat][1]][1], f[o][stat][1]);
        add(f[o^1][nxtst[stat][2]][2], f[o][stat][1]);
        add(f[o^1][nxtst[stat][3]][0], f[o][stat][1]);
        f[o][stat][1] = 0;
    }
    if(f[o][stat][2]){
        add(f[o^1][nxtst[stat][1]][1], f[o][stat][2]);
        add(f[o^1][nxtst[stat][2]][0], f[o][stat][2]);
        // 这里不能再加 I 了！再加你就死了！
        f[o][stat][2] = 0;
    }
}

还有这道题要优化空间，就像这份代码一样用滚动数组！否则你会 Memory Limit Enough！（bushi

0206T3 征服

猜猜我为什么要写前两道 DP 套 DP，还不是因为要补题……

这道题思路和前两道题相似：首先，内层 DP，设表示考虑和的 LCS。转移式子还是那样，我们看该如何设计外层。

因为说和的最长公共子序列长度至少为，那么在考虑位置时，应该。这样的话，你才能在后面加字符并且能了。并且你还可以得到一个性质：因为非常小，并且，那么的状态就是没用的。所以状态只用枚举即可。最多也就位（而这里记录的是差分数组，最多位就可以了）。

我们设为考虑，，。注意记录的还是状压差分数组，原因前两道题讲过。然后就是老套路，枚举新加进来的字母，更新。再判断一下是否。如果是，那么的答案加上。

最后统计答案，这道题就做完了。

P6007 Springboards G IN Lv.14

一道树状数组优化 DP 简单题，我不知道它是怎么被评到 IN Lv.14 的。但是我也是脑梗，做了 2 个小时才收。

首先我们可以想到朴素 DP：设为从走到所需要的最小步数。于是可以得到转移：

$dp_{i, j} = \min_{在(i,j)左下方的点(x,y)} (dp_{x,y} + |x-i| + |y-j|)$

又因为有跳板，那么当点为跳板的结尾时：

$dp_{i,j} = \min(dp_{i,j}, dp_{from_{i,j}})$

但是因为太大，所以可以考虑离散化点。离散化完了之后可以转移。

而再看转移式：

$dp_{i, j} = \min_{在(i,j)左下方的点(x,y)} (dp_{x,y} -x-y)+i+j$

（为描述方便，我们记）

于是我们可以维护在左下方的点的的最小值。可以先给这些点按为第一关键字，为第二关键字从小到大排序。于是就能维护的单调性了。那么有的限制，还要维护最小值，这种情况就可以用树状数组解决。

最后答案就是。

0207T1 交换

原题：CF1329G Omkar and Pies IN Lv.13

这道题的非常小，似乎可以设状态来状态压缩。

首先看到连续一段区间操作，现在想知道对于每个，执行第个操作之后，会变成什么。设其为。那么可以先求出后缀，即所有的。暴力做不行，肯定要优化。

假如说我们已经求出来了依次执行操作之后变成了什么。我们用一个排列来表示。这个排列表示的是操作之后，原本的第项变为了新的第项。然后求出在操作之后变成了什么是容易的，令这个排列为。我们考虑如何把这两个排列“加起来”。

实际上因为操作是连续的，要从操作得到的变为操作得到的，只需要即可。最后把其从排列解码即可。这样就求得了所有的。

现在后缀已经求出来了。考虑如何从后缀变为区间。因为不可能从直接推出来。那么就转化一下思路。可以把变为。然后这样，就相当于是首先变为了，这段改变了和的相对位置关系。而后面改变并没有改变和的相对位置关系。所以这两个相当于是等价的。

这样，计算所有区间变化后的结果，即和的时间复杂度从变为了。

然后开始计算答案。因为最后的答案一定是某个和的最长匹配，我们可以枚举串和的公共串（但是 不一定是最长的）。具体来说，若的某位值为，在该位的值一定为。然而若的某位值为，在该位的值不一定为。串也是这样。相当于是，将看作个集合，那么。

而因为我们原来是知道的的个数，和的的个数，和现在枚举的的的个数，那么，现在的答案就是。因为是两个串的公共部分显然吧，那么还剩下个失配，还剩下个失配，删掉失配的位之后，剩下的位数就是能匹配的位数了。

这种方法虽然不保证做得到不重，但是一定能做得到不漏。

然而，直接对于和暴力枚举和的公共串的时间复杂度是的，不行，于是我们可以考虑记录两个数组：

表示可以包含的的最小。
表示可以包含的的最大。

这两个数组相当于就是枚举了包含状态所可以达到的最小左端点和最大右端点。刚好满足了题目的要求。

那么就首先设置。然后转移的从大到小转移：枚举当前的每一个被删除了的情况，为，然后。

最后枚举每一个，然后看是否。若是，则按照要求更新答案。否则不管。于是这道题就做完了。

0207T2 游戏

原题：P9731 Balance IN Lv.13

OJ7 卡死了，原题都过了 OJ7 上面交不了，神秘。

Github 上面的 11490dx.net 都上的去，OJ7 还卡死了，神秘。

首先我们可以先求的情况。直接求肯定是不好做的，我们可以考虑将其转化为图：

每一行有两个数和。我们从向连一条边（值连边），代表它们两个不交换位置，即在第一列，在第二列。然后再连边，表示它们要交换位置，即在第二列，在第一列。就相当于是每一行都对应了一条无向边。

根据题目限制，每一个点的入度和出度的差值要，发现这玩意和欧拉回路很像（欧拉回路是回路上每一个入度和出度都相等）。但是一个图存在欧拉回路的条件是这个图的所有点度数均为偶数，那么我们就可以将所有度数（无向图度数）为奇数的点向一个超级源点点连一条无向边。这样就可以求一条欧拉回路了。并且，删去我们不要的边（和相连的边），剩下的有向边所构成的图中，每一个点的入度和出度之差正好。这是因为每一个点最多只连一条连向超级源点的边。这样可以保证最多删掉条边，与它相连的点度数的自然就了。

然后根据上面的建边原则交换一些和。这就是的做法。

那么当的时候呢？注意到，所以可以考虑分治。对于一个，将其分为两半部分：左和右。我们就可以使对于每一个数，在左半部分出现的次数和右半部分出现的次数的差小于等于。那么就仿照上面连边、建图、跑欧拉路、交换，然后再把分为两个小继续分治，直到为止，返回。输出，结束。

注意因为这道题的求欧拉路的过程比较多，因此需要用当前弧优化：

inline void GetEuler(int x){
    for(int &i=h[x];i;i=edge[i].nxt){ // 优化就是这里的“&”
        if(vis[i]) continue;
        int v = edge[i].to;
        // DFS 回溯序才是欧拉路
        vis[i] = -1, vis[i^1] = 1;
        GetEuler(v);
    }
}

0208T1 Add

原题：P3544 BEZ-Minimalist Security IN Lv.14

离 T1 满分最近的一次。但是因为【数据删除】子任务捆绑和不等式情况漏讨论导致 T1 爆零。可惜了。

这道题很明显地，可以一个一个连通块的来讨论。而在一个连通块内，只要你定了一个点的值，其它点的值也会因此而确定。所以我们可以定连通块里的起始点的减少量为，然后 DFS 遍历，根据边权来定其它点的减少量或者是（这里的是一个常数）。

假设一个点知道了它的和，那么就可以直接知道的值了。确定后再 DFS 一遍检验一下就可以了。

而如果我们不知道的话，那么就再 DFS 一遍，因为每一个点有其对应的减少量范围，所以就可以列不等式或。注意情况一定要讨论全！这道题我死的地方就是这里忘记分析这种可能性，然后就 Wrong Answer 了。

然后你就会得到一个最小值和最大值。若最小值大于最大值，那么就输出 NIE。否则定一个全局答案的最小值和最大值，然后把答案加进去。最后输出即可。

0208T2 Badminton

原题：P4800 核能国度 IN Lv.14

联考题没看就直接讲原题吧。

首先，先不考虑边界问题。那么对于每一个核电站，它的泄漏范围一定是一个以其为中心点的正方形。我们可以把这个泄漏范围画出来，然后会发现一些性质：

于是我们修改矩阵的时间复杂度就从 $面积$ 变为了 $边长$ 。但是还不够，还要继续优化。

我们发现这个差分矩阵也非常特殊，斜方向的值都是相同的。于是我们可以再给这个差分矩阵做一次差分。而这个新差分矩阵就不是二维差分，而是很多个斜方向一维差分数组。类似这种（矩阵里的相同编号的表示一个一维差分数组）：

$\begin{array}{cc} 1&2&3&4&5&6\\ 2&3&4&5&6&7\\ 3&4&5&6&7&8\\ 4&5&6&7&8&9\\ 5&6&7&8&9&10\\ 6&7&8&9&10&11\\ \end{array}$

同理，还有另一个差分数组，对应 \ 方向。

现在要考虑边界问题了。我们就可以分类讨论。这里的分类讨论的过程太过繁杂，所以写了一个下午。简而言之，就是讨论每一种 / 和 \ 的端点和整个大矩形（）的四个顶点坐标大小关系。根据这个来调整这些差分数组。

而为了好解决，我们还要设两个差分数组，表示的差分和的差分。这样做的意义是：因为整个大数组的差分是通过完成的，是从前到后的，所以自然在或是的时候要特别留意。而后面的又不会影响前面的，所以给矩形的另外两条边设差分数组没有意义。

然后分类讨论，每一个 \ 的上端点有种情况，下端点只有种，每一个 / 的上端点有种情况，下端点也有种情况。所以分类讨论很麻烦。而即使很麻烦，最后也能搞到的复杂度。

而最后，根据差分数组还原到原数组之后，因为要求矩形之和，所以再给原数组求一遍前缀和，然后查询前缀和查询即可。而这道题要求求平均值，所以还要除以面积。但是不能直接的使用 double 处理，因为你这样处理会有浮点误差，四舍五入不会得到正确的结果。这里有一种方法，把余数和原数比较即可。

（图为 490DX 因最终发现浮点误差问题而红温，在黑板上写下的几个大字）

0210T1 石头

原题：P6645 Interval Collection IN Lv.13

这道题头一次联考的题面比原题的题面写得好。

并且致敬传奇联考从 statement.pdf 到 statement-new-v1.pdf 一直改到 statement-new-v6.pdf。

这次对着联考的形式化题面讲。

首先，很容易想到最后的答案一定是只进行次操作。因为如果你搞出来了第个区间，枚举所有的情况也会发现这个并不比只选个区间优。这样就简化了问题。

然后我们就分类讨论：设现在的包含所有区间的集合为（但是因为这个【数据删除】题面里面没有说是否有两个区间相等，所以这个是一个 multiset）。

若里面包含的所有区间存在交，设其为，那么就要选右端点为并且左端点最大的区间，和左端点为并且右端点最小的区间。要实现的话就对每一个点存以其为右端点的左端点的 multiset，反方向同理。
若里面包含的所有区间不存在交，那么就要选两个不交区间和并且最小。那么我们就可以用线段树实现。每一个节点存储左端点在之间的最小右端点、右端点在之间的最大左端点、和和均在之间的最小，设其为。于是可以推出来：

$\begin{aligned} minr &\gets \min(minr_{lson},minr_{rson}),\\ maxl &\gets \max(maxl_{lson},maxl_{rson}),\\ ans &\gets \min(ans_{lson}, ans_{rson}, minr_{rson}-maxl_{lson}) \end{aligned}$

然后最后 query 一下根节点的即可。

求交就记录所有的左端点和右端点，然后求左端点的最大值和右端点的最小值即可。

为什么洛谷改 UI 了！！！我的 phigros-in-luogu 插件除了在题目检索界面和提交记录界面之外的其他地方都用不了了！！！原本的 Phi 标现在就变成了一个冰冷的 AC 或者是 100 了 /ll，而且也不是一百万分制了 /ll，题目界面配上 Dark Reader 其实也没有好看到哪里去。并且里面的【IN Lv.13】就直接变回原来的了，而且题目颜色也显示不了了啊！！！

0211T1 乌龟

原题：Gym103495 B

这道题最特殊的点就在于。很容易想到状压。

可以首先把这两个龟给拆开，每一个龟跑自己的，因为，所以我们可以枚举第一个龟它杀的猪的集合，然后就可以推出来第二个龟它杀的猪的集合了。然后组合起来即可。

那么每一个龟应该跑什么呢？因为要关于每一个龟杀的猪的集合，我们可以设表示现在的龟它在点，并且它的杀猪集合为，此时这个龟所需要走的路程的最小值。

求得这个有一个方法，就是枚举，对每一个分层跑 Dijkstra。然后层之间的转移就是枚举每一条线索，设这个线索为第只猪在时刻出现在节点，并且这只猪还没被杀（即 ((stat >> (p-1)) & 1) == 0），而且你还必须要在这只猪出现或出现之前赶到现场把它宰了，不然它会跑（即 dis[stat][x] <= t），则可以转移： dp[stat^(1<<(p-1))] = min(dp[stat^(1<<(p-1))], t)。

最后就像上面所说，跑了两遍 Dijkstra 之后，枚举第一只龟杀的猪的集合，然后推出第二只龟杀的猪的集合，然后取最大值作为当前答案。最后就是在这些答案中取最小值即可。

0211T2 路灯

而这道题就考了我们数学。顺带一提，看到题目里面的我第一时间居然是把它想到在圆里面做，放三角形之类的，结果最后还真是 double 求值后和比较啊……诈骗→)╥﹏╥

去网上搜索了一下这种三角形的种类，它叫做本原直角三角形。它有一个定理，就是说这种三角形的三边可以分别用两个奇偶性不同的数表示出来：

$\left\{ \begin{aligned} a &= m^2 - n^2 \\ b &= 2mn \\ c &= m^2 + n^2 \end{aligned} \right. \\ (m \bmod 2 \neq n \bmod 2, m \ge n, \gcd(m, n) = 1)$

而知道定理也要知晓如何证明：

现在你要求并且的通解，那么首先可以把原式转化为。

那么首先，定理 1：。分类讨论：

若为偶数，那么有这一质因子，也就包含因子。

而若为奇数，那么就可以被描述为，然后了。

根据这个定理，我们可以推出：为一奇一偶的。因为若全为偶数，那么就不满足，而若全是奇数，那么，而这在定理 1 中是不存在的，所以也舍去，即得证。

那么这里先钦定为奇数，为偶数。而又因为，那么。

然后定理 2：和均为完全平方数。

发现这里有项和项，那么我们设，则。而因为，所以。可以发现这玩意可以被看成两个数的和与差的为，则。

然后我们就可以把原式变为含项：。而因为我们钦定为偶数，那么可以变为。而根据上一自然段得出的互质结论，并且乘起来的结果为平方数，所以只能是和均为完全平方数了。即得证。

因为和均为完全平方数，所以我们设，则，又因为为正整数，所以，然后解关于的方程可得，。本原直角三角形通解公式得证。

我们发现，这个公式，可以变式为。这个怎么样我们不管，因为都小于。我们只管。（这里默认后面的式子都含有这个隐形条件）

则这道题让我们求的其实就是求所限制的合法二元组的个数。

那么我们就可以先求出，因为，所以可以现算。最后求最接近的值即可。

我们可以先预处理，因为我们最开始要求的是的值，所以这里的代表使的最大。可以用双指针维护，因为随着的递增，递减。

于是可以表示为：

$\begin{aligned} f(l-1) &= \sum_{x=1 \land 2 \nmid x}^{\sqrt{l-1}}\sum_{y=1\land2\mid y}^{cur(x)} [\gcd(x,y) = 1]\\ &= \sum_{x=1\land2\nmid x}^{\sqrt{l-1}}\sum_{y=1}^{\frac{cur(x)}{2}} [\gcd(x,y) = 1] \\ &= \sum_{x \text{ is odd}}^{\sqrt{l-1}}\sum_{d \mid x} \mu(x) \lfloor\frac{\lfloor \frac{cur(x)}{2}\rfloor}{d}\rfloor \end{aligned}$

于是可以先预处理所有的 Mobius 函数和所有数的因数集合（因为数字大小所以不怕），然后枚举即可。

然后如何一个一个算出呢？

我们可以记录差分数组表示。这样，如果存在一个三角形，平常要让自加，现在只需要让自加，然后过后还原就好了。

具体地，枚举，就从开始枚举（因为之前代表所以这里使用合理），枚举到为止。然后如果遇到一个的二元组，那么就让自加。

最后根据差分数组还原原数组，然后用 double 计算题目里的数组，按照题目要求取最接近值，然后输出即可。

后记：啊啊啊啊啊啊比赛也没打全去证明这道题的定理去了，已经 23:50 了我要困死了……ヽ(*。>Д<)o゜

0213T1 Super

这道题可以把原集合转化为图，因为无序，就相当于是连边。然后一个操作相当于是删边然后连边。明显的，如果某个点在中的度数不等于在中的度数，那么无解。

如何构造有解？可以从小到大枚举其中一个端点，我们的目标是要让为端点的所有边全部都匹配。那么我们就可以让所有的不匹配的边全部都取出来。因为度数相等，所以中和中所有不匹配的边数量相等。我们现在要让他们两两匹配。

我们提取出其中两条边。然后我们要让它们匹配。那么我们所需要做的就是找到一个接驳点，并且在存在，那么就可以做操作，然后变为。但是因为又出了一条，所以也要保证在中不存在。

但是如果这样的接驳点不存在怎么办？正难则反，考虑在上面做手脚。那么还是像上面一样，找到，。然后做操作。可以证明这是一定可以找到的。

然后最后输出就是先从前到后输出修改的过程，再从后到前输出修改的过程即可。

时间复杂度。而因为，所以可以用邻接矩阵存图，然后找的就可以先按照方法得到一个状态，这个状态中表示不能选，表示可选。而为了优化复杂度，就可以用 _Find_first() 函数找到第一个，然后直接做即可。时间复杂度。

后记：一些神奇的事情：我在开放注册通道的间隙注册了一个小号，但是被隔壁机房发现了，于是痛失小号╥﹏╥…

0214T1 玩游戏

这道题因为，可以想到状态压缩。

因为从其它地方转移到点很麻烦，所以可以考虑从转移到其他地方的最短用时和最小代价是多少。又可以知道，假如你知道完成状态所需时间和代价，那么属于的子集的状态也可以最劣也可以在所需时间和代价完成。这启发我们最后可以用状态后缀和完成。

为了求得完成状态所需的时间和代价，那么我们设就是这个东西。考虑从小到大枚举，对于每一个再枚举这一天开放的颜色，那么。这里的代表现在我们扩展的范围是，下一天开放颜色所得到的最大范围。这个可以通过枚举和遍历边预处理出来。

最后，求出所有的之后，为了使，这些所有的都被照顾到，那么就枚举所有的使然后转移。这个思想和0207T1 交换的思想比较像。都是状态后缀和。

for(int stat=(1<<n)-1;stat>=1;stat--){
    for(int x=1;x<=n;x++){
        if(stat&(1<<(x-1))){
            dp[stat^(1<<(x-1))] = 
            min(dp[stat^(1<<(x-1))], dp[stat]);
        }
    }
}

0214T2 送外卖

这道题一眼是网络流。但是只能想到方法是网络流，具体怎么做不会……

首先，我们不管强制不让外卖员送餐的限制。直接网络流求整体最大值。那么首先，二分图连边要有：。超级源点向餐馆连边要有：，居民和超级汇点连边要有：。但是发现这种情况下我们只能求最大流下的最大权匹配。而题目中没有最大匹配这个限制。所以我们要将这个图改一下。

也就是把所有的餐馆向超级汇点连一条流量为，费用为的边。这样就保证了它的流量恒等于了。然后就可以跑最小费用最大流求出最大贡献值的相反数。最后再取反就是最大值了。

然后现在限制加进来了，就分类讨论：

假设边没有流量流过，那么删掉这条边没有影响，答案就是。
否则，边有流量流过，那么我们就要让它退流，然后重新找一条从到的最长路径。设，这就相当于是求在残量网络上，点到点的最长路。因为我们存的是负边，那么就是求最短路。负边加最短路很明显用 SPFA 求。求出最短路长度、取反后设其为，那么答案就是。注意这里边的长度是原图的边长，而不是残量网络上的。

：残量网络就是原图跑了一遍 Dinic，求了一遍最大流之后的图。

于是这道题就做完了。喜提第二劣解。

CF1817D Toy Machine IN Lv.15

对于这道题适配的构造模拟网页

为了方便讲述，请用的例子（字母）模拟（设现在的目标字母为）：

，即它是中间那个，那么执行一个 DL 操作即可。
，即它在左边，那么也简单，先做 L 操作，然后重复做 DLUL 操作，直到在最左上格为止。
，这个比较复杂。
1. 首先，先 L 一下，然后一直执行 DLUL 直到在中间的 # 之上。
2. 然后，执行 R 操作，将上面的东西移到右边。这时我们要用左边的东西把右边塞满，就一直执行 DRUR 操作直到右边被填满为止。
3. 最后，整个序列就被分成了上面的以为右端点的序列和下面的序列。我们要把这个提取出来并放到最左边。那么首先执行 LD 操作把上面序列的第一个字符提取出来。然后执行 RUR 操作合并上下两个序列并把刚刚提取出来的那个字符塞到整个序列的后面，这样就在这个序列的正中间往左格的区域了。最后执行 DL 操作把提取出来并放到最左边即可。

思维题。思维比较难想，代码 710B。

CF2064E Mycraft Sand Sort

~~由于这道题是最新最热，故难度还未发表。~~

首先看样例图示。因为排列的最小值肯定是，那么第一列其实就已经明示出数组的唯一顺序了。所以只用求满足条件的数组即可。

然后赛时就被卡在这里了。喜提 Rank 1000。o(一︿一+)o

赛后询问做法才发现，“沙子排序”的实质其实就是第列显示的颜色就是原本序列的颜色的相对顺序。就拿样例来说，第 3 列排完序后的颜色是红、橙、蓝，那么原本序列中剩下的 3 个元素的相对顺序一定也是红、橙、蓝。

而因为是一个排列，所以一定会每经过一列删除一个元素。例如从列 1 到列 2。原本的相对顺序是红绿橙绿蓝，现在第 4 行的绿沙子因为长度只有，那么就相当于是在第二列中被删除了。所以第 2 列的相对顺序就是红绿橙蓝。我们要维护每一次删除元素的时候它的相对顺序和输入沙子排列的每一列的相对顺序一致。

那么，转机来了：假设第列颜色的相对顺序是 2355541，现在原本数组删掉第 4 个 5 变成 235541，那么还有其他方法可以删除吗？肯定有的。找到这个 5 所在的颜色相同的最长连续段 555（~~舞舞舞（bushi~~），可以发现这 3 个 5 中其实删除任意一个 5 都可以达成目标相对顺序。所以这一步有种选法。

然后将它一般化，其实我们可以找到即将删除的元素在相对顺序中的位置，然后找到经过这个位置的颜色相同的最长连续段。因为每一步做法对下一步都是有影响的，所以答案就乘上最长连续段长度即可。

手玩一玩样例也可以知道。这里提供一组样例及做法：

IN：5 || 4 3 2 1 5 || 2 2 1 1 2，OUT：12

然后就可以开做了。本人的做法是开一条链，因为要删除元素，每一个节点存储它的前一个节点和后一个节点分别是什么。然后再开一个并查集，维护每一个连续段和其长度。要删除元素的时候就在链上删除这个元素，和（如果这个点在链上的前一个点和后一个点颜色相同）在并查集中合并左右端点及长度。

P4198 楼房重建 IN Lv.15

线段树单侧递归板题 + 难调题！！！！

【数据删除】【数据删除】【数据删除】【数据删除】【数据删除】【数据删除】【数据删除】【数据删除】【数据删除】【数据删除】

这道题楼房能被看见的实质其实就是：计算每一个楼房的斜率。若这个斜率是前面的所有斜率中的第一个最大值（我们记其为前缀最大值），那么这个楼房就可以被看见。

那么，我们可以用线段树来维护区间：线段树上的每一个节点记前缀最大值序列长度和这个序列的斜率的最大值。而现在我们要解决的问题其实就是如何合并区间。

我们分情况讨论：现在一个区间分左区间和右区间。

若，那么和均取的。
而若，我们就求右区间的大于的前缀最大值个数。而为了求值方便，我们反过来，求右区间的小于等于的前缀最大值个数，我们定义区间的小于等于的前缀最大值个数为（那么现在要求的就是）：
- 若，直接求即可。否则可以将其分为两个区间。
- 若，返回即可。因为后面的都大于，这不是我们要求的东西。不管。
- 否则，即，那么就到后面去找。但是这里有一个小插曲：因为后面的前缀最大值是从开始计算的，而不是从开始算的。所以我们要在计算时把后面前缀最大值个数减去，令其为。括号里的代表的就是右边大于的个数。减去就是右边的小于等于的前缀最大值的个数了。那么答案就是。
求出来值之后拿的减去它，最后加上即可。

这就是 pushup 函数和 les 函数的工作原理。所以这种线段树单侧递归主要就是合并区间的 pushup 要下点功夫了。最后查询线段树根节点的即可。

注意：这道题的斜率是个 double 型，所以有浮点误差（可以点击这里看本人之前因此而破防）。而这里又不能用长整型来替代，所以只能设置 eps = 1e-11（不知道其它指数可不可以）来减小这个误差。

P9130 Hungry Cow P IN Lv.15

这道题依然可以使用线段树维护。而因为，所以要使用动态开点线段树。

线段树上的一个节点里面存储只考虑这个区间的答案，这个区间的天数结束之后还剩下的干草个数，和这个区间内吃草的总天数。

我们开始 pushup(x)：

是好维护的，就是右儿子的加上左儿子填完右儿子的没有吃草的天数后剩下的干草数量。因为右儿子的长度和吃草的天数已知，所以没有吃草的天数就是它们之差。
也是好维护的。就是左儿子的加上右儿子的加上剩下的没有吃草的天数能被左儿子的填满几个。
就要下一点功夫了。首先左儿子的肯定是要算进去的吧，现在来对右儿子单侧递归，就是算右儿子被左儿子的尽量填满之后右儿子的：
1. 如果这个区间的长度为，那么若还有值，那就返回这个区间的端点（因为你要尽量填上，然后返回天数），否则返回原本的。
2. 否则算左儿子还有多少个空的。记其为。如果，也就是左边可以被填满，那么就返回左区间包含的天数之和（可用等差数列求得）加上右区间填满的答案。
3. 否则你就要去填左区间。那答案就是左区间填满的答案加上右区间在考虑左区间的答案。也就是我们现在正在算的东西。所以我们对于每一个线段树节点再维护一个变量，表示这个区间考虑左区间的后的答案。加上右区间的值即可。
然后给节点的赋上求出来的值，最后节点的答案就是左儿子的加上节点的值。

注意！这里的和变量的区别是：是只考虑这个区间的答案，还要算上相邻的左区间的之后，这个区间的答案！

修改操作（）就是：

如果，那么叶子节点所有变量全部赋为。
否则，那么你就要把这个空填上，所以叶子节点的。然后剩下个干草。被填的区间很明显有 1 个。

查询直接查根节点的即可。

P5278 算术天才⑨与等差数列 IN Lv.16

对于每一个等差数列为的的充要条件为：

这里的表示点的左边的距离最近的数值相同的点。没有重复肯定就是它的最近重复元素在左侧。（若没有则）。

发现这三个玩意都可以用线段树维护。

那么我们就可以用 set 维护同一种值（可以看作颜色）的下标集合，然后查询值就在 set 里面查这个前面的值就可以了。

后记：因为我脑子宕机了，写了一个 6KB 的代码（正常代码 2~3 KB）。调了一堆时间才过。跑得倒是挺快的。

Double Exp：P3792 由乃大母型原神 IN Lv.14

AT_jsc2019_final_h Distinct Integers IN Lv.15

注意：这里的下标均从开始！

先看查询。我们记为最大的使，那么任意元素两两不同的区间显然有一个性质：。

所以当我们要查找以为端点的所有合法的元素两两不同的区间，我们就查找。这是最小的合法的。然后合法的区间自然就有个了。

那么我们需要求的所有合法子区间（后面均令），那么意思就是要求，即。前面的那一项好求，现在就要求。

求区间的容易想到用线段树维护。令为，每一个节点都维护和。然后现在就要在 pushup 上面下一点功夫了。

我们现在知道区间和的，怎么将其合并？还是分讨如何求出右区间的所有：

若该区间为叶子节点，那么直接返回左区间的和叶子节点答案的最大值。
否则，将该区间分为左右子区间，若左区间的值小于区间的，那在考虑之后，左区间肯定会全部都是区间的。递归右区间即可。
否则，递归左区间找答案。再把答案加上该区间的减去该区间的右子区间的。因为此时左子区间的的限制已经强于的限制条件了。

查询的时候记得每一个都要和取。这个可以使用之前将 pushup 里面的线段树单侧递归函数的极限参数设为即可。

P4592 异或 IN Lv.15

(・∀・(・∀・(・∀・*)

这道题使用可持久化 Trie。

首先我们考虑如果只维护一维数组，求中与异或的结果的最大值。

那么就可以使用记录点的所有值插到 Trie 树上的结果。并且每一个结点还要记录一个值，代表这个点被遍历过几次，这会成为判断里面有没有第位为的依据。

int trie[N*32][2], val[N*32];
int rt[N*32];
int idxcnt = 0;
void insert(int pre, int x, int w){
    pre = rt[pre];
    rt[x] = ++idxcnt; x = rt[x];
    for(int i=30;i>=0;i--){
        val[x] = val[pre] + 1;
        int bit = (w>>i)&1;
        if(!trie[x][bit]) trie[x][bit] = ++idxcnt;
        trie[x][!bit] = trie[pre][!bit];
        x = trie[x][bit], pre = trie[pre][bit];
    }
    val[x] = val[pre] + 1;
}

然后查询就直接在中枚举该位，要尽量从高到低，让与的这一位不同的点被取到！这样才能保证异或结果值最大。

int query(int pre, int x, int w){
    pre = rt[pre], x = rt[x];
    int ans = 0;
    for(int i=30;i>=0;i--){
        int bit = (w>>i)&1;
        if(val[trie[x][!bit]] - val[trie[pre][!bit]] > 0){
            x = trie[x][!bit], pre = trie[pre][!bit];
            ans |= (1<<i);
        }else{
            x = trie[x][bit], pre = trie[pre][bit];
        }
    }
    return ans;
}

那么现在看题：

若查询点的子树，就建一棵 dfn 序的 Trie 树。insert 操作的就传该点的。查询就直接记录从这个点进子树的 dfn 和出子树的 dfn 查就可以了。
若查询路径，那么就建一棵基于父亲的 Trie 树。insert 操作的就传该点的父亲即可。查询就找 LCA，然后两条链上分别查即可。

P5795 异或运算 IN Lv.15

首先建出关于的可持久化 Trie。

查询的时候就这样：

因为很小，所以可以枚举所有的值和它们所在的节点（即上文代码的 pre 和 x）。
然后枚举位。对于位，看有多少个该位答案是的数和答案是的数（利用 val 查找）。如果答案是的数大于等于，那么就选。
否则就选，并将。但不管是选还是，都要更新所有的 pre 和 x，为了下一次统计和。
最后输出选的答案即可。

AT_abc258_g Triangle IN Lv.13

？

用 bitset 艹过去即可。

P7446 rfplca AT Lv.16

喜提一道 AT Lv.16 和 *3400(Double Exp)，爽。

这道题是一道由乃 OI。首先就想到分块。

我们分块，每一个节点存储两个信息：

这个点当前的父亲。
从这个点一直跳父亲直到跳出这个块所在的节点。

修改时，散块重构，复杂度明显。考虑整块。

目前的修改整块还是需要一个一个修改的，单次复杂度。但是考虑到一个性质：你在修改至少次之后，所有点的父亲都会小于这个块的头。这是利用了的性质。所以一个块最多被暴力修改次。花费在一个块上的复杂度最多。在这之后，我们开一个变量，记录这个块在这之后被减去的之和。这样就可以让原本的和，和变量结合起来就可以得到正确的和了。

查询的话，就分情况讨论：

若所在的块所在的块，取更大的变量，然后跳祖先到。
否则，若，取更大的变量，然后跳祖先到。
否则，若，取和里面更大的，然后跳父亲。

直到为止。于是这道题就做完了。

ABC394E Palindromic Shortest Path

我恨回文和图论。结果这两玩意还给我放一起考了。很明显没做出来，喜提 Rank 2600+。

这道题利用了回文字符串的一个性质：原本的一个回文串，两边加上同一个字母，这个新的字符串也是回文串。

于是乎，我们可以开始：用一个队列维护现在已知的所有回文串。然后用一个数组记录的答案。

那么就可以：首先将所有长度为的回文串（也就是位置）全部 push 进一个队列里，然后再把所有长度为的回文串（也就是不标有 - 的所有位置）也 push 进去。这样可以维护所有回文串的长度单调性。记得更新。

然后开始查询：首先提取出来队头，然后 pop，我们要找到一个里面没有值的坐标，然后查询是否存在并且它们的字母是否相同。若是，则计算，然后将 push 进队即可。

时间复杂度，的数据 2s 可过。

ABC394F Alkane

不明显，这个树的形态只有两种（确实不明显，但题解区里说手画一下即可得，可能是【数据删除】的 E 题把我给整蒙了）：

根的度数为，非叶子节点度数为。
根的度数为，非叶子节点度数为。

于是，可以开始树形 DP：

设为将设置为根，儿子有个，这种情况下的最大的アルカン的大小。

于是开始转移：遍历所有儿子，然后因为儿子有这一度数，所以以儿子为根的度数只有可能是或者。则转移：。注意倒序枚举，否则会有影响。然后初值则设。最后答案就是对每一个点的和取即可。

又注意到题目中有一个“至少有一个顶点度数为 ”的限制，所以要对取，那么它至少也要。

0224T1 和平外交

似乎确实是信心赛。因为这是我第一次真正意义上的场切 T1。不过 T1 在洛谷上面的难度是紫。

3 次 DFS 加上求链的和即可过。

0224T2 Maimai PRiSM

原题：CF1740G

这道题有一个性质：就是它构造出的解的剩余的光棱塔的数量永远都是。即没有不符合的。因为可以一边遍历一边构造，后面构造的时候可以证明。

因为是 chekck-max 操作，所以就从值最小的遍历到值最大的。我们来看现在遍历的这个点，然后我们让这个点的道激光射进来，然后再让之前遍历过的能射到这里的激光射进来。现在这个肯定是最大值。那么给这个光棱塔的贡献就是。

根据这个贡献就可以算出这个光棱塔应该填还是了。所以，只要这样做，总会构造出一组解使所有光棱塔成立。

然后对于的 4 个方向合并，这个可以使用并查集实现。

P7610 群星连结

大模拟。12 KB。