Pakencamp 杂题选刷

· · 个人记录

2023

Day 1

G MST (Easy) \color{green}\checkmark

给定序列 a(|a_i| \le 10^6)，构造 n(n \le 2\cdot 10^5) 个点的无向图，点 i,j 的边权是 a_ia_j，求图的最小生成树。

唐氏。首先给 a 排序，显然没有影响。

考察 a_i \ge 0 怎么做：显然答案就是 a_1 \cdot \sum_{i=2}^n a_i，原因根据 Kruskal 的贪心原理，如果连接了一条边 (x,y)，那么 (1,x),(1,y) 的边已经连过，故 x,y 已经连通。

如果有负数做法基本相同，答案是最小的负数乘上正数的和，加上最大的正数乘上负数的和。

复杂度可以线性。

K Or Set \color{green}\checkmark

给定长为 n(n \le 2 \cdot 10^5) 的序列 a(0 \le a_i < 2^m,m \le 30)，定义一个序列的权值为：

  • 初始时变量 x = 0。
  • 对于 i = 1,2,\ldots,n 依次执行，如果 x | a_i \ne 2^m - 1，则 x \gets x | a_i，否则不变。
  • 序列的权值即为 x 的最终值。

你可以任意重排序列，问最终可以产生多少种不同的权值。

笑点解析：这题 *2800。

若只。首先注意到，所有或完以后会到达 2^m-1 的数字全都可以扔到最后，而其他数字的顺序无关紧要。因此问题可以抽象成，将数字分成 A,B 集合，使得 A 集合的或和不为 2^m-1 且或上 B 集合任意数字后等于 2^m-1。

直接枚举 A 的或和里缺少哪一位 i，那么 B 中每一个数字都必须含有 i，而 A 集合里的数字都必须不含 i，一一枚举判断即可。复杂度 \mathcal O(nm)。

L Range Mex Sum Min \color{green}\checkmark

给定排列 p(n \le 5 \cdot 10^5)，有的地方已经填好，有的地方还没填。请你补全排列 p，使得排列 p 的所有子区间的 \text{mex} 之和最小。

唐氏。

注意到我们希望这个值最小，因此每次一定会填在最边上的空位上。但是这个决策是有后效性的，不能直接贪心，好在它的后效性并不多，具体的，操作的后效性只在一个连续段生效，可以这样感性理解： - 假设值域上连续的两个 $-1$ 都选择了左边，那么把一个换到右边不劣； - 否则，其不会产生后效性。 也就是说，操作 $1$ 的后效性在操作 $2$ 进行时就已经消除，故仍然可以线性解决。 ### [M + and Xor](https://atcoder.jp/contests/pakencamp-2023-day1/tasks/pakencamp_2023_day1_m) $\color{green}\checkmark

给定 n(n \le 2 \cdot 10^5)，求一个 n 阶排列 p 使得 \bigoplus_{i=1}^n (p_i+i) 的值最大，输出方案。

若只打表题。设 d = 2^{\log_2n}。

32 15 16
33 30 32
34 13 16
35 31 32
36 11 16
37 30 32
38 9 16
39 31 32
40 7 16
41 30 32
42 5 16
43 31 32
44 3 16
45 30 32
46 1 16
47 31 32
48 7 8
49 30 32
50 5 8
51 31 32
52 3 8
53 30 32
54 1 8
55 31 32
56 3 4
57 30 32
58 1 4
59 31 32
60 1 2
61 30 32
62 0 0
63 31 32

其中第一列是 n，后两列是 l,r。

规律：

根据这个规律直接模拟即可。

证明不会，我也不知道官方题解写的什么做法，日语看不懂一点。

P MST (Hard) \color{red} \times

给定序列 a,b(|a_i|,|b_i| \le 10^6)，构造 n(n \le 2\cdot 10^5) 个点的无向图，点 i,j 的边权是 a_ia_j+b_ib_j，求图的最小生成树。

