杜老师，我们喜欢你

我们喜欢你呀

我们喜欢你

阿皮阿杜老师，我们喜欢你

我们喜欢，插优第歪爱吃

先咕一下，闲下来写。

是我场上写的做法，只不过场上我以为它的复杂度是 $O(n \log n)$ 状物。

中间复杂度分析的部分有大量我的扯淡，请在看中间的分析之前先跳到最后查看正确的复杂度分析。

来写一下。

由于我不会 SMAWK，所以只能随机二分，自然询问次数为 $O(n\log n)$。

考察瓶颈所在的位置：二分提供 $O(\log n)$，双指针提供 $O(n)$。由于二分显然不可能被继续优化，考察如何减少双指针的次数。我的想法是设置步长 $s$，每一次指针移动的时候，相比于每次移动 $1$ 个位置，我们可以每次移动 $s$ 个位置。

这可能会带来误差，考察误差的影响。形象的思考带步长的双指针的过程。普通双指针实际上是找到了一个分割线/轮廓线，使得左上角是 $\leq mid$ 的数，右下角是 $> mid$ 的数。带步长的双指针找到的轮廓线是对这个轮廓线的一个粗略近似，但是它相比原轮廓线的误差不会超过步长 $s$。

那么我们二分再往两边递归的时候，如果想往左上递归，就将轮廓线往右下平移 $s$ 个位置，想往右下递归，就将轮廓线往左上平移 $s$ 个位置。这样所有当前可能成为第 $k$ 大的位置就仍然会被包含在待确定的区域中。

分析一下这个东西的询问次数。

我场上认为这个东西仍然是 $O(n\log n)$ 的，没有什么实质优化，所以一直在尝试调整步长 $s$ 并对拍。现在可以仔细分析一下询问次数了。下面的分析过程不太严谨，但是感性理解足够了。

设 $f(x)$ 表示当前待确定区域的左上到右下的斜向宽度（这里默认左下到右上方向的宽度为 $n$，显然不可能超过这个值）为 $x$ 的时候需要的询问次数。设步长为 $s$，有：

$$ f(x)=\min_{s} f\left(\frac{x}{2}+s\right)+O\left(\frac{n}{s}\right) $$

由于是随机二分，所以实际应该是一个概率分布，但是我正在感性理解，于是当成 $x/2$ 计算了。取 $s=\log x$，进行 $\log x$ 轮，由于 $s$ 远小于 $x$，暂时忽略这个 $f(x/2+s)$ 中的 $s$。那么有粗略的递推式：

$$ f(x)=f(\log x)+O(n) $$

然后大概就能得出 $f(n)=O(n\log^{*}n)$ 了。

虽然忽略 $s$ 这个事情看上去就不严谨，但是感性理解大概能得到一个这样的结果。然后这里不一定取到了下界，所以可能还会更优。

没有分析复杂度的常数，因为这东西本来就复杂度不优。并且我分析不明白，就这样。

感觉分析其实可能是错的，如果每一步都取 $s=\log x$，且忽略 $s$ 的话，只能得出：

$$ f(x)=f\left(\frac{x}{2}\right)+O\left(\frac{n}{\log x}\right) $$

然后这个解出来是 $f(x)=x\log \log x$。

请懂的人教我一下。@monstersqwq 教我一下谢谢。

其实是线性的，取 $s=x/2$，感谢咋克。

仔细分析各种乱七八糟的东西，最后可以得到 $15.5n$ 的复杂度上界。哈哈，没有任何意义。

Day 1

A

行列分别处理，随便枚举一下哪个坐标转完之后最小即可。

B

一种构造方案是：将 1 看成 (，0 看成 )，然后跑一个循环的括号匹配，把匹配上的右括号传过去。

