task6

[TOC]

1. 湖北省选模拟 2023 - 日记 [Keter] ✔️

题面

给定两个字符串 $S,T$

设 $P$ 为 $S$ 的前缀（可以为空），$Q$ 为 $S$ 的后缀（可以为空），求有多少本质不同的 $P+Q$ 包含 $T$ 为子串

$1\le |S|\le5\times10^6,1\le |T|\le2|S|$

题解

Sol

神仙题。

设 $|S|=n,|T|=m$

考虑如何选取代表元。

如果不要求包含 $T$，那么答案是容易计算的，将代表元选择为 $|P|$ 最小的串，那么每当 $P$ 的下一个字符等于 $Q$ 的第一个字符时就会产生一次重复，那么用 $|S|^2-\sum cnt_i^2$ 即可

同理，我们也可以这样求出 $|P|,|Q|$ 的长度分别在某个区间内的本质不同 $P+Q$ 数量

首先，有 $P$ 包含 $T$ 或 $Q$ 包含 $T$ 的情况。

设 $c$ 表示 $T$ 在 $S$ 中第一次出现的结束位置，$d$ 表示 $T$ 在 $S$ 中最后一次出现的开始位置，如果 $|P|\ge c$ 或 $|Q|\ge n-d+1$，$P+Q$ 一定包含 $T$

我们用总共的本质不同字符串数量，减去 $|P|<c$ 且 $|Q|<n-d+1$ 的数量，剩下的字符串一定都包含 $T$，那么接下来我们只需要考虑 $|P|<c$ 且 $|Q|<n-d+1$ 的字符串即可

令 $c\leftarrow c-1,d\leftarrow d+1$

这意味着 $T$ 一定是由 $P$ 的后缀和 $Q$ 的前缀组成的（我们认为这个后缀/前缀可以为空）

令 $zs_i$ 表示 $S[i:c]$ 和 $T$ 的最长公共前缀，$zr_i$ 表示 $S[1:d]$ 和 $T$ 的最长公共后缀，这可以用 Z 函数求出

我们枚举 $T$ 从 $P$ 和 $Q$ 的哪里开始匹配，设 $T$ 从 $P$ 的 $i+1$ 位置开始匹配，在 $Q$ 的 $j-1$ 位置结束匹配，那么不难发现对于一个 $i,j$ 最多有一种合法的串，有一种串的充要条件是 $zs_{i+1}+zr_{j-1}\ge m$

但是这样还是可能会重复，不同的 $i,j$ 可能会生成相同的串，如图所示：

这种情况下，我们人为选择统计 $P_1$

考虑 $P$ 满足什么条件才会成为 $P_2$，那么当且仅当存在 $per$ 使得：

• $per$ 是 $T$ 的周期
• $P_2$ 长为 $per$ 的后缀与 $T$ 的前缀相等
• $zr_{j-1}\ge per$

枚举 $i$，那么就可以跑 kmp 确定满足前两个条件的最小 $per$，求一下同时满足 $zr_{j-1}\ge per$ 和 $zs_{i+1}+zr_{j-1}\ge m$ 的 $j$ 个数即可

复杂度 $O(n)$

---

2. CF1361E - James and the Chase [Euclid] ⭐

题面

给定 $n$ 个点 $m$ 条边的有向强连通图，称一个点是好的当且仅当这个点到其他点都恰好有一条路径，如果至少有 $\frac15$ 的点是好点，则输出所有好点编号，否则输出 -1

$1\le n\le10^5,1\le m\le2\times10^5$

题解

Sol

这个 $\frac15$ 很神秘，我们可以想到，说不定是什么随机相关的东西。

那么我们随机一个点 $r$，判定它是否是好点，考虑好点满足什么性质。

首先，由于这个图强连通，所以一个点一定能到其他所有点，那么我们找出一棵以 $r$ 为根的外向生成树，那么 $r$ 是好点当且仅当所有非树边都是返祖边

那么我们可以 $O(n)$ 进行 check，如果在 $p$ 次后还没有找到好点就直接输出 -1，错误率为 $0.8^p$

接下来我们考虑这个性质能为我们带来什么。

首先，如果一个点 $u$ 子树内有至少两条到 $u$ 祖先的返祖边，那么 $u$ 到 $fa(u)$ 显然有两条路径

如果 $u$ 子树内没有到 $u$ 祖先的返祖边，$u$ 显然是好点

因此只用考虑 $u$ 子树内只有一条到 $u$ 祖先的返祖边的情况，设这条边为 $u\rightarrow v$，那么 $u$ 是好点当且仅当 $v$ 是好点

复杂度 $O(pn)$

---

3. CF568D - Sign Posts [Euclid]

题面

给定 $n$ 条形如 $ax+by+c=0$ 的直线，请选择 $k$ 个点，使得每条直线至少经过这 $k$ 个点中的一个

构造方案或判断无解

$1\le n\le10^5,1\le k\le5$

题解

Flamire 做法

Sol

如果有解，那么至少有一个点被经过 $\left\lceil\dfrac nk\right\rceil$ 次，而这样的点最多只有 $O(k^2)$ 个，因此我们可以考虑爆搜。

首先，我们随一条直线，计算其他直线与这条直线的交点，然后取出所有出现次数 $\ge\left\lceil\dfrac nk\right\rceil$ 的，这样每个满足条件的点被算到的概率至少是 $\frac 1k$，意味着我们随 $O(k)$ 次就可以找出所有满足条件的点

那么复杂度是 $O(n(k!)^2)$ 的，写的不那么丑就可以过了。

editorial 做法

Sol

考虑抽屉原理，任选 $k+1$ 条直线，一定存在两条直线由同一个点覆盖，也就是说它们的交点中一定有一个被选择的点

直接这样搜索是 $O(n\cdot\frac{k!(k+1)!}{2^k})$ 的，好像也能过。

但是可以优化。

考虑一个点如果被 $k+1$ 条直线经过，那么将上文的 “$k+1$ 条直线” 取为这些直线，可以说明这个点必选

而如果有解，那么至少有一个点被经过 $\ge\left\lceil\dfrac nk\right\rceil$ 次，当 $n$ 足够大（比如 $n>30k^2$）时这个值 $\ge k+1$，也就是说一定存在一个被经过 $k+1$ 次的点，并且我们可以通过上一种做法的随机在 $O(k)$ 次随机内找到任意一个必选点，那么我们就能减小 $k$ 进行递归了

因此复杂度为 $O(nk^2+k^2\cdot\frac{k!(k+1)!}2)$

---

4. CF1805F2 - Survival of the Weakest (hard version) [Keter] ⭐

题面

定义为 $F(a_1,a_2,\cdots,a_n)$ 为最小的 $n-1$ 个 $a_i+a_j(1\le i<j\le n)$ 组成的数列

给定 $n$，求对给定数列 $a_1,a_2,\cdots,a_n$ 做 $n-1$ 次 $F$ 后剩下的数的值，对 $10^9+7$ 取模

$2\le n\le2\times10^5,0\le a_i\le10^9$

题解

Sol

神秘。

接下来的讨论均默认序列有序。

首先，我们可以在保证所有数非负的前提下集体减去一个数 $x$，最后再将答案 $+x\cdot2^{n-1}$ 即可

那么我们现在可以使 $a_1=0$。

考虑 $a_n$，经过一次 $F$ 后存在一个包含 $a_n$ 的项留在序列中当且仅当 $0+a_n<a_2+a_3$

那么这时我们的序列变成了 $[a_2,a_3,a_4,\cdots,a_n]$，将第一项变为 $0$ 后就是 $[0,a_3-a_2,a_4-a_2,\cdots,a_n-a_2]$

这时，如果 $a_n$ 再次留在了序列中，那么序列（将第一项变为 $0$）就会成为 $[0,a_4-a_3,a_5-a_3,\cdots,a_n-a_3]$，由于 $a_n<a_2+a_3$ 且 $a_2\le a_3$，所以 $a_n-a_3\le\frac12a_n$，而如果 $a_n$ 没有留在序列中，最大值只会更小

因此，如果 $a_n$ 在一次 $F$ 后留在了序列中，必然会导致最大值在两次内降到原来的一半以下

这说明，只有前 $K=2\log_2 a_i+O(1)$ 个元素有用，那么只需要模拟前 $64$ 个元素即可

复杂度 $O(n\log a_i\log\log a_i)$

---

5. CF1838F - Stuck Conveyor [Keter]

题面

交互题。

有一个 $n\times n$ 的传送带矩阵，你可以规定每个传送带的方向，它会将每个到达这个格子的物体向该方向移动一格

一个物体运动到矩阵外时，它会停止。

但是有一个传送带坏了，无论你规定什么方向，它都只会向一个特定的方向移动物体