考虑使用 b*** 算法，问题可以基本转化为：

这一部分是 ABC244H。注意到 ax+by = b(\frac{a}{b}x+y)，李超树维护括号里面的东西即可。

Day 2

B Salesman X \color{green}\checkmark

给定一棵 n(n \le 2 \cdot 10^5) 个点的树和 2m 个关键点 x_1,x_2,\ldots,x_m,y_1,y_2,\ldots,y_m，要求：

  • 第一天从 1 出发，以任意顺序遍历前 m 个关键点 x_1,x_2,\ldots,x_m，并在其中某一个停下。

  • 第二天从这个点出发，以任意顺序遍历后 m 个关键点 y_1,y_2,\ldots,y_m，最后前往给定的终点 s。

    求行走的最小总代价和。

糖。首先考虑怎么计算第一天停在 x_i 的最小代价，实际上就是 1,x_1,\ldots,x_m 组成的斯坦纳树的边权两倍和，减去 d(1,x_i)。在树上，计算这个和的经典做法是按照 dfs 序排序后 \sum dis(i,i \bmod n + 1)。

然后我们已经得到了第一天停在 i 的代价 d_i，只需把它们每一个插入到第二天的斯坦纳树上即可，只需要找 dfs 序的前驱后继。upper/lowerbound 解决。

C Arithmetic Progression and ... \color{green}\checkmark

有一个长为 n(n \le 2 \cdot 10^5) 的等差数列 a_i = ki + l(a_i \le 10^{18})，但是有 \lfloor \dfrac{n-1}{2} \rfloor 项被篡改了。你得到了 a 重排后的序列，请你还原 k,l。保证有解。

等差数列必然满足 \forall i,j \in [1,n],a_i \equiv a_j \pmod k，于是立刻想到 ABC272G，但问题是本题值域太大，根本不可能一一检验 a_i - a_j 的因数。

注意到等差数列满足 \dfrac{a_i-a_j}{k}<n，因此只需要检验 a_i-a_j 的满足 \dfrac{a_i-a_j}{d} < n 的因数 d，猜测一下这个数量不会太多，然后就过了。神秘。

H Two PCities \color{green}\checkmark

DS 好玩捏。

给定一棵 n(n \le 10^5) 个点的无权树和一张无向无权图 G，如果 (i,j) 在树上距离大于常数 k 则在图上有一条边。q(q \le 10^5) 次询问 u,v 在图 G 上的最短路。

一个很直观的想法是，直接走直径。从 u 到较远直径的一端，然后可能需要跨直径，然后再到 v，需要 3 步。这引出了一个很重要的观察：如果有解，答案必定小于等于 3。

判定答案是否是 1,-1 是容易的，问题是怎么判断答案是否是 2。而这等价于，判断是否存在一个 w 满足 dis(u,w) > k 且 dis(v,w) > k。

考虑边分治，对于左子树的每一个 u 只寻找跨过 rt 的 w。容易发现，满足条件的 w 在深度上是一段后缀。v 到某个点集里最远的点一定在直径上，那么直接维护这个后缀的直径即可。复杂度 \mathcal O(n \log n)。

官方题解里有一个简洁的做法：找到路径中点，则必定一边离 u 更近，一边离 v 更近。只需要维护两边的直径。一边是子树，可以直接 dfs；另一边是 dfs 序上的前后缀，可以快速合并。搭配 \mathcal O(n)-\mathcal O(1) 的树上 k 级祖先和 LCA 可以做到线性，比较牛的。

Day 3

B AND \color{green}\checkmark

  • 给你一个数组 a(n \le 2 \cdot 10^5,a_i < 2^{30})，每次你可以选择两个相邻元素 i,j 并把 a_i \gets a_i \& a_j（不一定要求 i<j）。数组的权值即为最小的操作次数，如果无解为 -1。

糖。

