task7

[TOC]

1. JOISC2021 - IOI 热病 [E]

题面

有 $n$ 个人，$0$ 时刻第 $i$ 个人在 $(x_i,y_i)$，每个人会选择一个上下左右中的一个方向，并沿这个方向一直以 $1$ 的速度运动

$0$ 时刻，第 $1$ 个人感染了 IOI 热病，接下来的任意时刻，如果有两个人处于同一坐标，且存在一个人感染了 IOI 热病，那么另一个人也会被感染，并且不存在被感染的人治愈的情况

求最后最多有多少人被感染

$1\le n\le10^5,1\le x_i,y_i\le5\times10^8$，$(x_i,y_i)$ 互不相同

题解

Sol

当确定第一个人 S 向上后，讨论一下就可以发现其他人的方向都是确定的，因此我们现在要解决的就是给定所有人的方向，求感染人数，将这个旋转做 4 遍就可以得到原题答案

考虑这是一个最短路的过程，我们需要求出每个人最早被感染的时刻

考察从 $P$ 出发的转移的形态（以 $P$ 向上为例），那么会涉及经过 $P$ 的斜率为 $-1,\infty,1$ 的直线的某个前缀/后缀，且对于每种斜率都有一个固定的方向

直接用线段树维护是非常愚蠢的，所以我们考虑如下做法：

Dijkstra 每次只需要求出距离最小值，而我们从 $P$ 向外转移时，可能成为次近点的只有可能是每条直线上最近的点，那么我们可以只插入这三个点，并且弹出一个点时将下一个点加入

具体地，我们 Dijkstra 的堆中每个点是一个四元组 $(v,dis,k,0/1)$，表示点 $v$，更新的距离为 $dis$，并且下一个次近点的方向的斜率是 $k$，$0/1$ 表示我们下一个次近点在正方向还是负方向

那么我们每个点只会加入 $O(1)$ 个新点，总复杂度 $O(n\log n)$，但是常数巨大（说不定是我写丑了）

非常难写。

2. JOISC2021 - 建筑装饰 4 [E]

题面

给定长为 $2n$ 的序列 $a,b$，对于每个 $i$，你需要在 $a_i$ 与 $b_i$ 中选择恰好一个，使得你最后选出来的序列递增，且恰好选了 $n$ 个 $a$，$n$ 个 $b$

给出构造或判断无解

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

题解

Sol

一种决策用包含 A 与 B 的字符串表示

结论：对于任意一个数列，所有可构造的 A 的个数组成一个区间

证明：

我们证明，如果存在两种决策 $s,t$，那么 A 的个数在 $s$ 与 $t$ 的 A 的个数之间的都是可构造的

首先，如果 $s$ 与 $t$ 有相同选择 $s_i=t_i$，那么我们可以从 $i$ 分成左右两部分，归纳说明

那么我们现在只需要说明 $s,t$ 没有相同选择的情况，称 $s$ 中的决策为 C，$t$ 中的决策为 D

我们说明如下事情：我们可以每次改变 $s$ 中的一个选择，将 $s$ 变为 $t$，且经过的所有决策均为合法决策，容易发现这与原命题等价

考虑将 $s_1$ 替换为 D，不合法的条件是 $D_1>C_2$

在此条件下，我们尝试将 $s_2$ 替换为 D，不合法的条件是 $D_2C_3$，但由于 $D_1C_3$

由此可得对任意 $i$，$D_iC_n$，那么可以将 $s_n$ 替换为 D

因此得证。

那么有了这个，我们直接转移每个前缀最少/最多用几个 A 即可，复杂度 $O(n)$

3. JOISC2021 - 汉堡肉 [K] ✔️

题面

给定 $n$ 个二维平面上的矩形，你需要给出一个可重点集 $S$ 满足 $|S|=k$ 且每个矩形至少包含一个 $S$ 中的点

$1\le n\le2\times10^5,1\le k\le4$

题解

Sol

考虑最左的右边界 $r_\min$，如果一个点在 $r_\min$ 左边，那么一定调整到 $r_\min$ 上一定不劣，而至少有一个点在 $r_\min$ 上，否则会有矩形无法被覆盖，类似地求出 $l_\max,u_\min,d_\min$

对于 $k\le 3$，四条直线上都至少有一个点，所以一定有一个点在交点上，那么枚举这个交点是哪一个，就可以转化为 $k-1$ 的问题，那么复杂度就是 $O(4^kn)$

对于 $k=4$，我们需要处理的情况就是四个点分别在四条直线上，考虑每个矩形：

经过了 $\ge3$ 条直线，那么一定完全经过某条直线，可以直接忽略
经过了 $0$ 条直线，说明这种情况不合法
经过了 $1$ 条直线，限制这条直线上的点一定选在 $[l,r]$ 范围内
经过了 $2$ 条直线，说明这两条直线的 $[l_1,r_1]$ 和 $[l_2,r_2]$ 内至少有一个点

这可以用一个 2-sat 模型来处理，前缀和优化可以做到边数 $O(n)$

总复杂度是 $O(n\log n+4^kn)$

4. JOISC2020 - 扫除 [K] ✨

题面

有一个顶点为 $(0,0),(n,0),(0,n)$ 的等腰直角三角形，这个三角形里有 $m$ 个点，$q$ 次操作，每次操作为以下四种中的一种：

1 p，询问第 $p$ 个点的坐标
2 l，将所有点 $(x,y)(x\le n-l,y\le l)$ 移动到 $(n-l,y)$
3 l，将所有点 $(x,y)(x\le l,y\le n-l)$ 移动到 $(x,n-l)$
4 x y，加入一个新点 $(x,y)$