现在只给定 $n$，你可以进行 $25$ 次询问，每次给每个传送带规定一个方向，然后提供一个 $(x,y)$，交互库会回答如果 $(x,y)$ 初始有一个物体，如果最后它会停止，交互库会给出最后的坐标，否则交互库会返回 -1 -1

你需要求出坏掉的传送带的坐标，以及它固定的方向

$1\le n\le100$

题解

Sol

烂题。

先把坏掉的传送带向矩阵外面指的情况判掉，这是好判的，造一个圈即可。

考虑路径 $(1,1)-(1,n)-(2,n)-(2,1)-(3,1)-(3,n)-\cdots$，我们先构造矩阵让传送带都指向这个方向，那么要么进入死循环，要么从终点出去

如果进入死循环，那么我们可以二分出行，然后再二分出列

如果从终点出去，那么讨论一下可知将路径反向一定会进入死循环，那么同样进行二分即可

操作次数是 $2\log n+O(1)$

---

6. luoguP9150 - 邮箱题 [Keter] ✔️

题面

给定 $n$ 个点 $m$ 条边的有向图，给定一个排列 $k_1,k_2,\cdots,k_n$，$i$ 号点上有 $k_i$ 号点的钥匙

你到一个节点会立刻拿起这个节点上的钥匙，你只有获得了一个点的钥匙才能进入这个点

对每个 $i$：

假设你当前在 $i$，并拿到了 $i$ 的钥匙，你每次可以任选一条已经有钥匙的邻点，并走过去

你需要求出从 $i$ 能到多少多少点，以及 $i$ 能到多少个点并仍能回到 $i$

$3\le n\le1.5\times10^6,0\le m\le3\times10^6$

题解

Sol

考虑 $i\rightarrow k_i$ 的若干环，容易发现不同环之间是互相独立的。

对每个环分别处理，下面的讨论中假设环上的节点分别是 $1,2,\cdots,n$，我们把环复制两份，转化为链上的问题，那么我们需要处理的就是若干长为 $n$ 的区间

考察一个区间会形成什么联通情况，$i$ 能到达的点一定是一个区间的形式，并且满足对区间内的每个 $k$ 都满足 $k$ 能到 $k+1$

经过一些观察，我们发现最后的结构一定是若干条链，每条链是若干连续的强连通分量串起来，那么我们只要能够维护出这个结构即可

想一下，肯定是在起点处加点比较容易，因此我们考虑从 $i+1$ 开始的区间推 $i$ 开始的区间

大致想法就是每次检查第一条链是否能和第二条链合并，我们设第一条链是 $[i,x]$，那么就是要检查 $x$ 是否能到 $x+1$，我们可以维护出每个 $k$，编号 $i$且$pre_k$和$x$ 属于同一个强连通分量

观察一下，如果 $x$ 和 $i$ 不属于同一个强连通分量，也就意味着合并这两条链与 $i$ 没有关系，那么这两条链一定在 $>i$ 的时候就已经合并了，所以第一条链一定整体是一个强连通分量，才有机会合并

但是问题在于我们合并链之后没办法快速合并强连通分量，暴力无法均摊复杂度

因此我们考虑合理利用性质，由于第一条链是一个强连通分量，所以对于每条链，我们存最大的 $x$，使得存在一条边 $x\rightarrow u$ 满足 $u>i$ 且 $u$ 和 $x$ 不强连通，然后用并查集均摊合并

复杂度 $O(n\alpha(n))$

---

7. CTT2021 - 经典游戏 [Keter]

题面

有两个人在一棵 $n$ 个点的有根树上博弈，初始第 $i$ 个节点有 $a_i$ 个棋子，每一回合内一个玩家可以将任意棋子挪到它原来节点的子树中的任意一个节点（但是不能保持位置不变），不能操作者输

它们会玩 $m$ 轮游戏，每轮游戏有两个参数 $x,y$，意义如下：

游戏开始前，在 $x$ 处新增一个棋子，这个棋子会在之后的所有游戏中保留

然后，先手可以选择将树的根设为 $y$ 或任意与 $y$ 直接相连的点

之后，后手可以任意选择一个节点，新增一个棋子

询问先手有多少种决策树根的方式，无论后手怎么加棋子，先手都有必胜策略

$1\le n,m\le10^9,0\le a_i\le10^9$

题解

Sol

首先用 SG 函数分析一波，$a_i$ 可以直接模 $2$，在这之后判断每个 $a_i=1$ 的点的子树高异或起来是否 $\neq0$，$\neq0$ 为先手胜，否则后手胜

以 $1$ 为根考虑。

定义 $R_u$ 为以 $u$ 为根时所有有棋子的点的树高异或和，$H_u$ 为从 $u$ 出发的最长链的长度，那么一个决策时优的当且仅当 $R_u\le H_u$

考虑一次修改会对 $R$ 带来哪些影响：

称从 $x$ 出发的最长链上的第一个节点为 $rson_x$，$x$ 向子树内出发的最长链上第一个节点为 $son_x$

• 如果 $rson_x=fa_x$，则相当于对 $x$ 子树内的点异或次长链长度，$x$ 子树外的点异或最长链长度
• 如果 $rson_x\neq fa_x$，则相当于对 $rson_x$ 子树内的点异或次长链长度，$rson_x$ 子树外的点异或最长链长度

这可以用树状数组来维护。

那么现在我们会判断一个树根是否合法了，但与 $y$ 直接相连的点有可能很多，需要快速处理

进行一些观察，对一个一个与 $y$ 直接相连的点 $v$ ，如果满足 $v\neq fa_u,v\neq son_u$，那么所有 $H_v$ 都是相同的

因此，如果我们将所有这样的 $R_v$ 都放到一个数据结构里，我们每次的查询就是查询数据结构内 $\le H$ 的数的个数

而我们这个数据结构还需要支持整体异或上一个值，不难想到开 $n$ 个 01-trie，然后用树状数组维护每个 01-trie 的整体异或标记

那么总复杂度就是 $O(n\log A)$

---

8. CTT2021 - 算术 [Safe]

题面

对于给定的 $B,p$，以及一个参数 $k$，定义如下一种判断任意一个 $B$ 进制整数 $x$ 是否被 $p$ 整除（以下运算均在 $B$ 进制下考虑）：

将 $x$ 在 $B$ 进制下的表示分段，每 $k$ 位分一段，从低到高依次得到 $b_0,b_1,\cdots,b_m$，然后对于所有下标为奇数的 $b_i$，将 $b_i$ 赋值为最小的 $\equiv -b_i\pmod p$ 的非负整数，所有下标为偶数的 $b_i$，将 $b_i$ 赋值为最小的 $\equiv b_i\pmod p$ 的非负整数

经过上述操作后，$\overline{b_0b_1b_2\cdots b_m}\equiv x\pmod p$

给定 $p$，$t$ 组询问，每次给定一个 $B$，询问在当前的 $B,p$，最小的使得上述算法成立的 $k$ 是多少，或者报告无解

$t\le10^5,2\le p<B\le10^{15}$

题解

Sol

当原数为 $p$ 的倍数时，我们要求新数也是 $p$ 的倍数，代入一下得到条件：$\forall 1\le i\le m,(-1)^iB^{m-i}\equiv B^{ik+m}\pmod p$

取 $i=m=1$，即 $B^{k+1}\equiv -1\pmod p$，不难验证这两个条件是等价的，同时我们也说明了 $\gcd(B,p)\neq 1$ 的时候无解

当原数不为 $p$ 的倍数时，我们要求新数不能是 $p$ 的倍数，在原来条件的基础上只需满足 $\forall 0<x<p,xB^m\not\equiv0\pmod p$，而对于 $\gcd(B,p)=1$ 显然成立

那么我们要找到最小的 $k$ 使得 $B^{k+1}\equiv -1\pmod p$，这意味着 $B^{2k+2}\equiv 1\pmod p$，那么我们可以从 $\varphi(p)$ 开始，不断试除质因子，就可以找到最小的 $k$

复杂度 $O(\sqrt p+T\log^2p)$

---

9. CTT2021 - 简单数据结构 [Keter] ⭐

题面

给定长为 $n$ 的数组 $a_1,a_2,\cdots,a_n$，$q$ 次操作，每次操作为以下几种中的一种：

• 1 v，对所有 $a_i$ 执行 $a_i\leftarrow\min(a_i,v)$
• 2，对所有 $a_i$ 执行 $a_i\leftarrow a_i+i$
• 3 l r，查询 $\sum_{i=l}^ra_i$

$1\le n,q\le2\times10^5,0\le a_i,v_i\le10^{12}$

题解

Sol

好题！！！！！！11

这些操作意味着，如果 $a_i,a_j(i<j)$ 在某一时刻满足 $a_i\le a_j$，那么之后一定一直满足 $a_i\le a_j$

进一步观察，所有被 1 操作影响过的位置组成的子序列，一定单增，因此我们可以整体维护，这样 1 操作就变成了线段树上二分+区间推平，而剩下没被 1 操作影响的部分又只有 2 操作，因此是容易维护的