首先注意到，如果序列里有 0，那么可以直接用这个 0 解决问题；否则，我们一定会先造出来一个 0，此时别的元素的值我们不再关心，因此我们可以转化问题成求造出来 0 的最小操作次数。

考虑枚举位置 i，怎么求它的最小次数？注意到造 0 一定是两边同时往中间推，可以设计一个 dp_l：表示左端点的位置在 l 时右端点的最小值。l 的本质不同取值只有 \mathcal O(\log V) 个，只需要关心这些点的 dp 值。

求子区间的答案等价于求 [l,r] 包含的最小权 dp 区间，简单扫描线即可求出。

G MOD \color{red} \times

给定数组 b(n \le 2 \cdot 10^5) 和 m(m \le 2 \cdot 10^5) 条边 (u_i,v_i)。你有一个初始为 0 的数组 a，可以进行任意次操作，每次可以选择一条边并给 a_u,a_v 同时加一。问能否使 b_i \equiv a_i \pmod p 对所有 i 成立，其中 p 是一个全局给定的数（不保证是质数）。

很好的题啊，除了我不会以外都很牛！

首先进行一些最基本的观察：

注意到剩下的情况里，图一定存在奇环，我们希望用奇环做一些调整。首先，不在奇环上的部分可以当作森林处理，我们计算出新的 b_i。环上的部分我们先按照链处理，只有最后一个位置可能产生冲突。我们希望只有这个位置的值改变，给 1,2 位置 +1，2,3 位置 -1 以此类推，由于环长是奇数，1 位置最终会加上 2 而其他位置的值不变。如果此时的 b_i 为偶数，显然可以达成目标；否则如果 M 是奇数可以选择操作 2 的逆元次，也可以达成目标。唯一的无解情况是，M 是偶数。此时易证无解，原因是操作改变不了奇偶性。

注意到 M 是偶数时森林上的操作不会改变最终 b_i 的奇偶性，故直接判断 \sum b_i 是否是 2 的倍数即可。

2022

Day 1

I Forgotten Sequence \color{green}\checkmark

你需要构造一个序列 a(n \le 2 \cdot 10^5)，有 m 条限制，每一条限制形如：a_x = a_y 或 a_x \ne a_y。求字典序最小的序列 a，或报告无解。

并查集维护数字的相等关系，贪心构造。

不知道这种唐氏题是咋评到 2000 以上的。

J An Unusual King in Paken Kingdom \color{green}\checkmark

给定一棵树和 q(n,q \le 2 \cdot 10^5) 次询问，每次询问 u,v 两点之间路径上边权的中位数，

主席树板子，谔谔。

K Beautifulness \color{green}\checkmark

给定序列 a(n \le 2\cdot 10^5) 和 q(q \le 2 \cdot 10^5) 次询问，每次询问一个区间有多少种不同的前缀 \max。

由于不带修且可离线，我们不需要写单侧递归。直接将所有询问离线，从后向前扫描线扫 l 并维护反向的单调栈，树状数组维护贡献。复杂度 \mathcal O((n + q) \log n)。

L Mex on Blackboard 2 \color{green}\checkmark

给定序列 a(n \le 2000) 和整数 k(k \le 2000)，你需要做 k 次操作。一次操作是选择当前 a 的一个子序列并把这个子序列的 \text{mex}。问最后可以得到多少不同的序列 a，对 998244353 取模。

注意到如果 a 中存在 \text{mex} = k 的子序列，则一定存在 \text{mex} = 0,1,\ldots,k-1 的子序列。

注意到如果插入的 \text{mex} 不是原序列的 \text{mex}，那么原序列 \text{mex} 以上的数字的出现状态没有改变。预处理 to_i 表示 \text{mex} = i 且插入 i 后 \text{mex} 变为多少，然后据此简单 DP 即可。

M 01 Tree \color{green}\checkmark

你有一颗 n(n \le 5 \cdot 10^5) 的树，每个点可以涂黑白两种颜色，已经有 k 个点确定颜色。还有 n 条限制：点 a_i 和其所有儿子颜色必须和点 i 一样。构造或报告无解。