$1\le n\le10^9,1\le m\le5\times10^5,1\le q\le10^6$

10s，1GB

题解

Sol

抽象数据结构。

题解区一堆看不懂的做法。

首先，我们把点 $(x,y)$ 转化为区间 $[x,n-y]$，那么这样每次操作就是对于所有包含 $x$ 的区间，将其左端点或右端点设为 $x$

考虑分治，处理区间 $[l,r]$ 时，我们考虑所有区间 $[l,r]$ 内部涉及的所有区间和操作，我们现在想模拟所有操作，使得每个区间要么被分在 $[l,m]$，要么被分在 $[m+1,r]$，要么在本层处理

我们按时间顺序考虑所有操作：

1 操作，我们判断一下询问的这个点是否已经进入了 $[l,m]$ 或 $[m+1,r]$，否则就回答当前这个点的坐标
2 操作（将 $l$ 取 $\max$ 的操作），如果操作的参数 $p>m$，那么我们需要取出 $r$ 最大的若干个点，将它们放入右儿子，并且这个操作也会影响右儿子，如果操作的参数 $p\le m$，那么我们需要取出 $l$ 最小的若干个点，并修改它们的 $l$，然后为保证复杂度，将它们的 $l$ 作为同一个等价类，这里的操作也会影响左儿子，需要进行下放，3 操作同理
这需要我们能够取出 $l$ 最小的点和 $r$ 最大的点，可以用堆 + 并查集维护（注意到我们需要能够求出一个等价类中的所有点，因此这个并查集）
4 操作，如果这个点不经过 $m$，我们可以直接放入对应的儿子，否则加入我们的堆 + 并查集结构

这样我们每个操作只会进入一个儿子，因此一层的复杂度是 $O((m+q)\log(m+q))$，那么总复杂度就是 $O((m+q)\log(m+q)\log n)$

5. JOISC2020 - 变色龙之恋 [E] ⭐

题面

有 $2n$ 只变色龙，$n$ 只性别为 X，$n$ 只性别为 Y，每只变色龙都与恰好一只异性变色龙原色相同，同性变色龙原色两两不同

每只变色龙都恰好喜欢一只异性变色龙，保证一只变色龙和它喜欢的变色龙颜色不同，每只变色龙只被恰好一只异性变色龙喜欢，喜欢关系不一定是双向的

你可以进行询问，每次询问你需要选择一个变色龙的子集 $S$，对于 $s\in S$，如果 $s$ 喜欢 $t$，那么它的颜色会如下变化：

如果 $t\in S$，那么 $s$ 的颜色为 $t$ 的原色
如果 $t\notin S$，那么 $s$ 的颜色为 $s$ 的原色

你会得到 $S$ 内的变色龙颜色种类数

请在 $20000$ 次操作内求出每只变色龙与哪只变色龙的原色相同

$1\le n\le500$

题解

Sol

首先，双向喜欢关系并没有任何用处，因此可以忽略掉

那么首先考虑询问每对变色龙，如果颜色数为 $1$，那么说明这两只变色龙颜色相同或者有喜欢关系，否则没有

由此可以得到一张二分图，每个点度数为 $1$ 或 $3$，如果一个点 $s$ 度数为 $1$ 说明 $s$ 属于某个双向喜欢关系，因此它与它连边的点颜色相同，如果度数为 $3$，设其连边的点为 $a,b,c$，那么 $(s,a,b)$ 颜色数为 $1$ 当且仅当 $s$ 喜欢 $c$，那么我们可以在 $2$ 次询问内找出 $s$ 喜欢的点，将所有关系建出来后就可以排除得出与 $s$ 颜色相同的点

现在我们算法的瓶颈在于快速建出这张二分图。

如果我们知道这张二分图的左部点集合，那么我们每次取左部点 $x$，以及一个右部点点集 $S$，询问 $x\cup S$ 可以得到 $x$ 与 $S$ 内所有点是否有连边，那么就可以在右部点上二分得到所有的边

考虑不知道二分图的左部点集合的情况，我们发现上面的算法只要求 $S$ 内部没有连边，也就是我们需要能够将图划分为两个独立集

那么我们每次加入一个点 $i$，动态维护两个独立集 $L,R$，加入 $i$ 时二分出 $L$ 与 $R$ 的每条连边，然后再对这个图跑黑白染色得到新的 $L,R$

询问次数是 $O(n\log n)$

6. JOISC2020 - 有趣的 Joitter 交友 [S]

题面

对于一个有向图 $G$，按如下方式定义 $f(G)$：

如果存在互不相同的三个点 $x,y,z$，使得 $x\rightarrow y,y\rightarrow z,z\rightarrow y$ 均有直接连边，且 $x\rightarrow z$ 无连边，加入 $x\rightarrow z$ 这条边
当无法再操作时，边的条数就为 $f(G)$

现在有一张 $n$ 个点 $0$ 条边，$m$ 次加边操作，每次加入一条边 $u\rightarrow v$ 并求此时的 $f(G)$

$2\le n\le10^5,1\le m\le3\times10^5$，保证无重边

题解

Sol

注意到如果有两个点之间有双向边，那我们可以将它们缩成一个团，注意到我们的加边操作一定会保证团内点两两有边，且如果 $u$ 连向了团中任意一个点，那么我们的加边操作一定会使 $u$ 连向团中所有点，除此之外不会有其他加边

那么启发式合并维护极大团即可

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

7. JOISC2020 - 遗迹 [K] ⭐

题面

有一个长为 $2n$ 的数列 $a_1,a_2,\cdots,a_{2n}$，其中 $1\sim n$ 每个数恰好出现 $2$ 次

定义一次操作如下：