那么我们只需要知道每个 $a_i$ 最早什么时候被 1 操作影响，设 $b_j$ 表示 $j$ 操作之前有多少次 2 操作，那么就是求最小的 $j$ 使得 $a_i+i\cdot b_j\ge v_j$，这个可以通过整体二分+凸包来求得

总复杂度 $O(n\log n)$

---

10. CF1870F - Lazy Numbers [Keter]

题面

对于 $1\sim n$ 的数，求有多少 $i$ 满足 $i$ 的 $k$ 进制数表示字典序排名在 $1\sim n$ 的 $k$ 进制表示中为 $i$

$t$ 组数据。

$1\le t\le10^3,1\le n\le10^{18},2\le k\le10^{18}$

题解

Sol

考虑这些数的表示形成的 trie 树，那么一个点的 dfs 时间戳就是这个点的字典序排名，一个点的 bfs 时间戳就是这个点的实际大小，我们要求的就是 dfs 时间戳等于 bfs 时间戳的点的个数

对于同一深度的两个相邻的点，考察它们的 $dfs-bfs$，容易发现 $\Delta dfs\ge 1,\Delta bfs=1$，因此 $dfs-bfs$ 是单调不降的

那么我们可以对每层进行二分，这需要我们求出任意一个点的 $dfs$，而这个可以通过不断跳父亲来 $O(\log n)$ 求出

那么整体的复杂度就是 $O(t\log^3n)$ 的

---

11. CF1870G - MEXanization [Keter] ⭐

题面

对于一个可重集 $S$，你需要重复进行如下操作：选择 $S$ 的一个非空可重子集 $T$，将 $T$ 从 $S$ 中删除，并向 $S$ 中加入 $\text{mex}(T)$，直到 $|S|=1$ 为止

给定长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，对每个 $i\in[1,n]$ 求 $S=\{a_1,a_2,\cdots,a_i\}$ 时，进行如上的操作，最后剩下的数最大是多少

$1\le n\le2\times10^5,0\le a_i\le2\times10^5$

题解

Sol

考虑对于一个序列如何求解。

不难发现如果我们能凑出 $x$，我们一定能凑出来所有 $\le x$ 的数

因此我们考虑如何判断是否能凑出 $x$，设我们要凑出 $ned_i$ 个 $i$，并且 $S$ 中有 $cnt_i$ 个 $i$，那么如果 $cnt_i<ned_i$，我们就需要将 $ned_0,ned_1,\cdots,ned_{i-1}$ 都加上 $ned_i-cnt_i$

最后除 $i=0$ 之外一定都满足 $ned_i\le cnt_i$，那么我们只需要判断 $\sum ned_i\le n$ 是否成立即可

重新整理一下这个过程，还是按 $i$ 从大到小，我们有一个变量 $p$，表示我们给这个前缀的 $ned$ 整体 $+p$，我们要求 $sm$，表示整理完 $ned$ 后所有 $ned$ 的和

如果找到了一个 $cnt_i<p$，那么我们令 $p\leftarrow p+(p-cnt_i),sm\leftarrow sm+(i-1)(p-cnt_i)$

这样我们单次是 $O(A)$ 的，考虑优化这个过程

我们每次用线段树来找到最大的 $i$ 使得 $cnt_i<p$，而每次至少让 $sm$ 加 $i-1$，因此找的次数最多为 $O(\sqrt n)$

那么我们看起来得到了一个 $O(n\sqrt n\log A)$ 的做法

实际上，可以说明这是 $O(n\sqrt n)$ 的

具体地，我们在线段树查找时，从叶子向上查找下一个小于某数的，不妨假设我们访问过的所有 $cnt_i<p$ 的 $i$ 分别为 $i_1,i_2,\cdots,i_k$，那么访问的节点数就是 $dis(i_1,i_2)+dis(i_2,i_3)+\cdots+dis(i_{k-1},i_k)$，而一个长为 $2^t$ 的节点在 $dis(a,b)$ 中会被访问当且仅当 $a,b$ 不在同一个长为 $2^{t-1}$ 的块中

而又由于访问 $i$ 会至少让 $sm$ 加上 $i-1$，所以对于任意块长 $B$，$i_1,i_2,\cdots,i_k$ 的不同块数最多为 $\sqrt{\dfrac nB}$，因此总共访问的节点数最多为 $\sum\sqrt{\dfrac n{2^t}}=O(\sqrt n)$

因此总复杂度 $O(\sqrt n)$

---

12. CTT2021 - 小明的树 [Euclid] ⭐

题面

给定一棵 $n$ 个点的树，以 $1$ 为根

给定一个 $2\sim n$ 的排列 $a_1,a_2\cdots,a_{n-1}$，他会按这个顺序依次点亮树上对应的点

有一个计数器 $T=0$，他每次点亮一个点后，如果当前所有的点满足，对于一个被点亮的点，它的子树一定也全被点亮，那么小明会将 $T$ 加上当前点亮的点的连通块数

有 $m$ 次修改，每次修改断掉一条边 $(x_1,y_1)$ 再加上一条边 $(x_2,y_2)$，保证操作后仍然是一棵树，对所有修改前以及每次修改后求如果初始 $T=0$，那么小明执行完这个过程后 $T$ 的值

$2\le n\le5\times10^5,0\le m\le5\times10^5$

题解

Sol

连通块不好处理，所以我们点-边容斥，而点和边都看起来比较好维护，只要算出来每条边被完全点亮的时刻就变成一个区间加

考虑子树点亮的限制怎么做，观察发现，由于 $1$ 不会被点亮，所以这等价于黑点形成一个连通块，那么用类似的方法维护即可，注意到黑点的连通块个数 $\ge1$，所以线段树维护区间内黑点连通块个数最小的位置的答案和即可

复杂度 $O(n\log n)$

---

13. CTT2021 - 魔塔 OL [Keter] ⭐

题面

有 $q$ 次事件，每次事件为以下三种中的一种：

• + x y z a b，表示新增了一个属性为 $(x,y,z)$ 的任务，你做这个任务会消耗 $a$ 个金币，完成任务后会获得 $b$ 个金币，该任务的编号为之前存在过的任务个数 $+1$
• - k，删除编号为 $k$ 的任务
• ? g l d，对所有满足 $x\le g,y\le l,z\le d$ 的任务 $(x,y,z)$，求初始至少要有多少金币，使得能以某种顺序完成所有这样的任务，并且任意时刻金币非负

$1\le q\le150000$，+ 与 ? 操作个数分别不超过 $50000$，$1\le x,y,z,g,l,d\le10000,0\le a,b\le10^9$

题解

Sol

不太正常。

首先，对于任意任务集合，我们完成的最优顺序是将所有 $a\le b$ 的在前，$a>b$ 的在后，$a\le b$ 内部按 $a$ 从小到大，$a>b$ 内部按 $b$ 从大到小，这个是经典结论，似乎有人叫 “打怪兽”，容易通过 Exchange Argument 证明

那么我们先按这种排序方式排序，不难发现如果我们维护经过一个集合后的 $(mn,sum)$，表示过程中最小金币数和最后金币数，这个信息是可以合并的

这个题求的是四维偏序内信息的合并，对传统数据结构来说还是有点太超前了，所以接下来介绍一些神秘魔法。

多维偏序可以对每一维，每个 $x$，用 bitset 处理出有哪些元素在这一维上 $\le x$，查询时直接 & 在一起，得到有哪些元素同时满足多维偏序，这样复杂度对于 $n$ 个元素和 $k$ 维是 $O\left(\dfrac{n^2k}\omega\right)$

但是这题还要维护信息合并，因此我们加一些小小的扩展

令 $B=log_2n$，我们排序后每 $B$ 个分一块，然后类似 bitset 一样 $B$ 个压位，那么可以在每组询问 $O\left(\dfrac nB\right)$ 的复杂度内预处理出来满足多维偏序的元素

信息合并时，我们对每个块预处理出所有 $2^B$ 种子集合并出来的信息，那么每次调用 $O\left(\dfrac nB\right)$ 个块的值即可

总复杂度 $O\left(\dfrac{n^2}{\log n}\right)$

---

14. ARC130F - Replace by Average [Euclid]

题面

给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$，每次操作你可以选定三个数 $i,j,k$ 满足 $1\le i<j<k\le n,j=\frac{i+k}2$，并执行 $a_j\leftarrow\left\lfloor\frac{a_i+a_k}2\right\rfloor$

$3\le n\le3\times10^5,1\le a_i\le10^{12}$

题解

Sol

将 $a_j$ 变大一定不会更优，因此以下假设我们每次操作只能将 $a_j$ 变小

由于我们做一次操作并没有任何损失，所以我们可以认为极优解就是最优解，即我们需要尽可能操作直到无法操作为止