若只。

考虑直接并查集暴力合并会有什么问题，复杂度可能被重复的 a_i 卡到 \mathcal O(n^2)。然而注意到合并一次后 a_i 和其儿子必然是一个颜色，故第二次遇到 a_i 时只和其本身合并即可。

N Paken Machine \color{green}\checkmark

给定数 x,t,p 和数组 a_0,a_1,a_2,b_0,b_1,b_2。第 i 次操作会令 x \gets (a_{i \bmod 3}x + b_{i \bmod 3}) \bmod p。问 x 第一次等于 t 是第几次操作，或报告无解。保证 p 是质数，且 \textbf{0} \le a_i,b_i,x,t < p \le 10^9。

注意到操作在模 3 意义下有循环节，且两次操作可以快速复合。不妨先枚举除去整循环节后还有几次操作，然后只需要计算最少要几个整循环节，这是 BSGS 板子。

然后特别注意，a,b,x,t 都可以取到 0 或 1，请对一些情况导致的除 0 特判。特判非常恶心，也许是本题的唯一难点。

O Paken Land \color{green}\checkmark

给定一棵 n(n \le 2 \cdot 10^5) 的树，对于每个点 i 找一个 j \ne i 的点，最大化 i \to j 路径上边权的平均数。

首先考虑序列上怎么做，其实就是 ABC341G。经典的套路是，把平均数的除法看作前缀和除以长度的斜率，于是只需要建出凸包。

问题搬到树上，我们边分治并对一边建凸包，回答另一侧的询问即可。注意查询的时候由于没有单调性，需要一次额外二分斜率。复杂度两个 \log。

Day 2

E Harmony \color{green}\checkmark

有 n 个物品和 m 种颜色（n,m \le 10^5），每个物品有属性 a_i,b_i,c_i，分别是价值、颜色和价格。对于每个物品，你都可以花费 c_i 的价格将其颜色 b_i 修改为任意颜色。你需要回答 q(q \le 10^5) 个询问，每个询问形如：在总价格不超过 x_i 的情况下，每个颜色的最大价值的最小值是多少？

考虑单组询问怎么做：显然可以二分答案 mid，这样物品只有 0 和 1 的价值。我们需要将每种有多余物品的颜色的较小的 num-1 个扔进没有的里面。

注意到可能的答案只有 n 种，对每一种都求出答案即可。按 a 排序后处理，用平衡树维护决策，复杂度一个 \log。

F Farthest \color{green}\checkmark

给定数组 a(n \le 2 \cdot 10^5)，一些部分变成了 -1，你需要将他它们补成 1 \sim n 的元素。定义一个数组是好的，当且仅当存在一棵无权树，满足距离点 i 的最远点是 a_i。求有多少种填法满足数组 a 是好的，模 998244353。

首先考察序列 a 是好的的必要条件：

我们贪心的希望 k = n - 1，然后你发现这些条件实际上已经充分，因为你总可以构造一个菊花图，这样每个点可以到达的最远点可以是除了自己以外的任意叶子。

不妨忽略颜色的限制，只管第一条限制。那么此时的答案显然是 (n-1)^{t}，其中 t 是问号的数量。

注意到满足第一条且不满足第二条的序列 a 实际上是一个错排。计算一部分已经填好的错排方案是经典问题，使用容斥原理可以做到线性，参见 CF340E。

G Worst Town \color{red}\times

  • 交互题。交互库有一张 n 个点 m 条边的无向图（n \le 200,m \le 300），你只知道 n 的值而不知道 m 的值和图的形态。
  • 你每次询问可以给出一个点集，交互库告诉你这个点集是都是一个独立集。你做多可以询问 3200 次，你需要还原原图的每一条边。
  • 有一些有启发性的部分分：
    • Sub 2：图是二分图，且左部点是所有奇数。
    • Sub 3：对于任意三个点 a,b,c，如果 a,b 两点有边，b,c 两个点没有边，则 a,c 两个点之间一定有边。