第二遍把 1 看成 )，0 看成 ( 做一个对称的操作即可。

杜老师告诉我，这个模型是一个 Hypercube，然后做 Hypercube 的 symmetric decomposition，找到输入集合的补集在链上的对称点即可。

C

考虑分的两个子序列，它们值域有交的第一个位置，容易发现之后一定可以取到理论上界，也就是答案为：该位置前的答案 $+$ 满足所有元素小于子序列 $1$ 的 $\min$ 的最长下降子序列长度 $+$ 满足所有元素大于子序列 $2$ 的 $\max$ 的最长上升子序列长度。

在这个位置之前，两部分值域不交，一定只有 $O(n)$ 种情况，用线段树维护转移，每次将一个状态分裂成两个状态。对于最长上升子序列和最长下降子序列，倒着用线段树做一遍这个过程，把修改看做一些区间加，然后正着做的时候倒过来模拟这些区间加即可。

时间复杂度 $O(n\log n)$。

D

把集合放到 Trie 上考虑 mex-极限。不妨设当前子树中有数不存在于集合中，分类讨论：

1. 左儿子没有满：mex-极限和左儿子的 mex-极限相等；
2. 左儿子满了，右儿子中最小的数 $2^k$ 存在：mex-极限和右儿子的 mex-极限相等；
3. 左儿子满了，右儿子中最小的数 $2^k$ 不存在，最大的数 $2^{k+1}-1$ 不存在：mex-极限是 $2^k$；
4. 左儿子满了，右儿子中最小的数 $2^k$ 不存在，最大的数 $2^{k+1}-1$ 存在：此时一次操作后会将整个子树翻转，且翻转后的左子树不满，所以 mex-极限和右子树翻转之后的 mex-极限相等。

于是容易写出 DP 状态，使用 NTT 转移。

时间复杂度 $O(2^k k^2)$。

Day 2

A

没咋看，看上去就是简单题。

B

跑一遍 DP，保留所有起点 DP 值为奇数或偶数（选择个数较多那个奇偶性）的区间，注意在最优方案中的区间需要保留，不能让答案小于 $\frac{m}{2}$。正确性显然。

C

将答案转化为 $n(n-1)m$ 减去每个人到达终点之后其他人走到检查点的次数求和。注意到检查点坐标的和不大，所以可以将其按照前缀长度 $\max$ 分成若干段，每一段贡献其实相同。

然后随便做一下，复杂度 $O(n\sqrt x)$。

D

给一个点点权增加 $1$，答案最多增加 $1$。于是可以从全 $l_i$ 慢慢增加到全 $r_i$。每个点增加的过程中一定是一段前缀对答案没影响，剩下来的后缀每次给答案 $+1$。用全局平衡二叉树做修改点权，查询全局最大独立集，然后容易找出这个前缀和后缀的分界点。

时间复杂度 $O(n\log n)$。

考虑从 $s,t$ 开始双向 Dijkstra 跑最短路，直到两边经过的点集出现公共点为止，设为 $p$。由于数据随机，所以每个点会等概率地被 $s$ 和 $t$ 增广到，由生日悖论可以得出，此时经过的点的数量是 $O(\sqrt n)$ 级别的。

考虑此时如何统计答案，容易发现会被算进答案的路径形态一定是：$s\to u\to v\to t$，其中 $u,v$ 之间直接由边相连，$u$ 和 $v$ 分别属于刚才的最短路过程中被 $s,t$ 增广到的集合。该结论证明是简单的，因为如果路径形态是 $s\to u\to x\to v\to t$，由最短路过程的性质有 $dist(s,x)\geq dist(s,p),dist(x,t)\geq dist(p,t)$，这样的路径必然是不优的。事实上需要特殊考虑 $s\to p\to t$，不过这是 trivial 的。

此时我们得到了一个 $O(qm\log m/ \sqrt n)$ 的做法。

为了优化掉复杂度中的 $m$，我们对 Dijkstra 应用一个优化：将一个点所有出边按照边权排序，在松弛时不要全部同时加入优先队列，而是当上一条边出队之后再加入下一条边。这样，第一部分的复杂度就变成了 $O(q\sqrt n\log n)$。

对于第二部分，我们枚举路径中的 $u$ 和它的出边，去更新答案，总共需要考虑 $O(m/\sqrt n)$ 条边。但是事实上，我们可以考虑在 $dist(s,u)$ 和 $dist(v,t)$ 中较小的那一侧去枚举。若 $dist(s,u)+e(u,v)+dist(v,t)\geq dist(s,p)+dist(p,t)$，那么这条路径必然不优。所以我们只需要枚举到 $e(u,v)\leq 2(\max\{dist(s,p),dist(p,t)\}-dist(s,u))$ 即可，较小的那一侧是 $t$ 那一侧的情况是对称的。

那么这一部分总共有多少条边呢？感性理解，对于 $e(u,v)\leq 2(\max\{dist(s,p),dist(p,t)\}-dist(s,u))$ 的边中，满足 $e(u,v)\leq \max\{dist(s,p),dist(p,t)\}-dist(s,u)$ 是所有在第一部分最短路过程中被处理过的边，而这两个值域恰是两倍关系，故第二部分的边数也是 $O(\sqrt n)$ 级别的。

这个感性理解事实上有潜在的漏洞，因为涉及到的概率不一定独立。钱哥声称，第二部分的边数的上界为第一部分边数乘 $O(\log n)$，那么第二部分的边数是 $O(\sqrt n\log n)$ 级别的。总时间复杂度是 $O(q\sqrt n\log n)$。

关于这个问题，钱哥有一个绝妙的证明，但是后面忘了。