同时进行，对于每个 $a_i\neq0$，如果后面有与其相等的数，那么 $a_i$ 会减 $1$

重复这个操作，最后会恰好剩下 $n$ 个非零的 $a_i$

现在给定这 $n$ 个非零 $a_i$ 的下标，求初始的 $a$ 序列个数，对 $10^9+7$ 取模

$1\le n\le600$

题解

Sol

差点就做出来了。火大。

ad-hoc dp。

首先观察到两件事情：靠后的最大值一定会剩到最后，$a_{2n}$ 一定会剩到最后

这为我们提供了两种思路，一种是按最大值从大往小考虑，一种是从后往前考虑

可以尝试一下按最大值考虑，就会发现和给定的下标序列搭不上什么关系，因此我们弃掉。

那么我们从后往前考虑，考虑每次加入一个数 $a_x$，相当于我们动态维护了一个桶，每次加入 $a_x$ 时找到前面第一个没被占用的位置，将 $a_x$ 放到这个位置，如果前面的位置都被占用，那么说明 $a_x$ 会变为 $0$

容易发现，我们把一个数变成 $0$ 的方案数只和第一段连续占用有关

那么我们有一个初步思路：令 $f_{i,j}$ 表示后 $i$ 个数，第一段连续的占用为 $j$ 个，转移的时候如果 $i$ 没有留下，那么它一定放在了前 $j$ 个当中，而这个方案数是可以计算的，如果 $i$ 留下了，那么我们可能会发生 $j$ 变大的情况，那么我们枚举从 $j+2$ 开始的段的长度 $k$，然后钦定这次操作填上了 $j+1$

但这样会出现一个问题，我们无法知道 $f$ 中有多少方案从 $j+2$ 开始的段长为 $k$

我们修改一下定义，令 $z_{i,j}$ 表示后 $i$ 个，将前 $j$ 个填满，且不在前 $j$ 个内进行的操作我们全部忽略（即不进行决策）的方案数

那么就可以列出正确的转移了，中间需要计算辅助数组 $G_i$ 表示用 $i$ 次操作将一个长为 $i$ 的区间填满且不发生溢出的方案数，这个也是容易做的

还有一个小细节：我们上面的讨论可以认为两个高度为 $j$ 是不同的，最后再除掉 $2^n$，这样就避免了一些奇怪的算重问题

复杂度 $O(n^3)$

8. JOISC2020 - 星座 3 [E]

题面

一张大小为 $n\times n$ 像素点的图片，满足 $(i,1)\sim(i,a_i)$ 都为白色，且 $m$ 个给定坐标 $(x_i,y_i)$ 的像素点为黄色，其余像素点均为黑色

保证白色和黄色像素点不重合

你现在需要将一些黄色像素点变为黑色，使得这张图片满足，不存在一个连续子矩形包含至少两个黄色像素点且不包含白色像素点

将第 $i$ 个黄色像素点变为黑色的代价为 $c_i$，求最小总代价

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

题解

做法 1

Sol

反悔贪心。

对于每个点，如果我们选了它，会 ban 掉一个区域，那么我们可以只保留一个偏序方向上的区域，这里如果我们取 $y$ 大于等于当前点的区域，那么就相当于 ban 掉了一个 3-side 矩形 $[l,r],y$，表示所有 $l\le x^\prime\le r,y^\prime\ge y$ 的点 $(x^\prime,y^\prime)$ 都不能再选

将所有点按 $y$ 从小到大排序，那么我们选完一个点后就相当于 ban 掉了一个区间内的点不能选

那么考虑当前点，如果它被之前的点的区间覆盖了，那么我们可以将这些区间删掉，设代价为 $W$，或者将当前的点删掉，设代价为 $C$

注意到有一个性质，每个点 ban 掉的区间一定不交或包含，也就是说 $W$ 的区间一定被 $C$ 的区间包含

如果 $W\ge C$，那么显然删掉 $C$ 更优，因为代价小，ban 掉的区间还更小

如果 $W<C$，那么我们先将 $W$ 删掉，然后给 $C$ 的 $[l,r]$ 内每个点的代价（也即将来的 $W$）加上 $C-W$，如果我们取了这个，代表我们反悔了 $C$，选择了 $W$

出于某种原因，好像就是对的。

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

做法 2

Sol

依然使用 3-side 矩形的转化，并且我们求最大能保留的权值

这个东西长得很笛卡尔树，所以我们把笛卡尔树建出来，每个节点表示一个极大的区间

我们把每个黄点放到对应的节点上，那么一个节点最多只能保留一个

枚举最大的节点选了哪个点，如果选了横坐标为 $x$ 的点，那么下面的节点能 ban 掉的区间只能在 $[l,x-1]$ 或 $[x+1,r]$ 内

也就是说我们想要维护出所有 ban 掉区间为 $[l,x]$ 的答案

注意到这是可以从左右儿子的答案转移的，转移操作只有整体加以及序列拼接，可以用你喜欢的方式维护。

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

9. JOISC2020 - 收获 [E]

题面

圆上有 $n$ 个人，$m$ 棵树，圆的周长为 $L$，第 $i$ 个人在 $a_i$ 的位置，第 $i$ 棵苹果树在 $b_i$ 的位置

每棵苹果树上初始有一个苹果，这个苹果被摘掉后的 $C$ 秒，它会长出一棵新苹果（但不会继续长出第二个苹果）

每个人会以 $1$ 每秒的速度向圆的正方向移动，如果他到了一棵苹果树，那么他会摘掉这棵苹果树上的苹果（如果存在），人之间不独立

$q$ 次询问，每次询问求某个人 $k$ 在 $T$ 时刻及之前一共收获了多少苹果