很牛的题啊！

首先 Sub 2 是很送分的，由于所有左部点内部没有边，考虑对于每一个右部的点 x，用若干次询问问出其连接的所有边。我们可以使用二分找出一条边：如果 x 和 [1,mid] 的左部点形成独立集则 x 与 1 \sim mid 的左部点间没有边，否则有。 使用 \mathcal O(\log n) 次询问问出一条边，则总询问次数 \mathcal O(m \log n)，精确计算大概是 300 \times 6 = 1800 次询问。

考虑 Sub 3 的神秘限制，这个神秘的条件说的其实是，图是一张完全 k 分图。考虑将图划分为 k 个独立集，如果存在两个点 i,j 属于两个不同的独立集且它们之间没有边，则任意选择一个 k 满足 j,k 之间有边（如果找不到那么 i,j 应当在同一个独立集，矛盾），根据独立集定义 i,k 无边，故 (i,j,k) 不满足题意。

那么这个 subtask 的做法也很简单，直接动态加点维护每个独立集，暴力将新点加入。注意到加入一个点加不进去某个独立集一定是因为一条边，故 n 个点的总询问次数是 m。总询问次数 n+m。

那么其实原题的做法已经差不多清楚了，我们延续 Sub 3 的思路，仍然将图划分为若干个独立集，对两两独立集之间暴力二分。询问次数即为 n + m + m \log n，可以通过。

Day 3

A Moving Piece \color{green}\checkmark

给定 2n+1(n \le 300) 大小的方阵 a，在 (i,j) 放置障碍物的代价是 a_{i,j}。求最小的代价使得 (1,n+1) 和 (2n+1,n) 两点不连通，不能再这两个点上放障碍。

比较经典的最小割转最短路建模。

左侧建超级原点连向左半边的边缘，网格八连通连边，右半边边缘连向超级汇点。显然任意一条源点到汇点之间的路径都会把目标点割开，故源汇之间的最短路即为答案。

B Chmax \color{green}\checkmark

给定序列 a,b(n,m \le 3000)，你需要对序列 a 执行 m 次操作，第 i 次操作可以选择一个 j \in [1,n] 并令 a_j \gets \max(a_j,b_i)。问最后可以得到多少个不同的 a 数组，对 998244353 取模。

首先注意到 b 的顺序是无所谓的，那我们不妨将它排序，升降两种排序方法走向两条完全不同的路：

不妨先考虑 \min b_i > \max a_i 的情况。 此时发现推平仍然难以计数，因为很容易算重，因此我们考虑第二种，直接 ban 掉已经用过的位置。

相同的值可能导致算重，因此我们按值域考虑。考虑设 f_{i,j} 表示填了值域 i \sim n 的数，且还剩 j 个位置没有被覆盖的方案数。 如果 b 里有 d_i 个 i，则有转移 \dbinom{j}{k}f_{i,j} \to f_{i-1,j-k} (k \in [0/1,d_i])。复杂度均摊 \mathcal O(nm)。

考虑没有了 \min b_i > \max a_i 的限制，相当于推平的位置有了限制，可能会随时消失，这对我们计数很不方便。我们不妨把整个过程倒过来做，这样 ban 掉位置相当于加位置，很好处理了。

corner case 比较多，傻逼。

C Permutation of Length 26 \color{green}\checkmark

给定字符串 s(n \le 10^5)，首先你需要任意选择一个子串 s[l,r] 并令 s \gets s[l,r]，然后选择一个 1 \sim 26 的排列 p，同时将串中所有字符 i 替换为字符 p_i。求 s 字典序的最大值。

首先由于要求的字典序最大，我们选择的肯定是一个后缀。那么有了暴力 \mathcal O(n^2) 做法：对每个后缀贪心一遍得到其排列 p，然后比较字典序。