那么考虑所有形如 $i-1,i,i+1$ 的操作，设 $d_i=a_i-a_{i-1}$，那么这个操作能让 $a_i$ 变小当且仅当 $d_i>d_{i+1}$

也就是说最后的序列差分是递增的，而我们可以说明只通过形如 $i-1,i,i+1$ 的操作能达到这一点，具体如下：

依次 $i-1,i,i+1$ 操作的影响为 $d_i\leftarrow\lfloor\frac{d_i+d_{i+1}}2\rfloor,d_{i+1}\leftarrow\lceil\frac{d_i+d_{i+1}}2\rceil$，接下来的操作均在差分数组上考虑

这启发我们，定义一个块为形如 $x,x,\cdots,x,x+1,x+1,\cdots,x+1$ 的连续段，那么对于两个相邻的块满足第一个块的末尾大于第二个块的开头，可以说明它们合并完仍然是一个块，并且由于操作保持和不变，所以这个块是可以求的

我们将一开始所有元素都视作一个块，然后增量用栈维护即可

复杂度 $O(n)$

---

15. ARC130E - Increasing Minimum [Keter]

题面

有一个长为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$，但你不知道是什么，我们在上面进行了 $k$ 次操作，第 $x$ 次操作如下：

任选一个 $a_c=\min(a_1,a_2,\cdots,a_n)$，令 $i_x=c$，并将 $a_c$ 加 $1$

现在给定 $n,k$，以及 $i_1,i_2,\cdots,i_k$，求字典序最小的 $a$，或判断无解

$1\le n,k\le3\times10^5$

题解

Sol

这个操作序列可以被分成若干段，每段对应着一次 $a$ 的最小值 $+1$，那么除了最后一段外，每一段必须包含之前出现过的所有数，并且不能有重复元素

观察可得对于一个右端点，合法的左端点只有一个，即最近的满足包含所有出现过的数的点

那么对于每个右端点 $i$，我们可以算出来如果它为某一个块的右端点，那么这个块为第几个块，称这个值为 $f_i$

我们只要枚举出最后一个完整段的结束位置 $s$，那么所有事情就都确定了，结论是我们选择的是满足 $[s+1,n]$ 不含重复元素，且 $f_s$ 最小，且 $f_s$ 最小的情况下尽可能靠右的元素，原因是：

• 最后一段不能包含重复元素
• $a_x$ 可以表示为 $f_s-|\{i|1\le i\le s,a_i=x\}|$，那么我们希望任意一个 $a_x$ 尽量小都是选择 $f_s$ 最小，且 $f_s$ 最小的情况下尽可能靠右的 $s$

那么模拟即可。

复杂度 $O(n\log n)$

---

16. JOISC2022 - 监狱 [Keter]

题面

给定 $n$ 个点的树，树上有 $m$ 个人，第 $i$ 个人需要从 $s_i$ 走到 $t_i$，且必须要按照最短路径

每一时刻一个人可以走一步，但你要保证任何时刻任意节点上最多有一个人

求是否可能

$1\le n\le1.2\times10^5$

题解

Sol

结论：如果有解，那么一定存在一个解使得每个人都不需要“等待”，即 $m$ 个人按照某种顺序依次移动

证明：

定义同一个人移动的某段连续时刻为一个连续段

考虑一个人移动的 $X,Y$ 两个连续段，假设 $X$ 后这个人在 $B$，那么这棵树就在 $B$​ 被切开，周围是独立的问题

我们令这个人走到 $B$ 之前在 $A$ 子树，走出 $B$ 之后在 $C$ 子树，那么我们其实只需要满足

也即 $X$ 与 $Y$ 之间的时刻，子树间的操作顺序可以任意排列，那么我们将同一子树的操作排在一起，称 $A$ 子树的连续段为 $A$ 段，$C$ 子树的连续段为 $C$ 段

我们现在想通过重排，在不破坏任何连续段的情况下，让 $X$ 和 $Y$ 相邻，而我们发现我们只需要满足 $X$ 在 $A$ 段之前，$Y$ 在 $C$ 段之后即可

那么我们将 $XACY$ 重排成 $CXYA$ 即可

不断这样调整，每个人移动的时刻会形成一个连续段，因此得证

那么现在我们只需要考虑人之间的顺序关系即可，容易发现两件事情：

• 如果路径 $s_i-t_i$ 经过 $s_j$，那么 $j$ 一定在 $i$ 之前操作

• 如果路径 $s_i-t_i$ 经过 $t_j$，那么 $i$ 一定在 $j$ 之前操作

树剖优化建图并拓扑排序即可，复杂度 $O(n\log^2n)$

upd：好像可以倍增优化建图做到 $O(n\log n)$

---

17. JOISC2022 - 复制粘贴 3 [Keter]

题面

一款文字编辑器，有两个字符串 $X,Y$，你可以通过如下三种操作来改变它们的值：

• 选定一个字符 $c$，令 $X\leftarrow X+c$，花费 $A$ 的代价
• 令 $Y\leftarrow X,X\leftarrow\varnothing$，花费 $B$ 的代价
• $X\leftarrow X+Y$，花费 $C$ 的代价

给定长为 $n$ 的字符串 $s$，初始 $X=Y=\varnothing$，求最少花费多少代价

$1\le n\le2500,1\le a,b,c\le10^9$

题解

Sol

考虑我们当前固定了一个 $Y$，凑出某个字符串 $s$ 的最小代价是什么，如果复制粘贴不优那么答案就是 $nA$，否则我们需要在 $s$ 中尽可能匹配 $Y$，不难发现这可以贪心，我们只需要找到最近一次匹配

不难发现任意时刻 $X$ 一定是 $s$ 的一个子串，因此我们区间 dp，令 $f_{l,r}$ 表示 $X\leftarrow s[l:r]$ 的最小代价，那么我们有两种转移：

• 直接加字符，也就是 $f_{l,r}\leftarrow\min(f_{l,r-1},f_{l+1,r})+A$
• 复制粘贴，由于我们有上面的转移，因此我们可以假设当前的左右端点都是粘贴出来的，可以考虑贪心匹配的过程，固定一个右端点 $r$，那么我们找到左边第一个与 $s[l:r]$ 相等且不相交的 $s[i_1:j_1]$，然后从 $s[i_1:j_1]$ 开始找到下一个与 $s[i_1:j_1]$ 不交的 $s[i_2:j_2]$，以此类推，设我们第 $k$ 次找到的为 $s[i_k:j_k]$，那么有转移式 $f_{i_k,r}\leftarrow f_{l,r}+B+(k+1)C+((r-i_k+1)-(r-l+1)(k+1))A$

转移是调和级数的，复杂度 $O(n^2\ln n)$

---

18. JOISC2022 - 一流团子师傅 [Keter]

题面

交互题。

有一个长为 $nm$ 的序列 $a$，对于每个 $i\in[1,n]$，$a$ 中恰好有 $m$ 个 $i$，你知道 $n,m$，但不知道 $a$

一次询问你可以给出 $\{1,2,\cdots,nm\}$ 的子集 $S$，交互库会返回 $1,2,\cdots,n$ 在 $\{a_i|i\in S\}$ 中出现次数的最小值

最后，你需要将 $a_i$ 分成 $m$ 个序列，满足每个序列恰好包含一次 $1,2,\cdots,n$

$n\le400,m\le25$，询问次数 $\le50000$

题解

这都不会了？？？？这都不会了？？？？这都不会了？？？？

正经做法

Sol

$4\le \log_225\le5$，所以我们可以考虑 $O(nm\log m)$

那么我们不断增量构造这 $m$ 个序列 $s_1,s_2,\cdots,s_m$，每次将 $a_i$ 插入到第一个不包含 $a_i$ 的序列中

现在需要解决的问题就是如何 $O(\log m)$ 次询问内找到第一个不包含 $a_i$ 的序列

注意到询问返回的是 $\min cnt$，那么我们询问补集，就可以得到 $\max cnt$，因此我们二分，每次查询 $s_1\cup s_2\cup\cdots\cup s_{mid}\cup\{a_i\}$ 的 $\max cnt$，如果 $\max cnt>mid$ 就说明 $s_1,s_2,\cdots,s_{mid}$ 均包含 $a_i$，那么就可以二分了

询问次数是 $O(nm\log m)$ 的

奇怪做法

Sol

直接顺着扫，我们希望一轮找出来一个序列 $S$

扫到 $i$ 时询问 $|S|\cup\{a_i\}$ 的 $\max cnt$，如果 $=1$ 就将 $a_i$ 加入序列，当 $|S|=m$ 时退出，进入下一轮

询问次数大概在 $4.3\times10^4\sim 4.7\times10^4$ 之间

---

19. JOISC2022 - 京都观光 [Keter]

题面