$1\le n,m,q\le2\times10^5,1\le L,C\le10^9,1\le T\le10^{18}$

题解

Sol

考虑如果某棵苹果树被 $k$ 拿了，那么下一个拿它的人一定是固定的，即 $k$ 后面第一个位置差超过 $C$ 的人，我们称这个为 $p_k$，称传递到下一个人需要的时间为 $w_k$

那么相当于给定一张内向基环树，上面有一些节点 $x_i$ 在某个时刻 $T_i$ 出现一个苹果，苹果会沿着基环树传递，每次询问求点 $k$ 在 $T$ 时刻之前有多少苹果经过了它

对于一个基环树考虑。

我们选择一个环上的基准点 $S$，那么对于每个苹果，它一定会经过 $S$，那么我们拆成经过 $S$ 前和经过 $S$ 后

经过 $S$ 前推一下式子就可以发现是求子树内小于等于某数的数的个数，这个可以用喜欢的数据结构维护。

经过 $S$ 后，我们可以将所有苹果第一次到达 $S$ 的时间 $t_i$ 排序，那么每次询问 $(k,T)$ 就相当于求：

$\sum_{t_i\le T-w_k}\left\lfloor\frac{T-w_k-t_i}{W}\right\rfloor+1$

其中 $W$ 是环长，$w_k$ 是从 $S$ 到达 $k$ 的时间，都是与 $i$ 无关的常量

这个下取整很讨厌，我们想办法把它干掉。

我们按 $t_i$ 从小到达加入，并且从小到达考虑所有询问 $T$，那么我们可以将所有 $t_i$ 变成 $t_i\bmod W$，进行一个“基准化”，这样查询的时候可以关于余数讨论一下，而多算的数对于每个都是一定的

那么我们现在只要维护加入一个 $t_i\bmod W$，求小于等于某数的个数，这个也可以用喜欢的数据结构维护。

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

10. JOISC2020 - 首都城市 [S]

题面

给定一棵 $n$ 个点的树，每个点有一个 $1\sim k$ 内的颜色 $c_i$，你需要选择一个最小的颜色子集 $S$ 使得 $c_i\in S$ 的点组成一个连通块

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

题解

Sol

注意到如果颜色 $i$ 选了，那么包含所有颜色 $i$ 的极小连通块内部的所有点都必须选

那么我们对每个颜色建出虚树然后倍增优化建图即可，最后答案就是出度为 $0$ 的 scc 的最小大小

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

11. JOISC2020 - 治疗计划 [E] ✔️

题面

有 $n$ 个人，初始所有人都染病，有 $m$ 种治疗方案，第 $i$ 种会在第 $t_i$ 天晚上将 $[l_i,r_i]$ 内的人全部治愈，代价为 $c_i$

每天早上，如果第 $i$ 个人染病，那么当天中午 $i-1$ 和 $i+1$ 会被传染

你需要选择一些治疗方案使得最后所有人均被治愈，求最小代价和或判断无解

$1\le n,t_i,c_i\le10^9,1\le m\le10^5$

题解

Sol

以时间为 $x$ 坐标，人的编号为 $y$ 坐标，那么每个治疗方案都是一条竖直的线段，而我们需要从 $x=0$ 走一条斜率为 $-1/0/-1$ 的折线不经过任意一条线段走到 $x=+\infty$（这里可能需要把每个线段两端各增长 $0.5$）

一个经典思路是转化成下底到上底的最短路

观察一下性质，每个线段 ban 掉的位置是一个 45° 倾斜的正方形（对于端点在 $y=1$ 和 $y=n$ 就是一个直角三角形）

我们第一步的 ban 掉的区域一定是从一个直角三角形开始，不断合并进来一个联通的正方形，直到 ban 掉的区域与上底联通为止

注意到由于我们的斜率只能是 $-1/0/-1$，画一下图可以发现我们任意时刻有用的 ban 区域一定是一个直角三角形（如果我们加入出了两个直角三角形的并，那么之后扩展一定是用的新加入的那个，要不然这步操作将毫无意义）

将直角三角形转化为 $y=1$ 上的区间，那么每个治疗方案相当于：如果当前区间包含 $[l_1,r_1]$，可以花费 $c$ 的代价将其变为 $[l_2,r_2]$

容易发现这是一个二维偏序，可以直接主席树优化建图，复杂度 $O(m\log^2 m)$

但是有高明做法。

考虑把点权放在每个点的出边上统计，那么现在每个点的出边权值均相同，这样的图的 dijkstra 可以使用数据结构模拟转移

具体地，按 $dis_i+w_i$ 从小到大考虑点，那么每个点只会被松弛一次

因此我们需要支持找到某个矩形内的所有点，并将它们删除，那么我们用一个线段树套 set 维护，每次找到最小值判断是否满足二维偏序

注意到每个点贡献一次 $O(\log m)$ 的复杂度，所以总复杂度 $O(m\log m)$

12. JOISC2019 - 馕 [K]

题面

给定一个长为 $L$ 的馕，要分给 $n$ 个人吃

馕分为 $L$ 个长为 $1$ 的段，第 $i$ 个人认为第 $j$ 段的美味度为 $v_{i,j}$

你需要将这个馕从 $n-1$ 个有理位置 $\frac{a_i}{b_i}$ 分开，并选定一个排列 $p$，将第 $i$ 个部分分给第 $p_i$ 个人

你需要使得对于任意人 $i$，他得到的馕的美味度之和大于等于他认为的馕的总美味度除以 $n$（$\frac1n\sum_jv_{i,j}$）

构造方案或判断无解

你构造的方案需要满足 $1\le b_i\le10^9$。