我们希望快速比较两个后缀 i,j 谁更优秀，根据比较字典序的规则，我们需要：

考察我们这个贪心的流程：

那么快速确定每个字母的值是比较简单的：将所有字母在这个后缀以后的第一次出现位置倒序排序即可。

注意到一个位置的字符和其前驱的位置强相关，如果我们将小于后缀开头的位置都设为 0，那么我们可以用序列 \{i-pre_i\} 来刻画原串。进一步的，序列 \{i-pre_i\} 之间的等量关系和两串的等量关系完全相同。

有了这个观察，我们可以线段树动态维护序列 \{i-pre_i\} 的哈希值并二分求 LCP。

复杂度视实现可以做到 \mathcal O(n \log n) 或 \mathcal O(n \log^2 n)。

D Yet Another Balls and Boxes Problem \color{red} \times

给定数组 a(n \le 2 \cdot 10^5,a_i \le 10^5)，一次操作是选择 x,y 满足 a_x \ge a_y，同时令 a_x \gets a_x - a_y,a_y \gets 2a_y。用不超过 2 \cdot 10^6 次操作使得数组里只剩下一个元素，或报告无解。

最理想的情况是，数组是 2^k 个 1，这种情况非常好做。

考虑能够借鉴上面倍增的思想，每次合并两个奇数，操作后一定会得到两个偶数。如果恰好有偶数个奇数，则两两合并后全都会变成偶数；否则总和一定是奇数。

如果每次合并都有偶数个奇数，那么合到最后立刻结束。否则我们断言直接无解。考虑一个奇素数 p 满足 p 是 \sum a_i 的因数，则 a_i \bmod p = 0 会对所有 i 成立。考虑一个数对 (x,y) 满足 x \bmod p \ne 0 且 y \bmod p \ne 0，操作完后显然不可能变成 0，故无解。

  • 某模拟赛加强了这题：可以留下两个数字。
  • 注意到把每一轮多出的那个奇数留下来，最后会剩下一个有 \mathcal O(\log n) 个数字的互不相同序列。
  • 考虑选出三个数字 a < b < c，我们通过操作实现 b \gets b \bmod a，并不断迭代直到最小值等于 0。
    • 注意到 b \bmod a = b - a \lfloor \frac{b}{a} \rfloor，记 t = \lfloor \frac{b}{a} \rfloor，考虑类似快速幂的，每次给 a 乘 2，如果第 i 位是 1 就给 b \gets b - a，否则去对 c 操作。
    • 操作完后，a 会翻 t 倍，c 会变小，b 会变成一个 [0,a-1] 之内的数字。
  • 我不清楚怎么严谨的分析操作次数，但是看起来最小值大概是除以 2 了的。迭代一次的轮数可以看作 \mathcal O(\log n)，故操作数量为 \mathcal O(\log^3 n)。

E Output-Only \color{green}\checkmark

构造两个长度为 10^5 的正整数序列，满足 \forall i \in [1,2 \cdot 10^6]，都存在 x,y 满足 a_x \cdot b_y = i。

非常搞笑的题。

首先所有质数肯定要存在在序列里，打表发现 2 \cdot 10^6 以内的质数大概有 1.5 \cdot 10^5 个，我们将它们平分至两个序列。

直接把 1 \sim 20000 塞进每个序列。一个 2 \cdot 10^6 内的数字不可能有两个大于 2 \cdot 10^4 的质因子，故问题解决。

I Prefix Or \color{green}\checkmark

给定序列 a(n,a_i \le 2\cdot 10^5)，重排使得其所有前缀的或和之和最小。

看完题立刻写贪心：每次找最小的或和，只有 \mathcal O(\log n) 个不同的或和，故暴力复杂度正确！样例全过！然后不出意料的 wa 掉了。

考虑以下数据：

4
4 4 4 3

注意到 [3.4.4.4] 是不优秀的，因为 3 被算了太多次。