有一个 $n\times m$ 的有向网格图，左上角为 $(1,1)$，右下角为 $(n,m)$，有两种边：

• $(i,j)\rightarrow (i,j+1)$，连一条长为 $a_i$ 的边
• $(i,j)\rightarrow (i+1,j)$，连一条长为 $b_j$ 的边

求 $(1,1)$ 到 $(n,m)$ 的最短路

$1\le n,m\le10^5$

题解

Sol

神秘。

对于一个 $3\times 2$ 的子图考虑，设行分别为 $x<y<z$，列分别为 $l<r$，那么一共有三种决策：

• $(x,l)\rightarrow (x,r)\rightarrow (z,r)$，代价为 $(r-l)a_x+(z-x)b_r$
• $(x,l)\rightarrow(y,l)\rightarrow(y,r)\rightarrow(z,r)$，代价为 $(y-x)b_l+(r-l)a_y+(z-y)b_r$
• $(x,l)\rightarrow(z,l)\rightarrow(z,r)$，代价为 $(z-x)b_l+(r-l)a_z$

如果要用到 $a_y$，也即第二种最优，那么整理式子得 $\dfrac{a_y-a_x}{y-x}<\dfrac{b_r-b_l}{r-l}<\dfrac{a_z-a_y}{z-y}$，也就是说所有可能用到的 $a$ 都在下凸壳上，$b$ 同理

那么我们将下凸壳求出来，接下来考虑要优先走哪边

对于一个 $2\times2$ 的子图考虑，设行为 $x<z$，列为 $l<r$，那么对比以下式子可得 $(x,l)\rightarrow(z,l)\rightarrow(z,r)$ 更优当且仅当 $\dfrac{a_z-a_x}{z-x}<\dfrac{b_r-b_l}{r-l}$，而在下凸壳上这个顺序是唯一的，因此直接选即可

复杂度 $O(n)$

---

20. JOISC2022 - 错误拼写 [Euclid]

题面

对于长为 $n$ 的小写字符串 $s$，定义 $t_i$ 为 $s$ 删去第 $i$ 个字符后得到的字符串

现在有 $m$ 个限制，每个限制给定 $a,b$，表示 $t_a\le t_b$

求可能的 $s$ 数量，对 $10^9+7$ 取模

$2\le n\le5\times10^5,1\le m\le5\times10^5$

题解

Sol

如果 $as_{i+1}$

如果 $a>b$，那么限制相当于区间 $[b,a]$ 内第一个 $s_i\neq s_{i+1}$ 的位置不能满足 $s_i<s_{i+1}$

因此我们可以考虑相邻字符之间的大小关系来转移，具体地，令 $f_{i,j}$ 表示考虑完前 $i$ 个字符，$s_i=j$，且 $s_{i-1}\neq s_i$ 的方案数

转移时我们考虑下一个不等于的位置 $k$ 在哪里，那么我们只需要考虑所有左端点 $>i$ 的限制

不难发现，随着 $i$ 的增大，对于一个固定的 $k$，限制会不断变松，即先由不能转移，到只能转移大于或小于，到无限制

那么我们可以先倒着扫一遍求出来分界点 $t1_i,t2_i$，那么转移就可以前缀和优化

复杂度 $O(n|\Sigma|+n\log n)$

---

21. JOISC2022 - 团队竞技 [Euclid]

题面

有 $n$ 个人，每个人有三个属性 $a_i,b_i,c_i$

求三个人 $i,j,k$，使得 $a_i>a_j,a_k$，$b_j>b_i,b_k$，$c_k>c_i,c_j$，求 $a_i+b_j+c_k$ 的最大值

$3\le n\le1.5\times10^5$

题解

Sol

如果一个人同时是两个属性的最大值，那么这个人显然不可能出现在答案中

那么我们每次删除满足这样条件的人，直到无法再删除，那么此时 $a$ 的最大值，$b$ 的最大值，$c$ 的最大值一定互不相同，因此取这三个人即为最优

复杂度 $O(n\log n)$

---

22. ARC129E - Yet Another Minimization [Keter] ✔️

题面

你需要构造一个长为 $n$ 的序列 $x_1,x_2,\cdots,x_n$，满足 $x_i\in\{A_{i,1},A_{i,2},\cdots,A_{i,m}\}$

选择序列会有代价，具体地，令 $x_i\leftarrow A_{i,j}$ 会产生 $C_{i,j}$ 的代价

并且，对于 $1\le i<j\le n$，还会产生 $|x_i-x_j|W_{i,j}$ 的代价，其中 $W_{i,j}$ 给定

$2\le n\le50,2\le m\le5,1\le A_{i,1}<A_{i,2}<\cdots<A_{i,m}\le10^6,1\le C_{i,j}\le10^{15},1\le W_{i,j}\le10^6$

题解

题解做法

Sol

最小割。

每个数有 $m$ 种状态，这不是很好处理，因此我们采取如下的建图方式，建 $n$ 条链，$S\rightarrow A_{i,1}\rightarrow A_{i,2}\rightarrow\cdots\rightarrow A_{i,m}\rightarrow T$，割掉 $A_{i,j}$ 后的边的意义是令 $x_i\leftarrow A_{i,j}$，代价是 $C_{i,j}$

那么接下来我们需要处理的就是 $W_{i,j}$ 的贡献

考虑 $|x_i-x_j|$ 实际上是对区间 $[x_i,x_j)$ 内所有的整数 $k$ 算贡献，如果 $x_i\le k<x_j$ 或 $x_j\le k<x_i$，那么会对答案造成 $W_{i,j}$ 的贡献，由于这两个条件不交，所以我们可以都建到图里，下面以 $x_i\le k<x_j$ 为例

手模一下就可以发现，对于 $x_i$ 和 $x_j$，我们需要找到第一个满足 $A_{i,y}>k$ 的 $y$，以及最后一个满足 $A_{j,z}\le k$ 的 $z$，当 $A_{i,y}\in T$ 且 $A_{j,z+1}\in S$ 时会产生贡献，那么我们在这两个点之间建一条代价为 $W_{i,j}$ 的边，对所有 $k$ 建这样的边就可以通过最大流跑出答案

但值域太大了，我们可以合并 $y,z$ 相同的 $k$ 来降低复杂度，注意到对于一个 $x_i,x_j$ 不同的 $y,z$ 只有 $O(m)$ 种，因此最后的图有 $O(nm)$ 个点，$O(n^2m)$ 条边，总复杂度 $O(n^4m^3)$

神秘做法

Sol

最小割。

仍然采取 $S\rightarrow A_{i,1}\rightarrow A_{i,2}\rightarrow\cdots\rightarrow A_{i,m}\rightarrow T$ 的建图方式，接下来考虑如何处理 $W_{i,j}$

注意到最小割处理的实际上是 $x_i\in\{0,1\}$，求 $\sum_{1\le i<j\le n}w_{i,j}x_ix_j+\sum_{1\le i\le n}v_ix_i+C$ 的最小值，其中 $w_{i,j}\le0$

那么我们想办法往这个模型上靠，我们用变量 $x_{i,j}$ 表示 $A_{i,j}$ 是否 $\in S$

如果我们割掉了 $A_{i,p}$ 和 $A_{j,q}$ 后面的边，那么所有 $x_{i,P}x_{j,Q}(P\le p,Q\le q)$ 会造成贡献，这说明 $w_{(i,P),(j,Q)}$ 的二维前缀和是 $|A_{i,p}-A_{j,q}|$，那么我们通过一次二维差分就可以得出边权

考虑 $|A_{i,p}-A_{j,q}|-|A_{i,p-1}-A_{j,q}|-|A_{i,p}-A_{j,q-1}|+|A_{i,p-1}-A_{j,q-1}|\le0$，所以我们可以用上面的模型做这个问题

但有一个问题，就是当 $p=1$ 或 $q=1$ 时这个不等式不成立，我们发现 $S\rightarrow A_{i,1}$ 的边权是 $\infty$，那么 $x_{i,1}$ 一定为 $1$，因此我们可以将这个权值放到 $v_i$ 里（也即把 $S$ 和 $A_{i,1}$ 合并在一起），而 $v_i$ 对正负没有限制，因此我们可以建图

最后建出来的图边数不劣于任何一种建图方式？

---

23. JOISC2022 - 洒水器 [Safe]

题面

给定一棵 $n$ 个点的树，以及常数 $L$，点有点权，有 $q$ 次操作：

• 1 x d y，表示将与 $x$ 距离 $\le d$ 的点的点权乘 $y$ 模 $L$
• 2 x，查询 $x$ 的点权

$2\le n\le2\times10^5,2\le L\le10^9,1\le q\le4\times10^5,0\le d\le40$

题解

Sol

典。

考虑 $d$ 非常小，那么我们可以考虑打 tag，每个点打 $tag_{u,i}$ 表示 $u$ 深度为 $i$ 的子孙集体乘上了 $tag_{u,i}$