$1\le n\le2000,1\le L\le2000,1\le v_{i,j}\le10^5$

题解

Sol

猜一下一定有解，那么考虑归纳构造

我们从前往后考虑馕，找到最早的有某人达到指标 $R_i$ 的位置，那么直接将前面的馕分给这个人一定是符合归纳条件的

但是这样的问题在于分母会超过 $10^9$，因此我们考虑另一个做法

注意到使我们分母变大的主要是我们的每次决策都基于前面的决策，这样分母就会越乘越大

所以我们考虑这样一个策略：

找到每个人 $i$ 美味度第一次超过 $\frac jn$ 倍总和的位置 $pt_{i,j}$

我们枚举 $x$ 从 $1\rightarrow n$，每次找到还没分过馕的使 $pt_{i,x}$ 最小的 $I$，从 $pt_{I,x}$ 将馕切一刀，将切下来的这块分给 $I$

容易检验正确性，并且这样我们的分母也最多是 $O(nV)$ 的

总复杂度 $O(n^2+nL)$

13. JOISC2019 - 两个天线 [E]

题面

给定长为 $n$ 的数列 $H_1,H_2,\cdots,H_n$，$q$ 次询问，每次给定 $l,r$，你需要求 $l\le i<j\le r$ 使得：

$j-i\in[A_i,B_i]$
$j-i\in[A_j,B_j]$
$|H_i-H_j|$ 最大，你只需要输出这个最大值，不存在满足条件的 $(i,j)$ 则输出 -1

$2\le n\le2\times10^5,1\le q\le2\times10^5$

题解

Sol

容易发现绝对值没什么用，因为我们要求的是最大值，可以直接拆成 $H_i-H_j$，然后再将所有 $H$ 取相反数再做一遍

整理一下可以得到限制是 $i\in[j-B_j,j-A_j],j\in[A_i+i,B_i+i]$，也就是说对于一个 $j$，有用的 $i$ 是一个区间，对于一个 $i$，有用的 $j$ 也是一个区间

我们对 $j$ 扫描线，每个 $i$ 相当于在某个位置开始有效，某个位置失效，我们需要对每个 $i$ 维护出 $H_j$ 的最小值，每次询问就是一个区间查询

使用万能的线段树维护。

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

14. JOISC2019 - 两道料理 [K] ✔️

题面

你需要做两道菜：IOI 盖饭和 JOI 咖喱

IOI 盖饭有 $n$ 道工序，需要按顺序执行，第 $i$ 道工序需要 $A_i$ 的时间，如果你在时刻 $S_i$ 之前完成了这道工序，你会获得 $P_i$ 的分数，分数可能为负

JOI 咖喱有 $m$ 道工序，需要按顺序执行，第 $i$ 道工序需要 $B_i$ 的时间，如果你在时刻 $T_i$ 之前完成了这道工序，你会获得 $Q_i$ 的分数，分数可能为负

你在任意时刻不能闲着，求最大得分

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

题解

Sol

首先对 $A$ 和 $B$ 取前缀和。

令 $f_{i,j}$ 表示两道菜分别完成了 $i/j$ 道工序，最大得分，那么有如下两种转移：

$f_{i,j}\leftarrow f_{i-1,j}+[A_i+B_j\le S_i]P_i\\f_{i,j}\leftarrow f_{i,j-1}+[A_i+B_j\le T_j]Q_j\\$

容易发现 $A_i+B_j\le S_i$ 对于特定 $i$，满足条件的 $j$ 是一个前缀，且 $A_i+B_j\le T_j$ 对于特定 $j$，满足条件的 $i$ 是一个前缀

我们枚举 $j$ 从小到大，考虑如何快速维护 $i$ 的转移

每次 $j$ 改变，我们需要先将一个前缀加上 $Q_j$，然后执行 $f_i\leftarrow f_{i-1}+w_i$，其中 $w_i$ 是 $P_i$ 或 $0$

这启发我们维护差分，那么第一步就是单点修改，考虑如何处理第二步

我们发现，这个操作类似于将差分数组对 $w_i$ 取 max，但不完全是，因为我们会导致下一个位置的差分减小

观察到一件事情：如果某一段区间的差分 $d_i$ 全部取到了 $w_i$，那么这段区间开头的修改一定会传递到区间末尾（也即一定不会使中间的差分减小）

那么我们可以维护极长的取到 $w_i$ 的连续段，这样可以均摊分析复杂度

但是考虑 $w_i$ 会变，我们发现 $w_i$ 只会有一次在某个时刻从 $P_i$ 到 $0$ 的变化，也就意味着我们的变化次数是 $O(m)$ 次

那么我们每次把所有 $w$ 或 $d$ 变化涉及的位置全部断开重新暴力合并，复杂度就是 $O((n+m)\log m)$ 的

15. JOISC2019 - 选定城市 [E]

题面

给定一棵 $n$ 个点的树，每条边均为双向，两个方向各有一个权值

$q$ 次询问，每次询问给定一个参数 $k$，你需要选择点集 $S$ 使得 $|S|=k$ 且满足如下条件的边 $(u\rightarrow v,w)$ 的权值之和最小：

将 $u,v$ 之间的两条边删去后，包含 $v$ 的联通块不包含任意一个 $S$ 中的点

你需要输出最小权值和

$2\le n\le2\times10^5,1\le q\le n$

题解

做法 1

Sol

考虑选完 $S$ 后剩下的边长成什么样子，我们发现这就是将 $S$ 的虚树向外连的所有边

如果我们知道了 $x$ 一定被包含在 $S$ 的虚树中，那么我们直接从 $x$ 开始长链剖分，选择前 $k$ 大的长链即可