我想了很久也没能设计出一个合理的贪心策略，注意到值域不大，考虑 DP。

设当前最后一个位置的或和是 i 时最小前缀或和和时 dp_i。注意到这时候由贪心的思想，序列的长度其实是已经确定的：所有是 i 子集的元素其实都已经放在序列前面，故序列长度是 c_i，而这个值可以高维前缀和预处理。

有 DP 式子：dp_i+(i|a_j) \cdot (c_{i|a_j} - c_i) \to dp_{i|a_j}，但是这个 DP 是 \mathcal O(nV) 的，不能通过。

考虑对其进行放缩，去掉只可以或上 a 中元素的限制，直接做子集 DP，容易发现这样正确性仍然保持不变。

可以直接枚举子集做到 \mathcal O(3^{\log V})。

J Balanced Permutation \color{green}\checkmark

给定长为 n(n \le \textbf{5000}) 的排列 a，有些位置还没有填。补全排列 a 以最小化 \max|ip_i - jp_j| 的值。

不要被数据范围骗了。

想了很久也想不出来贪心从大往小填哪里不对，写了一发 \mathcal O(n) 的贪心，直接过了，傻逼。

与上面那个题形成鲜明对比。

2021

Day 2

I Multiple Swap \color{green}\checkmark

给定两个长 n-1(n \le 5 \cdot 10^{\textbf 4}) 的数组 a,b，一次操作你可以选择两个位置 i,j 满足 j 是 i 的倍数并交换 a_i,a_j。在 10^6 次操作内将 a 变成 b，或报告无解。

大水题，不知道咋 2k8 的。

首先我们可以根据 b 重标号 a，目标变成给 a 排序，只需要 n - 1 次交换任意两个数的操作。

有一个直观的交换方法是，i \to 2i \to 2 \to 2j \to j，唯一的问题是可能会出现 2i,2j > n。

注意到大于 n/2 的质数不可能被移动，故如果这些位置有不同必然直接无解。

否则，每个数字的最小质因子必然不超过 n/2，故交换路径 i \to f_i \to 2f_i \to 2 \to 2f_j \to f_j \to j 一定合法，需要 11 次操作，符合条件。

J Min-Max Sequence \color{green}\checkmark

给定 n,m(n,m \le 2 \cdot 10^5) 和长 n 的序列 a,b，你需要计数满足下面条件的值域 [1,m] 的序列 c，对 998244353 取模：

  • 条件：如果 a_i = 0 则 \min(b_i,b_{i+1}) = c_i；如果 a_i = 1 则 \max(b_i,b_{i+1}) = c_i。

直接设 dp_{i,j} 表示已经填了 i 个位置且最后一项的值是 j 的方案数，以 \max 为例，转移方程是

dp_{i,j} = \begin{cases} \sum\limits_{k \le j} dp_{i-1,k} & j = a_i\\ [j \le a_i] dp_{i-a,a_i} & \text{otherwise}\end{cases}

可以直接上线段树优化。

更优美的做法是，dp 数组有值的位置一定是一个值相同的区间和一个单点，可以直接维护，转移时讨论。复杂度线性。

K Bracket Inserting \color{green}\checkmark

你有一个空的字符串 s，一次操作可以在任意位置插入相邻的一对括号（即，s = s[1,i] + \texttt{()} + s[i+1,n]）。问 n 次操作后得到 t 的方案数，模 998244353。

把每次插入一对括号的过程倒过来看作每次删除一对括号，容易发现删除顺序本质上是括号树的拓扑序。

有根树的拓扑序计数是经典问题，考察每个点作为子树最小值的概率，故答案是 \dfrac{n!}{\prod siz_i}。

L ジグザグ道 \color{green}\checkmark

给定 n 个点 m 个点的图（n,m \le 10^5），边带互不相同的权。求一条 1\to n 的路径，满足路径上的边权 c_1,c_2,\ldots,c_k 满足 (c_i-c_{i-1})(c_{i+1}-c_i)<0。