修改和查询都直接暴力跳祖先即可，复杂度 $O(nd)$

---

24. JOISC2022 - 鱼 2 [Keter] ✔️

题面

有 $n$ 条鱼，第 $i$ 条鱼的大小为 $a_i$

当我们打开开关时，大的鱼会吃掉小的鱼，具体地，对相邻的两条大小为 $x,y$ 的鱼，如果 $x\ge y$，那么 $x$ 可能吃掉 $y$，大小变为 $x+y$，如果 $y\le x$，那么 $y$ 可能吃掉 $x$，大小变为 $x+y$。特别地，如果 $x=y$，两件事情均有可能发生

$q$ 次操作，每次操作为以下两种中的一种：

• 1 x y，将 $a_x$ 修改为 $y$
• 2 l r，查询如果只保留 $[l,r]$ 内的鱼，打开开关，并等待到只剩一条鱼为止，那么会有多少鱼可能成为最后一条鱼

$1\le n,q\le10^5,1\le a_i,y\le10^9$

题解

Sol

考虑对整个序列如何求答案：

我们可以找到所有满足 $\sum_{i=l}^ra_i<\min(a_{i-1},a_{i+1})$ 的区间，这样一个鱼可能成为最后的鱼当且仅当没有任意一个区间包含它

注意到包含一个点的区间只有 $O(\log V)$ 个，那么我们只要能够快速求出包含一个点的所有区间，我们就可以干很多事情了

考虑怎么求包含 $x$ 的所有区间，我们从 $[x,x]$ 开始不断扩展：

• 如果当前不满足 $sum<a_{l-1}$ 或 $sum<a_{r+1}$，那么我们从不满足的那一边开始扩展，不妨设为 $r$，那么假设新的右端点为 $r^\prime$，就需要满足 $sum_{r^\prime}-sum_{l-1}<a_{r^\prime+1}$，这可以用线段树上二分解决，找到 $r$ 后面第一个满足条件的 $r^\prime$
• 如果当前满足 $sum<\min(a_{l-1},a_{r+1})$，那么我们加入包含 $[x,x]$ 的区间，并从 $a_{l-1}$ 与 $a_{r+1}$ 中较小的一边扩展，可以说明这样能统计到所有包含的

那么求解包含一个为止的所有区间是 $O(\log n\log V)$ 的

有了这个，我们就可以做修改了，直接把包含 $x-1,x,x+1$ 的区间全部删掉，然后修改之后再加进去就可以了

考虑如何处理区间询问：

这相当于将 $a_{l-1},a_{r+1}$ 赋值为 $\infty$，然后查询 $[l,r]$ 内有多少鱼恰好被一个区间包含

但是这样写会被卡常，我们进行一些观察，这个操作实际上相当于删除所有经过 $l-1$ 和 $r+1$ 的区间，并且加入一个 $r^\primel$且$l^\prime$最小的右端点为$r$的区间$[l^\prime,r]$

总复杂度 $O(n\log n\log V)$

---

25. JOISC2021 - Food Court [Safe]

题面

有 $n$ 个队列，元素值域始终在 $[1,m]$ 内，$q$ 次操作，每种操作为以下三种中的一种：

• 1 l r c k，表示对 $[l,r]$ 内所有队列分别插入 $k$ 个 $c$
• 2 l r k，表示对 $[l,r]$ 内所有队列分别删除队首的 $k$ 个元素，如果不足 $k$ 个则将队列清空
• 3 a b，询问第 $a$ 个队列从队首开始第 $b$ 个元素的值，不存在则输出 $0$

$1\le n,m,q\le2.5\times10^5$

题解

Sol

考虑询问是只对一个队列进行的，因此我们可以对队列做扫描线，然后用数据结构维护时间轴

对于一组询问 $(t,a,b)$，其中 $t$ 为时间，假设我们现在扫描线到了 $b$

如果我们没有发生 “不足 $k$ 个并将队列清空” 的事件，那么是好做的，我们查询一下前面删除了多少个数，再 $+b$，那么就得到了我们查询的元素在所有元素中的排名，而这个线段树上二分一下即可

考虑上一次发生 “不足 $k$ 个并将队列清空” 的事件，注意到如果我们将加入 $k$ 个人视为 $+k$，删除 $k$ 个人视为 $-k$，那么这个就是前缀中最小前缀和的位置 $id$，因此这个是可以查询的

那么我们直接在 $[id+1,t]$ 上运行刚才的算法即可

复杂度 $O(n\log n)$

---

26. JOISC2021 - Road Construction [Euclid]

题面

给定 $n$ 个点，求曼哈顿距离前 $k$ 小的点对的距离

$2\le n\le2.5\times10^5,1\le k\le\min(\frac12n(n-1),2.5\times10^5),|x_i|,|y_i|\le10^9$

题解

正常做法

Sol

考虑二分，求距离 $\le M$ 的点对有多少

考虑曼哈顿距离是 $\Delta x+\Delta y$，而这个 $+$ 不是很好处理，我们可以考虑转化成切比雪夫距离，也即 $\max(\Delta x,\Delta y)$

那么我们可以用一个类似于滑动窗口的方式，先按 $x_i$ 排序，顺着枚举点对中 $x$ 较大的元素 $x_i$，并且时刻将 $x_j<x_i-M$ 的点删除，那么我们只需要支持查询当前范围内有多少点满足 $y_j\in[y_i-M,y_i+M]$ 即可，这是容易用数据结构实现的

复杂度 $O(n\log n\log V)$

高明做法

Sol

考虑二分，求距离 $\le M$ 的点对有多少，依然转成切比雪夫距离

将整个平面分成 $M\times M$ 的块，那么与 $(x_i,y_i)$ 距离 $\le M$ 的点一定在周围的 $3\times3$ 的块内

那么我们依次加入每个点，直接暴力枚举统计对数，发现合法对数 $\ge k$ 直接跳出

考虑分析这样做的复杂度：

考虑我们最后一次合法对数 $<k$ 时的局面，接下来一次操作复杂度最多 $O(n)$，因此我们只需分析这之前的复杂度

对于一个块 $A$，设其中包含的点数为 $p_A$，那么首先它会 $\frac12p_A(p_A-1)$ 个合法对，并产生 $O(p_A^2)$ 的复杂度，因此这部分的复杂度是不超过 $O(k)$ 的

对于两个相邻块 $A,B$，最坏情况下它们一个合法对也不会贡献，但是会贡献 $p_Ap_B$ 的复杂度，但考虑 $\frac12 p_A^2+\frac12p_B^2\ge p_Ap_B$，所以这部分的复杂度小于等于上面的复杂度 $\times O(1)$，因此也是 $O(k)$ 的

那么一轮 check 的复杂度就是 $O(k)$ 的，因此总复杂度是 $O(k\log V)$ 的

奇怪做法（Flamire 做法）

Sol

考虑求前 $k$ 小的一个方法是求出一些偏序关系，然后用堆维护这个偏序关系图上的拓扑排序

那么我们就需要建立一些这样的偏序关系，考虑按 $x$ 排序并分治，一层内我们按 $y$ 排序

由于曼哈顿距离的表达式为 $|x_i-x_j|+|y_i-y_j|$，所以对于 $x_i>mid$ 的点，所有 $y$ 小于它的点 $j$，距离为 $x_i+y_i-x_j-y_j$，那么对于同一个 $i$，距离的偏序关系就是 $-x_j-y_j$ 上的偏序关系，对于 $y$ 大于它的点同理

那么我们就得到了总共 $O(n\log n)$ 条链，但是我们还需要快速找到一条链上的下一个点，而我们的链不断在插入元素，因此这不是很好处理

考虑我们只有插入一个元素和求某个元素在某一时刻的后继的操作，而这相当于“可持久化链表”，具体地，对于每一个点，我们维护它的后继所有的变化时刻，那么就可以做到 $O(1)$ 修改，$O(\log)$ 查询

得到这 $O(n\log n)$ 条链后，我们放入堆中，然后每次查询一个点的后继即可

复杂度 $O(n\log^2n+k\log n)$

---

27. CF1874D - Jellyfish and Miku [Euclid]

题面

有一条 $n+1$ 个点的链，点分别编号为 $0,1,2,\cdots,n$，$i$ 与 $i-1$ 之间的边权值为 $a_i$

你在这条链上游走，初始在 $0$，接下来对于每一时刻，设你所在点出边权值之和为 $s$，对于你所在点的任意一条出边，若其权值为 $x$，那么你有 $\frac xs$ 的概率会沿着这条出边走出去

现在给定 $n,m$，你需要决策一个 $a_1,a_2,\cdots,a_n$，使得每个 $a_i$ 都是正整数且 $\sum a_i\le m$，在此前提下，你希望从 $0$ 到 $n$ 的期望步数尽量小，求出这个最小步数