那么直接套点分治，复杂度 $O(n\log^2n)$

做法 2

Sol

事实上，可以证明当 $k\ge2$ 时 $k+1$ 的最优解是可以通过 $k$ 的最优解构造的

证明没什么意思，所以不放了。

那么我们直接找出 $k=2$ 的最优解，然后以其中任意一个点开始长链剖分贪心即可

$k=1$ 是 trivial 的

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

16. JOISC2019 - 开关游戏 [S]

题面

给定长为 $n$ 的 01 串 $s,t$，你每次可以选择 $s$ 的一个连续子串，将其全赋为 0/1 或将其取反

求将 $s$ 变为 $t$ 的最小步数

$1\le n\le10^6$

题解

Sol

注意到一定存在一种最优方式使得我们先做所有赋值操作，再做取反操作

而取反操作部分的最少次数是差分为 1 的位置个数除以 2，那么我们需要合理使用赋值操作来让这个值变小

另一件事情是我们的赋值操作一定不会重合，那么我们就可以 dp 了

令 $f_{i,0/1}$ 表示前 $i$ 个数，赋值操作完后 $s_i$ 是 $0/1$，$\frac12\text{差分为 1 个数}+\text{赋值次数}$ 的最小值

列出式子后前缀 min 优化 dp 即可

复杂度 $O(n)$

17. JOISC2019 - 穿越时空 Bitaro [K]

题面

有 $n$ 座城市，$i$ 到 $i+1$ 之间有双向边，并且这条边只有在时刻 $[l_i,r_i-1]$ 才能通行，通行需要花费 $1$ 的时间

任意时刻，如果你在某个城市，你可以选择发动穿越时空技能，将时间倒退 $1$ 的时间，并且你的位置不会改变，你可以在城市任意等待

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

1 p s e，令 $l_p\leftarrow s,r_p\leftarrow e$
2 a b c d，你需要求出，如果你在 $b$ 时刻从 $a$ 城市出发，并且要在 $d$ 时刻及之前到达 $c$ 城市，你最少需要使用多少次穿越时空技能

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

题解

Sol

首先，我们判一下 $a$ 和 $c$ 的大小关系，$a>c$ 和 $a<c$ 是对称的，我们只考虑 $a<c$ 的情况

那么我们显然一定往右走，注意到走一步会花费 $1$ 的时间没什么用处，我们将每个 $l_i,r_i$ 减 $i$ 就可以去掉这个条件

这样每条边都是一个 3 段的分段函数，自变量为进入时间，因变量为离开时间以及最小技能次数

分类讨论一下，可以发现一段连续区间的边合并起来的分段函数也是 3 段的，那么直接用线段树暴力维护即可

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

18. JOISC2019 - 蛋糕拼接 3 [S]

题面

有 $n$ 个二元组 $(v_i,c_i)$，你需要从中选出 $m$ 个并任意重排成 $(V_1,C_1),(V_2,C_2),\cdots,(V_k,C_k)$，使得下式最大：

$\sum_{i=1}^mV_i+\sum_{i=1}^m|C_{i+1}-C_i|$

这里认为 $C_{m+1}=C_1$

求最大值

$3\le m\le n\le2\times10^5$

题解

Sol

决策单调性模板。

一定按 $C$ 排序，那么最后答案就可以写成 $\sum V-2(C_{mx}-C_{mn})$

注意到 $mn$ 的选择随着 $mx$ 增大而不断变大，因此可以决策单调性

但是我们求转移点的值使只能支持每次动一步，因此需要写分治

那么我们现在的操作就是加一个数，删一个数，求前 $m$ 大的和，这个不能用你喜欢的数据结构维护，需要使用常数优秀的树状数组上二分。

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

19. JOISC2019 - 合并 [S]

题面

给定一棵 $n$ 个点的树，树上的点被划分为 $k$ 个点集

定义一条边 $e$ 是坏的，当且仅当把 $e$ 断掉后每个点集仍属于同一个连通块

你需要合并一些点集，使得不存在坏的边，求最小合并次数

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

题解

Sol

首先，在某个点集虚树内部的边一定不可能是坏边，那么我们先用并查集将这个处理出来

容易发现剩下的边都是坏边，那么我们现在的连通块依然是一棵树的结构，我们每次可以选择两个点，然后把这两个点之间的路径全部缩起来

根据经典结论，最小操作次数是 $\lceil\text{叶子个数}/2\rceil$

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

20. JOISC2019 - 矿石 [K]

题面

交互题。

有一个数列 $a_1,a_2,\cdots,a_{2n}$，满足对每个 $i$ 恰有一个 $i\neq j,a_i=a_j$

有一个集合 $S$，初始为空，每次询问你可以向 $S$ 中插入一个数或删除一个数，然后你会得到 $\{a_x|x\in S\}$ 中的不同数个数

你需要在 $10^6$ 次内求出每个数与哪个数相等

$1\le n\le4.3\times10^4$

题解

Sol

玩原神玩的。

注意到这相当于是一个二分图，每个点的度数都为 $1$，询问一个集合相当于询问这个集合内部的边数

如果我们知道左右部点，我们可以通过二分来找出每个点的连边

但是我们的集合 $S$ 每次只能变一个元素，使用整体二分就可以保证操作数正确性

现在的问题就是如何找出左右部点

注意到这个可以直接增量构造，每次检查 $i$ 与当前的黑集合是否有边，有边则染白，否则染黑

那么至此我们就得到了一个 $O(n\log n)$ 次询问的算法

之后就是若干没有营养的卡常，这里只说其中的一种

注意到我们的分治操作次数满足 $F(n)=F(m)+F(n-m)+(n-m)+n$

