A

杜老师做的，听说是烂题。

B

签到题，先咕了。

C

做法一

倒过来模拟染色过程，考察联通块数的变化量。可以发现，倒过来模拟这个过程时，右边界有相同的颜色，下边界也有相同的颜色，所以染色会增加连通块当且仅当新的颜色与右边界和下边界都不同。

容易想到用线段树维护 DDP，每个节点要记录 $2^2$ 个值，表示不翻转/翻转行，不翻转/翻转列时的 DDP 状态。维护是简单的。

时间复杂度 $O(n\log n)$，有 $36$ 的常数，能跑过去。

做法二

先咕着。

D

不是我做的，咕了。

E

存在一个暴力的费用流做最小权完美匹配的做法，用 Cost Scaling 和匈牙利可以做到 $O(n^3\log V)$，常数比较大，应该是过不去的。

分析菱形覆盖的形态，发现对于上半部分，第 $i$ 行与第 $i+1$ 行间的竖直菱形数量恰好为 $i$，且相邻两层间的竖直菱形插空分布。于是可以把竖直菱形按照斜向分组，建出一个新的费用流，每一组对应 $1$ 的流量。此时只需限制点的流量和边的流量 $\leq 1$ 就可以保证竖直菱形插空分布。分类讨论一下边权的值暴力跑费用流。

注意到这个新图流量只有 $O(n)$ 大小，于是跑暴力即可，时间复杂度 $O(n^3\log n)$，可以通过。

F

签到题，求出每一层的 SG 函数，异或起来就做完了。

G

签到题，二分答案之后排序来 check 即可。

H

还没完全会，等过了再补。

I

杜老师做的签到题。

J

容易发现 $(1,0),(0,1),(-1,-1)$ 可以构造所有点，故答案 $\leq 3$。先特判答案为 $1$ 的情况。

要让答案 $\leq 2$，至少需要所有点在同一个半平面内。此时需要特判如果存在两个点方向恰好相反，如果还有不在直线上的点就答案为 $3$，否则答案为 $2$。

然后对于所有点在同一个半平面内的情形构造。对于所有点都 $x\geq 0$ 的情形，可以构造 $(0,1)$ 和 $(1,-10^{18})$ 作为答案。类比到所有情形，只需要半平面对应的直线的一个方向选择一个向量，然后找到半平面内尽量接近直线的点，往另一个方向拉到无穷远处即可。

尽量接近直线的点可以 exgcd 求出。

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

K

可以建出一个差分约束模型，于是可以得到如果有解，那么存在一种方案每个点的值要么是 $0$ 要么是 $K$。

对于两个有包含关系的区间，可以确定大区间减去小区间的部分全是 $0$，并删除大区间。得到一个位置是 $0$ 之后需要把剩余的区间缩起来然后继续考虑包含关系，同时判掉区间被删空的情形。

对于不存在包含关心的情形，排序之后贪心即可，一定有解。

时间复杂度 $O(n\log n)$。需要注意实现的细节。

L

树上背包模板。

M

将代价拆到每条边上，变成 这条边交换的次数 $+$ 这条边两侧均出现了的颜色种类数。如果不进行交换，一条边的代价 $\leq 2$。对于初始存在一条边代价为 $0$ 的情形，显然取到理论最小值 $n-2$，特判即可。

然后可以发现，要让一条初始为 $2$ 代价的边变成 $1$ 代价，必须要用它进行一次交换，并且最终它恰好隔开黑色和白色。于是这样的边最多一条，只需要判这种边存不存在。

容易发现存在的充要条件是这条边：

1. 将树分成了两个区域，大小分别是黑色点个数和白色点个数。
2. 黑色区域有恰好一个白点。
3. 白色区域有恰好一个黑点。
4. 这个黑点与这个白点都不是叶子。

判断这四个条件即可，时间复杂度 $O(n)$。

时光荏苒，小 S 和小 Y 也会散去。而我们和一个人保持连接的方式就是把小 S 和小 Y 变成 S 接 Y，仅此而已。

先进行一些分析。假设需要让 $(a,b,c)$ 分别是冠亚季军，那么：

1. $a$ 会尽量多过题且不会罚时；
2. $c$ 只会过一个题，且是最后一次提交才通过；
3. 除了这三个人之外的所有人都不过题。

更进一步的分析可以得到，$b$ 可行的过题情况有两类：

1. 在一次提交通过了唯一一个题，之前可能有罚时；
2. 过了两个题，最后两发提交才通过。

预处理出每个人作为冠军和季军的罚时，称为 $l_i,r_i$。只需要对于所有人作为亚军时的所有可行罚时情况，统计对应的 (冠军, 季军) 对的个数即可。

注意到，亚军过一个题且罚时大于 $L$ 的所有可行罚时中只需要保留最小的那个即可。所以可以根号分治统计所有人作为亚军的可行罚时情况。时间复杂度是 $O(n\sqrt L)$ 的，具体地，可以 $O(c^2)$ 或 $O(c+L)$ 来统计可行罚时情况。

然后计算出合法的数量。可能存在统计的时候多算冠军和季军是同一个人的情况，此时需要减掉。

查询需要减掉的情况数，本质是进行 $O(n \sqrt L)$ 次如下询问：对于 $[l,r]$，查询有多少 $i$ 满足 $[l_i,r_i]\subseteq [l,r]$。这是一个二维数点问题，可以离线下来做可持久化分块。更简单的做法是，容易发现，这 $O(n\sqrt L)$ 次询问中，只有 $O(n)$ 次询问的区间 $[l,r]$ 长度大于 $20$，所以可以提前预处理较短的区间的答案，对于较长的区间用主席树回答。

总时间复杂度是 $O(n\sqrt L + n\times 20^2 + n\log n)$。代码不是很难写，但是细节比较多。实现的时候不需要精细实现，复杂度多一点 $\log$ 或者 $20$ 也没卡。

关于 std：我偷看了一眼，看上去就没有根号分治，应该是 polylog 的。大概可以，每个人作为亚军时，每个提交对应了罚时情况中的一个公差为 $20$ 的等差数列，维护出区间之后大概处理一下，可以做到 $O(n\log n)$ 或者 $O(20\times n\log n)$。

IMO2023SL C1

将格子按照横纵坐标加和模 $3$ 分成等价类。每个等价类个数奇偶性需要相同，故可知 $3\mid nm$。

同时所有满足 $3\mid nm$ 的 $(n,m)$ 都合法。由 $3\times 2$ 和 $3\times 3$ 的构造显然得到，两个构造分别为：

00    11    11
00 -> 01 -> 11
00    00    11

和

000    011    011    011    101    111
000 -> 001 -> 101 -> 110 -> 100 -> 111
000    000    110    111    111    111

杜老师，我们喜欢你

我们喜欢你呀

我们喜欢你

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

我们喜欢，插优第歪爱吃

先咕一下，闲下来写。

是我场上写的做法，只不过场上我以为它的复杂度是 $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)$。

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