$1\le n\le m\le3000$

题解

Sol

考虑对于固定的 $a$ 如何求答案，我们令 $f_i$ 表示从 $i$ 出发到达 $n$ 的期望步数，那么通过一些推式子，我们可以得到：

令 $d_i=f_i-f_{i-1}$，那么有 $a_{i+1}d_i=a_{i}d_{i-1}+a_i+a_{i+1}$，而我们要求的是 $\sum d_i$，展开一下可以得到：

$$f_0=n+\sum_{2\le i\le n}\frac{1+a_1}{a_i}+2\sum_{2\le i<j\le n}\frac{a_i}{a_j}$$

注意到最优解一定满足 $a_1=1$，所以我们可以改写成：

$$f_0=n+2\sum_{1\le i<j\le n}\frac{a_i}{a_j}$$

那么不难列出 dp 方程，令 $dp_{i,j}$ 表示前 $i$ 个 $a_i$，和为 $j$，$f_0$ 的最小值，转移就是 $dp_{i-1,k}+\frac{2j}{j-k}\rightarrow dp_{i,j}$

这个有两种优化方式：

• 通过一些手段，注意到这个 dp 在 $j$ 上是有决策单调性的，直接套二分栈优化
• 观察到最优解一定满足 $a_i\le a_{i+1}$，因此可得 $a_i\le\frac{m}{n-i+1}$，暴力枚举 $a_i$ 的决策，复杂度是调和级数的

因此总复杂度 $O(n^2\log n)$

---

28. CF1874E - Jellyfish and Hack [Keter]

题面

function fun(A)
    if A.length > 0
        let L[1 ... L.length] and R[1 ... R.length] be new arrays
        L.length = R.length = 0
        for i = 2 to A.length
            if A[i] < A[1]
                L.length = L.length + 1
                L[L.length] = A[i]
            else
                R.length = R.length + 1
                R[R.length] = A[i]
        return A.length + fun(L) + fun(R)
    else
        return 0

求有多少 $A$ 满足 $A$ 是 $[1,2,\cdots,n]$ 的排列且 $\text{fun}(A)\ge lim$，对 $10^9+7$ 取模

$1\le n\le200,1\le lim\le10^9$

题解

Sol

定义 $dp_{i,j}$ 表示长为 $i$ 的排列，$\text{fun}(A)=j$ 的方案数，那么有转移式：

$$dp_{i,j}=\sum_{x=0}^{i-1}\sum_{y=0}^{j-i}dp_{x,y}dp_{i-1-x,j-i-y}\binom{i-1}{x-1}$$

直接做是 $O(n^6)$ 的，考虑优化。

$lim$ 非常大，可以考虑一些插值做法，但我们发现系数是 $O(n^2)$ 次的多项式，因此不能对系数插值

考虑这个转移非常像卷积，如果我们写出 $dp_i$ 的生成函数 $F_i$，可以得到：

$$F_i=x^i\sum_{x=0}^{i-1}F_xF_{i-1-x}\binom{i-1}{x-1}$$

而 $F_n$ 是一个 $O(n^2)$ 次的多项式，因此我们可以求出 $F_n$ 的 $O(n^2)$ 个点值，然后通过拉格朗日插值插出 $F_n$ 的所有系数，这样复杂度就是 $O(n^4)$ 的了。

notes：拉插插系数

考虑拉插的式子：

$$f(x)=\sum_{i=0}^ny_i\frac{\prod_{i\neq j}(x-x_j)}{\prod_{i\neq j}(x_i-x_j)}$$

那么我们直接对这个式子展开，就可以求出 $f$ 的每一项系数，如果我们令 $coe_i=\dfrac{y_i}{\prod_{i\neq j}(x_i-x_j)}$，就相当于我们必须选一个 $i$ 乘上 $coe_i$，否则我们可以选择乘上 $x$ 或 $-x_j$，那么做一个 $O(n^2)$ 的背包即可

---

29. JOISC2021 - Bodyguard [Euclid]

题面

有 $n$ 个 VIP 在数轴上走动，第 $i$ 个 VIP 会在 $t_i$ 时刻出现于 $a_i$，并以 $1$ 的速度向 $b_i$ 运动，到达 $b_i$ 后它会立刻消失

你是一名保镖，任意时候，你都可以选择跟着某个 VIP 一起走，对它进行保护，如果你保护 $i$ 号 VIP 行走 $d$ 的距离，你会得到 $d\times c_i$ 的收益（保证 $c_i$ 为偶数）

你可以任意时刻选择开始保护或结束保护一名 VIP，但你只能保护和你处于同一坐标的 VIP，并且同一时刻你只能保护一名 VIP，你的最大速度为 $1$

现在有 $q$ 次询问，每次询问给定 $p,x$，表示如果你在 $p$ 时刻出现于位置 $x$，你能获得的收益最多为多少

$1\le n\le2800,1\le q\le3\times10^6,1\le t_i,a_i,b_i,c_i,p,x\le10^9$

题解

Sol

可以发现，一定存在方案使得我们每一时刻都在以 $1$ 的速度运动

那么我们以 $t$ 为横坐标，位置为纵坐标，那么我们每步可以走 $(+1,-1)$ 或 $(+1,+1)$，而每个 VIP 是斜率为 $\pm1$ 的线段

旋转一下，那么我们每步可以走 $(0,+1)$ 或 $(+1,0)$，而每个 VIP 是横着或竖着的线段，在线段上走 $d$ 的距离会获得 $d\times c_i$ 的收益

那么首先可以将线段端点的 $x,y$ 坐标分别离散化一下得到 $[X_1,X_2,\cdots,X_m],[Y_1,Y_2,\cdots,Y_k]$，然后 $O(n^2)$ 的时间求出从每个离散化坐标能获得的最大收益 $dis_{X_i,Y_j}$

那么对于一个旋转后的询问的点 $(x_i,y_i)$，我们找到它右上角第一个离散化考虑过的点 $(X_a,Y_b)$，如果最优解在 $x_i\le x<X_a\cup y_i\le y<Y_b$ 的位置内没有产生收益，那么答案就是 $dis_{X_a,Y_b}$，需要考虑的就是在 $x_i\le x<X_a\cup y_i\le y<Y_b$ 内产生的贡献

考虑所有 $x=x_i$ 经过的且在 $y=y_i$ 及以上的横线，如果在 $x_i\le x<X_a$ 部分产生贡献，那么一定恰好经过其中的一条横线，因为所有经过的横线一定满足完全包含 $[X_{a-1},X_a]$，设 $c_k$ 为 $y=k$ 的横线收益，那么选择 $y=k$ 的横线的收益就为 $(X_a-x)c_k+dp_{X_a,k}$，这个可以看成一个关于 $x$ 的一次函数，由于没有比较好的单调性，所以我们用李超树维护，复杂度 $O((n^2+q)\log n)$

但是如果我们将其看成关于 $X_a-x$ 的一次函数，那么在 $y$ 变小时，$dp_{X_a,k}$ 逐渐增大，因此可以二分凸包，那么复杂度就是 $O(n^2+q\log n)$

---

30. JOISC2021 - Meetings 2 [Euclid]

题面

给定一棵 $n$ 个点的树，我们现在选择一个 $P\subseteq\{1,2,\cdots,n\}$，定义 $S$ 如下：

• 对于一个点 $x$，$x\in S$ 当且仅当 $\sum_{p\in P}dis(x,p)$ 在所有 $x$ 中最小

对于每个 $k=1,2,\cdots,n$，求当 $|P|=k$ 时 $|S|$ 的最大值

$1\le n\le2\times10^5$

题解

Sol

题解区一车虚树/点分治。神秘。

容易注意到 $S$ 就是 $P$ 中的所有点的带权重心的集合，那么当 $|P|$ 为奇数时答案显然为 $1$

那么对于每个 $|P|=k$，相当于我们需要选择两个点 $u,v$，使得 $u$ 以 $v$ 为根时子树大小 $\ge\frac12k$，且 $v$ 以 $u$ 为根时子树大小 $\ge\frac12k$

那么我们以 $1$ 为根分两种情况讨论，一种是 $u$ 与 $v$ 有祖孙关系，一种是 $u$ 与 $v$ 没有祖孙关系

接下来的两种做法都以这个分类讨论为前提。

Flamire 做法

Sol

无祖孙关系：

相当于我们需要选出两个无祖孙关系的 $u,v$，满足 $siz_u\ge\frac12k,siz_v\ge\frac12k$，且 $dis(u,v)$ 最大

一个初步想法是 $k$ 从大到小枚举，将所有 $siz\ge\frac12k$ 的点的集合 $T$ 拿出来求直径，但是这样会出现 $u,v$ 互为祖孙关系的情况

那么我们需要进行一些修正，考虑这样一种做法：每次加入 $x$ 时，将 $fa_x$ 删除，对得到的集合求直径，如果我们能做到这件事情，那么求出来的答案一定是正确的