进行一些数学讨论或者直接暴力 dp 可以得到一个常数 $C$，我们按这个比例分治左右长度就可以减小一点操作数

21. USACO22JAN - Minimizing Haybales [S]

题面

给定长为 $n$ 的序列 $h_1,h_2,\cdots,h_n$

对于任意 $i$，如果 $|h_i-h_{i+1}|\le k$，那么你可以交换 $h_i,h_{i+1}$

求若干次操作后能得到的字典序最小的 $h$

$1\le n\le10^5$

题解

Sol

字典序，那么直接从开头开始贪

注意到如果 $i$ 前面存在 $j$ 满足 $|h_j-h_i|>k$，那么 $j$ 和 $i$ 的相对位置关系一定不会变

那么我们每次就是要找到最小的 $h_i$ 使得不存在 $jk$

直接对每个 $i$ 维护 $jk$ 的 $j$ 个数，注意到我们每次只会把一个个数为 $0$ 数换到前面并将它删除，那么每次就是对值域 $[1,h_i-k)$ 和 $(h_i+k,+\infty)$ 的区间 $-1$，可以用值域线段树维护

一开始求个数可以用喜欢的数据结构实现。

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

22. USACO22JAN - Counting Haybales [S]

题面

给定长为 $n$ 的数组 $h_1,h_2,\cdots,h_n$

对于任意 $i$，如果 $|h_i-h_{i+1}|\le 1$，那么你可以交换 $h_i,h_{i+1}$

求若干次操作后能得到的本质不同序列个数，答案对 $10^9+7$ 取模

$1\le n\le5000$

题解

Sol

注意到差超过 $2$ 的数的相对位置一定不变

进一步注意到奇数和偶数内部的相对位置不变，那么就可以 dp 了

令 $dp_{i,j}$ 表示前 $i+j$ 个数内有 $i$ 个奇数和 $j$ 个偶数的方案数，转移是容易 $O(1)$ 的

复杂度 $O(n^2)$

23. USACO22FEB - Paint by Rectangles [E]

题面

给定 $n$ 个二维平面上的矩形，若矩形左下角为 $(x_1,y_1)$，右上角为 $(x_2,y_2)$，保证所有 $x$，所有 $y$ 分别形成一个 $1\sim 2n$ 的排列

这些矩形会将平面分割成若干区域，你需要给这些区域黑白染色，使得有公共边的区域颜色不同，且最外面的无限面颜色为白色

求最后黑白色区域分别有多少个

$1\le n\le10^5$

题解

Sol

烂得有点好。

这题显然只有一种思路是扫描线，那么就对着扫描线拟合做法

对 $x$ 扫描线，考虑一条加入一条线的时候会发生什么：

如果这条线是一条左线，那么我们会新建一些连通块，黑白各占一半，这个是好统计的
如果这条线是一条右线，那么我们会新建一些连通块，或者将两端的连通块合并，新建依然是好统计的，但是合并两端的连通块就会涉及两边是否是同一个连通块的问题

注意到如果两边是同一个块，那么这个一定组成了一个类似 “回” 的图形，而又由于有一档部分分是矩形边界都联通，我们可以猜一下两边属于同一个连通块当且仅当矩形边界出现了不连通的情况，将边界相交的矩形用并查集合并，然后特殊考虑一下即可

那么现在合并两端的连通块一定会造成连通块数 $-1$，因此可以直接用线段树维护

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

24. USACO22FEB - Sleeping in Class [E] ✔️

题面

给定 $n$ 个数 $a_1,a_2,\cdots,a_n$，你可以进行两种操作：

将 $a_i$ 拆成 $x,y$，满足 $x,y\ge0,x+y=a_i$，在原位插入
将 $a_i,a_{i+1}$ 合并为 $a_i+a_{i+1}$，在原位插入

$Q$ 次询问，每次给定 $q$，求最少多少次操作能将所有数都变为 $q$ 的倍数，询问之间独立

$2\le n\le10^5,1\le a_i\le10^{18},1\le Q\le10^5,1\le q\le10^{18}$

题解

做法 1

Sol

首先做一些显然的推导，最后我们要求的就是将 $a_i$ 做前缀和后有多少 $q$ 的倍数，我们可以通过这个 $O(1)$ 求出答案

以下均假设 $a_i$ 是求完前缀和后的结果，那么注意到有用的 $q$ 一定整除 $a_n$

考虑质因数分解，那么每个数都可以被表示为 $\prod p_i^{\alpha_i}$ 的形式，一个 $a_i=\prod p_j^{\alpha_j}$ 对答案的贡献相当于对所有满足 $\forall\alpha^\prime_j\ge\alpha_j$ 的 $q$ 的答案 $+1$，注意到这是一个高维前缀和

那么总复杂度是 $O(d(a)\omega(a)\log d(a))$

做法 2

Sol

质因数分解，考虑对每个 $q$ 直接求解

设 $q=\prod p_i^{\alpha_i}$，那么我们只需要将所有整除 $p_i^{\alpha_i}$ 的数取交即可

这个东西可以用 bitset 实现，但是这样我们一次询问需要取 $\omega(a_n)$ 次 bitset 交，这非常不好。

注意到我们预处理的复杂度其实完全没有达到瓶颈，因此我们可以考虑多预处理一些东西

我们将所有质因子 shuffle 一下，然后将相邻的一些质因子分为一个块，一个块内对所有 $\prod(\alpha_i+1)$ 情况全预处理出 bitset，这样每次询问只需要取 $\text{块数}$ 次 bitset 交

最后我写的方式是依次查看质因子，当 $\prod(\alpha_i+1)$ 大于定值 $LIM=250$ 时新分一个块

