哎，不想说了。 虽然今年难度很高，但是真的感谢 NOIP 送我退役，再也不用一个人在一个空荡荡的机房搞竞赛了，终于可以全心全意去搞 whk 了。

在讨论《平衡树删除节点》回复：

@[天空即为极限](luogu://user/530349) 就正常的无旋 Treap，定义也很正常。由于某些原因，我没有这份代码。只有部分截图

在讨论《平衡树删除节点》回复：

@[天空即为极限](luogu://user/530349) 别人写的，AC 了。

 删除 $v$，这种写法原理是啥啊？

```cpp int merge(int u,int v){ if (!u||!v){ return u|v; } if (val[u]<val[v]){ swap(u,v); } rson[u]=merge(rson[u],v); swap(lson[u],rson[u]); return u; } ``` 可以发现…

求最优排名是简单的。\ 假设求 $x$ 的最优排名，一定只让 $x$ 先走，$f_{i} = a_{i}+|i-x|$，分讨左右拆绝对值，前后扫一遍就可以维护出排名。 考虑求最劣排名。\ 假设求 $x$ 的最劣排名。\ 发现，**一定是让一个前后缀的人先走**。比如 `... a ... b ... x`，如果让 $b…

来一个不要容斥的做法。 标号可以最后再乘，问题变为 $2n$ 个点两两配对，配对的距离不是 $m$ 倍数的方案数，等价于不能让模 $m$ 同余的配对。 设 $f_{i,j}$ 表示前 $i$ 个同余类，总共有 $j$ 个要和后面的配对，的方案数。 设第 $i$ 个同余类有 $c_{i}$ 个点。转移就枚举第 $i+1$…

我的代码不能通过以下数据，但是洛谷 AC 了。 Input ``` 2 1 0 0 6 5 0 1 2 3 4 5 ``` Answer ``` No ```

### Day -INF（初赛） J 97，S 87.5 ### Day 0 刷串串题。 ### Day 1 上午忘了。 为啥今年要求开考前不能写代码？。 到了 $14:30$，写了几分钟缺省源。 然后 T1，贪心。T2，跑最小生成树压缩边数。啊，我只会 $O(2^kkn\log{nk})$ 啊。？为啥要多路归并，空间…

这篇题解只是补充 AC 自动机题解里两个细节，前面推导请看其他题解。 经过推导，我们得到如下转移式： $$ f_{i+1,k}\gets f_{i,j}+\sum_{p=0}^{n-i-1}g_{k,p} $$ 这为啥是对的？ >不是说不能统计有前导 0 的串的贡献吗，为啥可以直接不考虑，或者直接就把长度在 $[|l|…

在文章《P4298 [CTSC2008] 祭祀 题解》发表评论：

真是太牛了! ! ! 我对您的景仰如高山流水般连绵不绝 , 您的光芒万丈荡去了我内心的黑暗 , 您是我偶像啊! ! ! !

一个限制 $l, r, x$ 等价于 $x\in a[l, r]$ 且 $1\sim x - 1$ 都在 $[1, l - 1]\cup [r + 1, n]$。考虑处理出每个 $x$ 能在哪些区间。 注意到，每个 $x$ 所在区间要么包含要么相离，所以考虑树上考虑这个问题。 一个限制只会影响 $\le x$ 的元素，…

预处理每个位置的答案。 枚举正方形右下角，二分出长度。 然后矩形取 $\max$。 可以树套树，两个 log。离线后，变为一个 log。 由于是正方形，性质远比普通矩形多。 我可以先求左边界覆盖这个点的最大矩形，这个用单调队列求解。 再求覆盖这个点的最大矩形，也用单调队列求解。 瓶颈在于预处理以每个位置为右下角的最大正…

在讨论《关于洛谷自造题目数据》回复：

@[BGM114514](luogu://user/705058) 用了 `ofstream` 的 `ios::binary` 都不行啊\ll

在讨论《关于洛谷自造题目数据》回复：

逆天，我 assert 输入对了，输出 assert 错了。\ll

在讨论《关于洛谷自造题目数据》回复：

@[liuyuhan1522](luogu://user/1435840) 看过了，`01.in` 对的就是 `01.out`，我 assert 了一下，输入没有问题。然后直接输出 `01.out`，01 过了。不知道为什么。

在讨论《关于洛谷自造题目数据》回复：

@[liuyuhan1522](luogu://user/1435840) 就用 txt 输入进去，std 写输出。

我造的数据编号是 `01.in/01.out, 02, ...`，为什么 std 会 WA 一些啊。

当 $r-l\gt 2000$，暴力最多跳 $\frac{n}{2000}$ 次，每次找给定位置右侧 $Y$ 第一次出现的最小位置。先把 $A, B$ 拼起来跑 SA。每次在 height 二分出和 $Y$ 的 $\mathrm{lcp}$ 长度 $\ge |Y|$ 的区间 $[l, r]$。考虑在线段树上维护区间 $…

在讨论《求问 dp 优化》回复：

@[Forge_Unique](luogu://user/930686) 已关

在讨论《求问 dp 优化》回复：

@[Forge_Unique](luogu://user/930686) 感谢/bx/bx

在讨论《求问 dp 优化》回复：

@[Forge_Unique](luogu://user/930686) 转移就是 $f_{i, x, y}$ 从 $f_{i-1}$ 的一个矩形内求和，这个矩形 $x_0, y_0, x_1, y_1$ 满足 $x_0 = x - m, x_1 = x + m, y_0 = y - m, y_1 = y + m$，$…

一个二维 dp $f_{i, x, y}$，$i$ 是转移层数，$x, y$ 是坐标，每次 $f_{i, x, y}$ 从 $f_{i-1}$ 的一个矩形里转移，除了前缀和，一维形式可以矩阵加速，这个能否优化啊。

在讨论《求助一个区间问题》回复：

@[jianami](luogu://user/775991) 感谢大佬/bx/bx

在讨论《求助一个区间问题》回复：

@[jianami](luogu://user/775991) 额，这个好像没原题，不知道复杂度最优是多少。求您的建图方法。

给定 $n$ 个带权区间，和 $m$ 个点，以及整数 $s$。求最少选出多少区间，使得对于每个点 $p_i$，覆盖 $p_i$ 的区间的权值和 $\ge s$。 求大佬解答。

题解区里二分 + Hall 定理的判断方法，并没有保证区间长度 $\le L$。这里补一个证明。 首先，新郎 $\le L$，新娘 $\gt L$，这个对答案是没有贡献的。 考虑新郎 $\gt L$，新娘 $\gt L$。 ![](https://cdn.luogu.com.cn/upload/image_hostin…

在讨论《关于一个式子的简化》回复：

@[Polarisx](luogu://user/836759) 哦，懂了，/bx/bx。

在讨论《关于一个式子的简化》回复：

@[Polarisx](luogu://user/836759) 您第三步到第四步 $\sum_{i=1}^{x} i(i-1)^{s}$ 是咋变的呢？/yiw

给定了 $x, m$。 求 $s\in [1, n]$ 的每个 $g_s$。 $$ g_s = \sum_{m=1}^{x} \frac{(x-m+1)^{s} - (x-m)^{s}}{x^{s}}\times m $$ dalao 们看看能否做到 $O(n)$？