但大部分情况下，如果 $x$ 已经被加入集合，$fa_x$ 就不会产生贡献了，观察可得不满足这个的情况只有当我们加入的点组成一条到根链时，而这个是好判的

那么最后我们的算法就是：每次加入所有 $siz=\frac12k$ 的点 $u$，如果 $fa_u$ 标记在集合中，就将它删去，并标记 $u$ 为在集合中，那么集合中的点组成到根链当且仅当恰有一个点被标记在集合中，那么时刻维护这个集合的直径即可

这部分复杂度 $O(n\log n)$

有祖孙关系：

不妨设 $v$ 为祖先，那么需要满足 $siz_u\ge\frac12k$，且 $v$ 以 $u$ 为根时的子树大小 $\ge\frac12k$

我们还是依次加入所有 $u$，时刻保证所有 $siz_u\ge\frac12k$ 的点都被加入

如果 $v$ 到根的路径经过至少一条轻边，那么一定有 $n-siz_v\ge siz_u$，也就是说这种情况我们找到最浅的 $v$ 即可，这是好做的

那么考虑 $v$ 到根的路径不经过任何轻边的情况，那么这就说明 $v$ 在 $1$ 的重链上，那么注意到对于每个 $k$，满足 $n-siz_v\ge\frac12k$ 的是一段这条链的连续“后缀”，如果我们把每一个新加入的 $u$ 看成在其所属的链上的点上加入一个点，那么我们对于每个 $k$ 只需要进行一次后缀查询最大 $dep_u$，这个是容易用树状数组或桶维护的

这部分复杂度 $O(n\log n)$ 或 $O(n)$

题解做法

Sol

无祖孙关系：

考虑把 $dis(u,v)$ 拆成 $dep_u+dep_v-2dep_{lca}$，我们用欧拉序转化，那么相当于有一个序列 $a$，我们需要找到 $i<j<k$ 使得 $a_i-2a_j+a_k$ 最大，我们需要支持依次插入 $siz_u\ge\frac12k$ 的 $u$，这个容易用线段树维护，复杂度 $O(n\log n)$

有祖孙关系：

把 $dis(u,v)$ 拆成 $dep_u-dep_v$，那么对于每个 $u$ 只需要考虑其祖先里的 $v$，那么我们依次插入 $siz_u\ge\frac12k$ 的 $u$ 和 $n-siz_v\ge\frac12k$ 的 $v$，这个也容易用线段树维护，复杂度 $O(n\log n)$

---

31. JOISC2023 - Event Hopping 2 [Safe]

题面

有 $n$ 个区间 $[l_i,r_i]$，给出整数 $k$，你需要选择下标序列 $i_1,i_2,\cdots,i_k$ 使得 $\forall1\le j<k,r_j\le l_{j+1}$，并且在所有满足条件的序列中，将 $i$ 排序后得到的字典序最小

求将 $i$ 排序后的结果，或输出无解

$1\le n\le10^5$

题解

Sol

一个显然的贪心是每次选择右端点最小的不会冲突的区间

求字典序我们只需要判断加入 $x$ 后是否还合法，这相当于我们把原来一个空段拆成两个空段，那么我们维护倍增数组就可以计算一个空段的答案是多少，也就可以判断了

复杂度 $O(n\log n)$

---

32. JOISC2023 - Worst Reporter 4 [Safe]

题面

给定 $n$ 个人，第 $i$ 个人的 rating 是 $h_i$

给定长为 $n$ 的数组 $a$ 与 $c$，你现在需要修改一些 $h$，使得对于任意 $i$，$h_i\ge h_{a_i}$ 均成立，你可以花费 $c_i$ 的代价将 $h_i$ 修改为任何数

求最小代价

$2\le n\le2\times10^5$

题解

Sol

如果图是一张链，那么这个问题就是最大权上升子序列，可以数据结构优化 dp 来维护

那么现在变成树的情况，我们也采用 dp 的数组，那么我们现在需要进行的操作就有：查询单点值，将某个前缀对 $x$ 取 max，将两个序列对位相加合并

这可以用平衡树维护连续段来做，合并的时候采用启发式合并

最后环上直接枚举选哪一个值作为这个环上的相等值即可

总复杂度 $O(n\log^2n)$

据说存在线段树合并做法，复杂度是 $O(n\log n)$ 的，但是我不会

---

33. JOISC2023 - Escape Route [Keter] ✔️

题面

给定 $n$ 个点 $m$ 条边的无向图，每条边有两个属性 $l,c$，表示通过这条边需要 $l$ 的时间，以及你开始通过这条边的时刻 $t$ 必须满足 $0\le t\bmod s\le c-l$，其中 $s$ 为给定常数

$q$ 次询问，每次给定 $u,v,t$，求如果你 $t$ 时刻从 $u$ 出发，最少花多长时间能到达 $v$（你可以选择在某个点保持不动以等待边的可通行时间）

$2\le n\le90,n-1\le m\le\frac12n(n-1),2\le s\le10^{15},1\le q\le3\times10^6,0\le t_i<s$

题解

Sol

考虑 $u$ 到 $v$ 的最短路，我们找到第一次跨过 $\bmod s=0$ 的时刻的边 $x\rightarrow y$，那么我们一定是在 $x$ 等待到下一个 $t\bmod s=0$ 的时刻出发，而这就变成了一个从 $0$ 时刻开始 $x$ 到 $v$ 的最短路问题，我们可以轻松地通过 Dijkstra 对所有 $x,v$ 预处理出这个值，我们称之为 $dis_{x,v}$，那么我们只需要保证 $x$ 是第一次等待的位置即可

注意到由于我们在满足条件下离开 $x$ 的时间一定是 $t$ 后下一个 $\bmod s=0$ 的时刻 $t^\prime$，也就是说我们只需要判断 $t$ 时刻从 $u$ 出发是否能在 $t^\prime$ 时刻及之前到达 $x$，我们也可以通过 Dijkstra 对所有 $x,u$ 预处理出一个值 $tim_{x,u}$，表示最大的 $p$ 使得在 $t\bmod s=p$ 的时刻从 $u$ 出发，能在下一个 $\bmod s=0$ 的时刻及之前到达 $x$，那么我们只需要判断一下 $tim_{x,u}$ 与 $t$ 的大小关系即可

对每次询问，枚举 $x$，可以做到单次询问 $O(n)$ 的复杂度

但是还有一种情况，就是我们没有跨过 $\bmod s=0$ 的时刻，也即 $x,y$ 不存在，这种情况比较复杂

首先，如果 $tim_{v,u}\ge t$，说明一定存在这一类路径，而这一类已经一定是优于跨过 $\bmod s=0$ 的时刻的，因此我们只需要求最短的这一类路径即可

定义一条路线为 $(t,P)$，其中 $t$ 为出发的时刻，$P$ 为一条 $u\rightarrow v$ 的路径，容易发现，对于每个 $P$，存在一个时刻 $T$ 使得路线 $(1,P),(2,P),\cdots,(T,P)$ 均可行，而路线 $(T+1,P),(T+2,P),\cdots,(s-1,P)$ 均不可行，我们称满足这样条件的 $(T,P)$ 为临界路线

显然，一条临界路线上一定有边 $e:x\rightarrow y$ 满足到达 $x$ 的时刻为 $c_e-l_e$，反过来，如果我们能枚举所有 $e$，然后求出到达 $x$ 时刻为 $c_e-l_e$ 的 $u\rightarrow v$ 的长度最短的临界路线，那么任意一个 $u,v$ 询问的路径一定是某个求出的临界路线的 $P$，也就意味着我们把所有 $t\le T$ 的临界路线 $(T,P)$ 的长度取一个 min 即可，这个可以排序+二分处理

而对于一个 $e,u,v$，求解最优的临界路线是叫容易的，我们只需要用 Dijkstra 对每个点 $u$ 到达 $x$ 的时刻在 $c_e-l_e$ 之前的最晚出发时间 $sdis_{x,u}$，以及从时刻 $c_e$ 的 $y$ 到达每个点 $v$ 的最短时间 $tdis_{y,v}$ 即可

那么我们只有 $O(m)$ 次 Dijkstra，因此 Dijkstra 的总复杂度是 $O(n^2m)$，而这种情况下回答询问是 $O(\log m)$ 的

但有一个问题，我们求出临界路线后需要按出发时刻排序，这样才可以二分，于是我们复杂度又变成了 $O(n^2m\log m)$，无法通过

考虑排序只需要按照 $sdis_{x,u}$ 排序，和 $v$ 没有关系，因此我们可以在 $v$ 的循环外面预处理好，这样排序的复杂度就是 $O(nm\log m)$ 的了，那么总复杂度就是 $O(n^2m+q(n+\log m))$，可以通过

---