这样复杂度是 $O(nk\cdot LIM+Qk\cdot\frac{n}w)$，其中 $k$ 是块数，大概在 $4$ 左右

notes

Sol

注意到上面两种做法都用到了质因数分解，但是 $a_i$ 的大小可达 $10^{23}$，我总共收集了三种不同的处理方式：

直接使用 Pollard-Rho，复杂度 $O(a^\frac14)$
对 $\le10^6$ 的质因子暴力分解，对 $>10^6$ 的质因子特殊考虑（只会有最多三个 $>10^6$ 的质因子，也就是除掉 $\le10^6$ 的质因子后只有 $8$ 种情况，直接预处理这 $8$ 种数之间的倍数关系即可）
“相对分解”，考虑我们本质上是对 $a_n$ 分解，$a_n$ 的质因数不会很多，并且我们用到的质因数分解性质只有唯一性，那么我们没必要分出来的因子都是质数，只要两两互质即可
也就意味着我们可以直接动态维护一个因子集合 $S$，每次加入一个 $q$ 就将 $q$ 与 $S$ 中所有数取 $\gcd$，如果发现 $g=\gcd(q,x)>1$ 就将 $x/q$ 不断除 $g$ 直到 $x/q$ 不为 $g$ 的倍数为止，然后将此时的 $q^\prime,g$ 重新加入
复杂度不会算，大概是 $O(n\log^2a)$？

25. USACO22FEB - Phone Numbers [E]

题面

1
2
3

123
456
789

你有一个如上的数字键盘，你每次可以可以输入一个键，或者两个有公共边的键，或者一个 $2\times2$ 方格内的键

但不幸的是，你的手指很大，如果你一次输入的键数 $>1$，那么这些键会以随机顺序输入，你最后得到的字符串可能不是一开始想输入的字符串

给定字符串 $s$，问你有多少 $t$ 满足如果想输入 $t$，存在一种输入方式使得最后可能实际输入了 $s$，答案对 $10^9+7$ 取模

$1\le|s|\le10^5$

题解

Sol

一眼 dp 套 dp。

考虑判断对一个 $t$ 判断是否有解，那么令 $dp_i$ 表示 $t[1:i]$ 是否能输入成 $s[1:i]$

一种显然的思路是存前 $4$ 个数选了什么以及 dp 值，那么状态数是 $2^4\times9^4$，显然太大了。

考虑压状态：

首先如果 $dp_{i-3}$ 不为真或后面的数不是 $s[i-3:i]$ 的重排，那么 $i-3$ 显然不重要了，我们不用考虑，否则最多只有 $24\times2^3$ 种状态

进一步考虑，在上面的前提下，如果 $dp_{i-2}$ 不为真或后面的数不是 $s[i-2:i+1]$ 的重排，那么 $i-2$ 也不重要了，也不用考虑，否则最多只有 $12\times2^2$ 种状态

这样推下去，那么我们的状态总共有 $24\times8+12\times4+4\times2+1\times1=249$ 种状态，可以接受

复杂度 $O(249|s|\times10\times\text{poly}(4))$

26. USACO22OPEN - 262144 Revisited [K] ✨

题面

给定长为 $n$ 的数列 $a_1,a_2,\cdots,a_n$，每次你可以选择一个 $i$，然后将 $a_i,a_{i+1}$ 合并为 $\max(a_i,a_{i+1})+1$

定义 $f(l,r)$ 表示将 $a[l:r]$ 合并成一个数，最后的数最小是多少

你需要求 $\sum_{1\le l\le r\le n}f(l,r)$ 的值

$2\le n\le262144,1\le a_i\le10^6$

题解

Sol

神秘。

首先注意到 $f(l,r)$ 是最大值 $+O(\log)$ 级别的

存在一档部分分是 $a_i$ 递增，那么我们枚举每个 $r$，然后从 $r-1$ 向左合并出若干个极长的答案为 $a_r$ 的区间，那么我们就可以快速统计右端点为 $r$ 的答案，并且这个结构也是可以快速维护的，即如果 $a_r\neq a_{r+1}$ 那么我们进行一次暴力的合并，每进行一次长度一定减半，因此复杂度是对的

那么我们考虑推广这个做法，我们按最右边的最大值 $a_{id}$ 分治，拆成 $[l,id-1]$ 和 $[id+1,r]$ 递归求解，并对两边分别求出尽量向左合并 $F$ 和尽量向右合并 $R$ 合并出来是什么样子

现在我们要求所有经过 $id$ 的位置的贡献，注意到如果我们支持 $R_l$ 的随机访问，那么我们就可以枚举 $ans-a_{id}$，就可以在 $O(|F_r|\log n)$ 的复杂度内求出经过 $id$ 的答案

我们可以用两个数组分别维护 $F/R$，对每个区间分配内存，合并时我们可以暴力合并，因为这样 $F/R$ 的长度一定减半

考虑这种做法的复杂度，首先我们提出去一个 $\log$，注意到 $[id+1,r]$ 的最大值一定小于 $id$，也即会合并至少一次，那么剩下的部分就是：

$G(l,r)=G(l,id-1)+\frac12G(id+1,r)\\F(l,r)=F(l,id-1)+F(id+1,r)+\frac12G(id+1,r)$

注意到我们定义 $H(l,r)=F(l,r)+G(l,r)$ 就可以得到 $H(l,r)=H(l,id-1)+H(id+1,r)$，那么 $H(l,r)$ 就是 $O(n)$ 的

一种比较直观的理解方式是每个点只会在它祖先中向右走的链上产生贡献，并且在向右走的链上每产生一次贡献影响就会减半

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