考虑如果只需要严格递增怎么做：可以对每个点拆入点和出点，然后做前后缀优化建图。

现在需要先增后减，那么不妨额外记一个 0/1 跑最短路，总边数是大常数 \mathcal O(m)。

M Deque and Inversions \color{red}\times

  • 定义一个排列 p 的权值是，执行以下操作后 q 的逆序对的最小值：
    • 初始时 q 为空。
    • 对于 i = 1,2,3,\ldots,n，你可以选择将 p_i 放在 q 的开头和结尾。
  • 求所有 n! 个排列 p 的权值之和。

首先对题目做第一步转化，注意到不管把 p_i 插在哪里，p_{i+1} 插入时造成的逆序对数总是相同，因此可以直接按步骤贪心。即，如果设 f_i 表示 i 前面小于 p_i 的数量，答案是 \sum \min(f_i,i-1-f_i)。

一个很重要的观察：设 g_{i,j} 表示 f_i = j 的排列数量，对于固定的 i，g_{i,0} = g_{i,1} = \ldots,g_{i,i-1} = \dfrac{n!}{i}。直接列式子暴力证，发现最后实际上要证明的是 \sum \limits_{i} \binom{i}{p}\binom{n-i}{q} = \binom{n+1}{p+q+1}，使用类似上指标求和的组合意义证明。

N Polynomial Comparison \color{green}\checkmark

给你两个多项式 f(x),g(x)(n,m \le 2 \cdot 10^5)，问 x = k 时 f(x),g(x) 的大小关系。

首先先给 f \gets f - g，只需要比较 f(k) 和 0。考虑从大往小处理，由于 x^k = x \cdot x^{k-1}，如果 x^k 的系数不为 0 我们就给 x^{k-1} 的系数加上这个值乘 x。注意到当某一项系数已经很大的时候，整个式子和 0 的大小关系就取决于这一项，直接判断即可。

O Golf \color{green}\checkmark

给定一个字符串 s(n \le 2 \cdot 10^5)，定义一个字符串 t 是好的，当且仅当 t 在 s 中出现了恰好一次。q(q \le 2 \cdot 10^5) 次询问，每次询问给出 l,r，查询最小的 len 满足存在一个 x \le l,x + len - 1 \ge r 且 s[x,x+len-1] 是好的。

固定起点时，好的字符串长度有单调性。我们首先用后缀数组求出 a_i 表示以 i 为左端点的串长度大于等于 a_i 的都是好的。

然后就变成了一个线段树扫描线问题，直接维护即可。

Day 3

E お菓子 \color{green}\checkmark

E お菓子 \color{red}\times

给定一个序列 a(n \le 1 \cdot 10^5)，q(q \le 1 \cdot 10^5) 次操作，支持单点修改，查询有多少个区间的 \text{lcm} = x。

有一个比较简单的 \mathcal O(n \log^3 n) 做法，即维护线段树区间的 \mathcal O(\log n) 个前后缀并暴力合并。

但是注意到一个性质：包含位置 x 的区间的不同 \text{lcm} 其实只有 \mathcal O(\log^2 n) 个，原因是前后缀各自只有 \mathcal O(\log n) 个。那修改的时候直接线段树二分找出来，用 umap 动态维护。

F ワープ \color{green}\checkmark

  • 给定一条 1 \to n 的链和 m 个点对 (u_i,v_i)，q 次询问问如果加一条边 x,y，m 对点的最短路之和。询问之间独立。

垃圾题，根据 [x,y],[u_i,v_i] 的位置关系分类讨论直接走 v_i - u_i 和走额外边 (x,y) 的代价哪个更小。有 3 种情况只有 u_i,v_i 的限制，另一种还有 v_i - u_i 的限制。跑 5 遍二维数点和 2 遍三维数点即可计算贡献。复杂度 \mathcal O(n \log^2 n)。