SDSC2025

day 1

模拟赛

T1

序列，价值为全局 gcd，可以进行至多一次操作将 $[l,r]$ 内权值加常数 $k$，求最大价值。

答案由前后缀 gcd 和中间加 k 的 gcd 组成，前缀 gcd 一共有 log 段，每一段一定是取最大的 l 最优，后缀同理，枚举 l 计算答案就行了，时间复杂度 $O(n\log V)$。

---

T2

Alice 在 X 国家旅游，一共有 n 座城市，标号 1 到 n。城市之间有 m 架航班，第 i 架航班从 ui 城市飞往 vi 城市，花费 wi 元钱。注意航班是单向的，也就是不能从 vi 城 市飞往 ui 城市。
Alice 现在在 1 号城市，她的家在 n 号城市。Alice 现在只剩下 p 元钱了，可能不够回家的路费了。但是 Alice 没有放弃！她可以在 i 城市打工，每工作一天获得 ai 元钱。
假设城市之间除了航班没有其他的交通方式。Alice 想知道，要想能回到家，她至少需要工作多少天？如果无论如何都无法回到家也请告知 Alice，身在异国他乡，她会照顾好自己的。

记录二元状态 $(c,m)$ 表示工作次数与剩余钱数，两者构成严格偏序关系，因为走得越远越有可能工作得少。记 $f_{i,x}$ 表示走到 $i$ 路径上最大值在 $x$ 的状态，dij 转移即可。

---

T3

树有点权，将其划分成若干区域，区域的价值是区域中第二大的点权值，求最大的区域价值和。

观察到只需要选择最大值和次大值的点所确定的路径即可，设 $f_{i,x}$ 表示点 $i$ 连了权为 $x$ 的点的答案，$g_i$ 表示考虑到 $i$ 的子树内的答案，有转移

$$f_{u,i}=\max\{f_{u,i}+g_v,f_{v,i}+\sum_{v'<v}g_{v'}\}$$

$$g_u=\max\{g_u+g_v,f_{u,i}+f_{v,i}+\min(i,j)\}$$

对每个点开 seg 维护 $f_{u,i}$ 的最大值与 $f_{u,i}+i$ 的最大值做线段树合并就行。

---

T4

你正在研究一个排列 p 的性质。但是你的草稿纸密密麻麻，你弄丢了这个排列！幸运的是你找到了草稿纸上记录的这个排列的一些性质。具体的，你找到了这个排列 p 长为 n，其中 1, 2, ···, n 在其中分别出现过一次。你还找到了长为 n 的序列 b，其中 bi 表示 j < i 而且 $p_j > p_i$ 的 j 的数量。你想要从序列 b 还原排列 p。但是你看着你乱作一团的草稿纸，时不时找到一个新的 bi，导致你一直在改变 b 的值。接下来的 q 分钟内，每分钟会发生其中一种事件：

1. 1 i x ——你改变了 bi 的值为 x。
2. 2 i ——你想要找到 pi 的值。
   但是单靠 b 序列也许并不能确定 pi 的值，请你输出最小的可能的 pi 的值。保证至少有一个排列 p 满足序列 b 的限制。

$c_i=i-b_i$ 的含义是 $b_i$ 的前缀中 $p_i$ 的排名，扫 $i:1\rightarrow n$，由定义设 $p_i=c_i$ 然后把 $p_j\geq c_i$ 的 $p_j$ 加一，于是可以构造出唯一的 $p$。这样可以做到 $O(qn)$。

对于一个区间，定义 $t(x)$ 表示 x 经过区间之后会变成的数，这是一个分段函数，并且每一段的斜率都是 1。这个东西不好维护，转而维护 $f(i)$ 表示表示如果 $x\geq f(i)$ 那么 $x\rightarrow x+i$，考虑合并两个区间的函数 $f_l$ 和 $f_r$，考虑一共增加了 $k$，枚举分别加了 $i,j$，那么 $f(k)\geq f_l(i),x+i\geq f_r(j)$，于是 $f(k)=\min_{i+j=k}\{\max(f_l(i),f_r(j)-i)\}$。发现这样合并有很好的性质：如果 $k$ 是由 $(i,j)$ 转移而来的，那么 $k+1$ 就只能从 $(i+1,j)$ 或者 $(i,j+1)$ 转移过来！原因是 $f$ 单调不降，$(i,j)$ 能多贡献就多贡献，不会回退，就得到了 $O(len)$ 合并信息的做法。线段树维护这个信息就能做到 $O(n\log^2 n)$。但是这样维护单调修改的话就是 $O(n)$ 的，考虑分块平衡复杂度，分成 $B$ 块，每块开线段树，这样修改时间复杂度 $O(B)$，查询时间复杂度 $O(\frac{n}{B}\log n)$，平衡一下令 $B=\sqrt{n\log n}$ 就可以做到 $O(n\sqrt{n\log n})$ 了。

讲课：基础算法 神秘题目

人类智慧大赏。

---

Latin Square

$n\times n$ 的矩阵，每行每列都是 $1$ 到 $n$ 的排列，有如下几个操作：

• 每行向右/左循环移位
• 每行向上/下循环移位
• 将每行/列的排列变为逆排列（一个排列 $p$ 的逆排列 $q$ 指 $p_{q_i}=i$）

求最终矩阵的样子

平凡的记 $(i,j)$ 维护前两种操作是方便的，但难以维护逆排列的操作，考虑记 $n^2$ 个三元组 $(i,j,a_{i,j})$，那么逆排列操作就变成了交换 $(i,j)$ 中一维和 $a_{i,j}$，直接维护三元组中的位置最后到了那以及偏移量就行了。

提交记录：https://codeforces.com/contest/1458/submission/330299272

---

Cloyster

交互。$n\times n$ 的矩阵，每个格子有互不相同的正整数值你不知道。除了最大值所在的格子，每个格子都存在一个相邻的格子值比自己大。相邻指的是有公共边或点。每次可以询问一个格子上的值，要求出最大值的位置，询问次数 $3n+210$ 次。

非常好题目，考察了基础算法。先问出一列来，把这一列的最大值位置的周围八个格子都问出来，如果最大值在左侧就往左走否则往右走，这样会问 $n\log n+8n<3n+210$ 次。不写了，太屎了。

---

Replace

对于排列 $\{a_n\}$，定义 $f([l,r])=[\min(a_l,\dots,a_r),\max(a_l,\dots,a_r)]$，多次询问 $[l,r]$，求最小的 $k$ 使 $f^k([l,r])=[1,n]$.

引理：对于 $[l_1,r_1]\cap[l_2,r_2]$，那么 $f([l_1,r_1]\cap[l_2,r_2])=f([l_1,r_1])\cap f([l_2,r_2])$。

由此可推广到多个区间以及高次复合的情况，于是选取每个 $[i,i+1]$ 作为答案区间，倍增预处理 $f^{k}([i,i+1])$，st 表做到 $O(1)$ 查询。

提交记录：https://codeforces.com/contest/1707/submission/330310685

---

四舍五入

对于 $x$，操作最小次数成为 $y$。操作形如选择一个不超过 $m$ 的进制 $k$，将 $x$ 写为 $k$ 进制形式然后四舍五入将末尾变成 0。

我们发现能形成 $y$ 的 $x$ 是连续的，所以倍增预处理 $f^k(l,r)$ 表示 $[l,r]$ 中的数进行 $k$ 次逆操作之后的区间，用 st 表维护即可。

提交记录：https://qoj.ac/submission/1237065

---

[ZJOI2020] 序列

正整数序列，每次操作可以选择一个区间给其中所有数/下标为奇数的数/下标为偶数的数减一，求最少多少步使序列中数全为 0.

神秘的题目就是神题！不妨先考虑较为容易的 $a_1$ 的情况。我们称连续的区间为直线，其余为跳线，考虑一步步将 $a_1\leftarrow a_1-1$，那么如果 $a_2>0$ 那么一定选直线否则选跳线，正确性显然。考虑后面的一个点 $i$，他前面有若干条线可以向后延伸，这些线能用就用因为不会付出额外代价，如果它们数量小于 $a_i$ 那很好说，要考虑的是直线数量 $A$ 和跳线数量 $B$ 的和超出了 $a_i$ 的情况，设 $k=A+B-a_i$，表示可以有 $k$ 条免费的线从位置 $i$ 开始，让后面决定这些线是直线还是跳线，所以 $a_i\leftarrow a_i+k$，这样 $a_i$ 也可以直接处理了，时间复杂度线性。

这个题还可以线性规划爆裂狮子然后搞一个常数巨大的 dp，很不优，严格劣于人类智慧！

提交记录：https://qoj.ac/submission/1237434

---

Topforces Strike Back

$n$ 个数，最多选 3 个，使它们之间两两不是倍数关系，最大化和。

最大的数 $mx$ 无论如何要选，除非同时存在 $mx/2,mx/3,mx/5$，因为有且仅有着一种情况的和大于 $mx$。

提交记录：https://codeforces.com/contest/1183/submission/330282793

---

Survey in Class

在 $n$ 个区间中选 $a,b$ 两个区间使 $|a|-|a\cap b|$ 最大。

如果 $a$ 在 $b$ 左边那么 $b$ 可能是右端点最小/左端点最大的区间，对于完全包含的区间答案则是长度最小的区间，对于每个 $a$ check 这三种情况的答案即可。

提交记录：https://codeforces.com/contest/1834/submission/334497978

---

[SCOI2016] 萌萌哒

字符串长为 $n$，$m$ 条限制形如 $[l_1,r_1],[l_2,r_2]$ 指这两个子串完全相同， $\Sigma=10$，字符串第一个字符不能是 0，求方案数。

暴力就是对于区间内每一对对应的点都在 DSU 上 merge 起来，答案是 $9\times 10^{|S|-1}$，这里使用倍增并查集优化。具体的，$f(i,k)$ 表示 $i$ 开始长为 $2^k$ 的序列中所有点所在集合的根的左端点，求答案的时候因为我们只关心 $k=0$ 的情况，所以从最长的区间开始把区间裂开就可以。

提交记录：https://qoj.ac/submission/1237816

day 2

模拟赛

T1

求对每一个 $l\leq r$ 删除其中字符串后生成的所有字符串中本质不同的字符串的数量。

$$Ans=\frac{n(n+1)}{2}-\sum_{a}^z\frac{c(c-1)}{2}$$

---

T2

$n$ 个点 $m$ 条边的无向连通图，每条边边权为 1，每个点有颜色为黑或白，建立新图包含所有黑点，边权是原图上最短路，求新图最小生成树。

从每个黑点开始 01bfs 把第一个遇到的点扔到联通快里然后跑 Kruscal 就行了，但是我数组开小卡了半个上午。

---

T3

序列，维护区间覆盖/区间取 gcd/求区间 gcd。

维护 lcm，gcd，sum 一车可能有用的信息然后算复杂度就做完了。

---

T4

困难，不会。

讲课：构造

Colorful Graph

有若干个点，共有 n 种颜色，第 i 种颜色有 $a_i$ 个点。需要给这些点之间连边，使得同色的点之间的距离大于等于 d 或者不联通。求最大边数。$n\leq 500000,a_i\leq 1000000000$.

d=1 时直接连完全图，d=2 时所有不同色的点两两连边,$d\geq 3$ 的时候直接连成若干个颜色互不相同的完全图，因为对于当前的团想要拉进来一个新的点会让边数减小。

提交记录：https://qoj.ac/submission/1240134

---

Powers of Two

序列 $c_i=2^{a_i}$，分别有 $x,y,z$ 个符号 $\text{AND,OR,XOR}$，$x+y+z=n$，随意摆放 $\{c_n\}$ 和符号，初始答案为 0，然后从左往右执行符号所对应的操作，求最终的值的最大是多少并给出构造方案。

我就放这了，有谁想陶吗？反正我不想陶。

---

Errich-Tac-Toe

给定一张 n 行 n 列的棋盘，每个格子可能是空的或包含一个标志，标志有 X 和 O 两种。如果有三个相同的标志排列在一行或一列上的三个连续的位置，则称这个棋盘是一个胜局，否则称其为平局。一次操作中，你可以将一个 X 改成 O，或将一个 O 改成 X。设棋盘中标志的总数为 k，你需要用不超过 $\lfloor\frac{n}{3}\rfloor$ 次操作把给定的局面变成平局。

参考资料：信息学奥赛中构造题的常用解题方法——蒋凌宇

我们按 $i+j\bmod 3$ 的值将分为 0/1/2 三类，我们有三种合法的方案：

• 第 0 类上的 X 改成 O，第 1 类上的 O 改成 X
• 第 1 类上的 X 改成 O，第 2 类上的 O 改成 X
• 第 2 类上的 X 改成 O，第 0 类上的 O 改成 X

我们发现这三种方案的操作数的和正好是 $k$，由鸽巢原理，得到最小的代价必然满足要求。

提交记录：https://codeforces.com/contest/1450/submission/334639552

day 3

模拟赛

T1

文 艺 平 衡 树。

---

T2

起点 $S$ 和终点 $T$ 之间有三条长度不一的链，有 $m$ 条额外的边，现在有恰好三条不同的道路正在维修，维修期间不得通行，于是你需要求出，有多少种维修的方案使 $S,T$ 不连通。

必要的观察是删除的三条边一定分别在三条主干道上，并且如果有 $(S,T)$ 这样一条边那么答案是 0。对于主干道内部相连的点把他们中间的扔掉，用差分前缀和就可以快速询问主干道的某个区间有多少边可以割。对于额外边相当于限制主干道要么都割在左边或右边，考察具体的某一条便，相当于限制另一条主干道的割只能在 $[l,r]$ 内。预处理 $x$ 主干道上一个区间在 $y$ 主干道上的影响 $[l_i,r_i]$，四个指针表示 1 主干道限制了 2/3 主干道的区间，枚举 1 的时候指针右移，时间复杂度 $O(n+m)$。

ppt 里面的另解没看懂，感觉很假。

---

T3

$n$ 个开区间，每次操作可以将其向左/右平移一个单位。这 n 个区间是“美观的”当且仅当不存在任意两个开区间有交。这 n 个区间是“好的”当且仅当有一个公共点，初始时它们是好的，求最少多少次操作后会是美观的。

最后区间的情况肯定是每个区间都是首位相连中间没有空，找到每个区间都覆盖的点 $P$ 把它平移到原点。如果 $n$ 是奇数，那么一定存在一个区间不动，否则加上区间 $(0,0)$ 即可，设为 $Y$。考虑左边的区间从左到右的序列是 $P$，右边的区间从右到左构成的序列是 $Q$，那么答案就是

$$\sum(r_{P_i}+i\times(r_{P_i}-l_{P_i}))+\sum(-l_{P_i}+i\times(r_{P_i}-l_{P_i}))+(-l_Y\times|P|+r_Y\times|Q|)$$

由排序不等式得 $P,Q$ 肯定是等长并且单调递减，设 $dp(i,j,0/1)$ 表示前 $i$ 个区间选 $j$ 个放左边的，是否确定 $Y$ 的答案就能 $O(n^2)$ 转移了。

讲课：数论与计数

Part 1. 数论

补习

看我讲数论的博客吧。

题目

[SNOI2019] 数论

以 $\operatorname{lcm}$ 为周期，每个周期直接算，考虑最后的散段怎么做。考察一个经典结构，对于 $[0,Q-1]$ 中的数建立一个点，每个点向 $(i+P)\bmod Q$ 连边，那么整个图会被分为 $\gcd(P, Q)$ 个环，每个环的点数是 $\dfrac{\operatorname{lcm}(P,Q)}{P}$。假设 $P\leq Q$，在这个结构上考虑问题，枚举 $a_i$，我们要找 $a_i$ 这个环上有多少个 $b$，在环上做前缀和就可以了。

---

HDU 5728（共加五个 0）

相较原题 $n\leq 10^{10},m\leq 10^9$。

对于 $\sum \varphi(in)$ 经典做法是

$$\sum_{i=1}^m\varphi(in)=\sum_{i=1}^m\dfrac{\varphi(i)\varphi(n)}{\varphi(\gcd(i,n))}\gcd(i,n)$$

然后各种经典套路往里扔，最后推出来

$$Ans=\varphi(n)\sum_{T|n}(\sum_{d|T}\dfrac{d}{\varphi(d)}\mu(\dfrac{T}{d}))(\sum_{i=1}^{\lfloor\frac{m}{T}\rfloor}\varphi(iT))$$

而 $\mu^2(n)=1$ 告诉我们 $n$ 没有平方因子，于是对于 $d$ 可以预处理每个因子 $d$ 的价值，左边那一坨直接 $O(3^{\omega(n)})$ 剥蒜，右边的地柜下去知道 $n=1$ 是跑一遍杜教筛就做完了。

---

CF1656H Equal LCM Subsets

设 $a_i=\prod\limits_{j=1}^{k_i} p_j^{\alpha_j}$，若 $\alpha_i > \max\limits_{x \in S_B} \{\log_p x\}$，那么 $a_i$ 就只能删掉了。定义 $v_p x$ 表示 $x$ 的质因数分解中 $p$ 的指数。则该条件可表示为：

$$\forall x \in S_A,\forall p,\exists y \in S_B,v_p x \leq v_p y$$

$$\iff \forall x\in S_A,\forall p,\exists y \in S_B,v_p x=\min(v_p x,v_p y)$$

$$\iff \forall x \in S_A,\forall p,\exists y \in S_B,v_p \frac{x}{\gcd(x,y)}=0$$

$$\iff \forall x \in S_A,\forall p,v_p( \gcd\limits_{y \in S_B} \frac{x}{gcd(x,y)})=0$$

$$\iff \forall x\in S_A \gcd_{y\in S_B}\frac{x}{\gcd(x,y)}=1$$

暴力判断显然过不了。考虑到我们的操作其实是求 $\gcd$，单点删除。对于每个 $a_i$ 和 $b_i$ 维护一颗 seg，对于 $a_i$ 的这棵 seg，每编号为 $j$ 的叶节点维护 $\frac{a_i}{\gcd(a_i,b_j)}$，单点删除就相当于把这个点的值改为 $0$。复杂度 $O(n^2 \log n \log V)$，其中 $\log V$ 是 $\gcd$ 的复杂度，用 pbds 可能能把这个消掉。

---

CF1034C Region Separation

设权值和为 $S$，分成 $k$ 份，那么 $u$ 的父边需要被断掉当且仅当 $s_u\bmod S/k=0$，考虑求 $f_k$ 表示多少个 $u$ 满足条件，则符合约束当且仅当 $f_k=k$，考虑求 $f$，等价变化一下，条件等价于 $S/k|\gcd(s_u,S)$，进一步等价于 $\frac{S}{\gcd(s_u,S)}|k,k|S$,然后将所有 $\frac{S}{\gcd(s_u,S)}$ 标记出来做 Dirichlet 前缀和即可。

Part 2. 计数

容斥原理，子集反演

---

「CSP-S 2019」Emiya 家今天的饭

第三个限制很愤怒（do_while_true 原话），考虑容斥，发现只用容斥一层就可以，考虑枚举不满足的，对于当前情况 dp。设 $dp(i,j,k)$ 表示前 $i$ 个烹饪方式，做了 $j$ 道菜，第 $x$ 道菜用了 $k$ 次的方案数，对答案的限制是 $k>(j-k)$，发现具体的 $k$ 的大小并不是我们关心的，所以将 $j$ 这一维改成 $k-(j-k)$ 的值，这样时间复杂度变成了 $O(n^2m)$。

---

「2021 山东三轮集训 Day2」体育测试

给定序列 $\{a_n\}$，求合法排列 $p$ 的数量满足：

• $a_i>0$ 则 $i$ 在 $p$ 中出现位置 $\leq a_i$；
• $a_i<0$ 则 $i$ 在 $p$ 中出现位置 $\geq |a_i|$。

如果 $a_i$ 均非负，那么把 $a$ 从小到大排序，方案数就是 $\prod(a_i-i+1)$。

对于 $[\geq |a_i|]$ 的限制，转化为 $[\leq |a_i|-1]$。我们钦定集合 $S$ 中的 $\geq$ 条件不满足，剩余的不管，它的容斥系数是 $(-1)^{|S|}$，把 $S$ 中的 $a_i$ 和所有大于 0 的 $a_i$ 放一块按上面的方法做，对于剩下的乘个 $(n-|S|)!$ 就行了。

根据这个容斥列 dp。设 $dp(i,j)$ 表示考虑完了前 $i$ 个 $a$，钦定 $j$ 个 $\geq$ 是不合法的，其带着容斥系数的方案数是多少。$\leq$ 直接转移，$\geq$ 要多带一个容斥系数，统计答案的时候求 $\sum dp(n,i)(n-i)!$ 即可。

---

常见 ogf

$$<1,-1,1,-1,\dots>=\frac{1}{1+x}$$

$$\sum\_{i=0}\binom{n+i-1}{i}x^i=\frac{1}{(1-x)^n}$$

---

多项式推理法

两个 $\leq d$ 次的多项式如果有 $>d$ 个点点值相同，由于差是 $\leq d$ 次的，而非 0 的 $d$ 次多项式最多有 $d$ 个零点，这说明两个多项式的差恒为 0，处处取值相等。用处是对于组合恒等式可以先证明正整数位置上均成立，然后多项式推理法说明对任意整数均成立。

---

线性递推。

假设答案的 ogf 是 $F(z)$，若 $F(z)=\dfrac{P(z)}{Q(z)}$，则 $Q(z)F(z)=P(z)$ 分别提出 $[z^n]$ 项，可发现是一个线性递推，现在来直接计算 $[z^n]\dfrac{P(z)}{Q(z)}$。把分子分母同时乘上 $Q(-z)$ 得到 $[z^n]\dfrac{P(z)Q(-z)}{Q(z)Q(-z)}$，这时分母的奇数项都变成了 0，这样算除法的时候分子的奇数项和偶数项之间就独立了。假设 $n$ 是奇数，那么分子项只有奇数项有用，可以看成 $[z^n]\dfrac{zU(z^2)}{V(z^2)}=[z^{\frac{n-1}{2}}]\dfrac{U(z)}{V(z)}$，这里 $U(z)$ 是 $P(z)Q(-z)$ 把奇数项取出来然后从 0 往后排得到的多项式。偶数项的递归是类似的，这样时间复杂度就是 $O(k\log k\log n)$ 的。

//[x^n]p(x)/q(x)
using Poly=vector<int>;
auto adjust=[&](Poly &f,int o){int i;for(i=o;i<(int)f.size();i+=2)f[i/2]=f[i];f.resize(i/2);};
while(n)
{
 int o=(n&1);n>>=1;Poly rq=q;
 for(int i=1;i<(int)rq.size();i+=2)rq[i]=del(0,rq[i]);
 q=q*rq;adjust(q,0);p=p*rq;
 if(!o)adjust(p,0);else adjust(p,1);
}
if(p.size())wr(1ll*p[0]*qpow(q[0],mod-2)%mod),pn;
else puts("0");

---

Matrix-Tree 定理

无向图 $G=(V,E)$ 的 度数矩阵 $D$ 为 $D_{i,i}=\operatorname{deg}(i),D_{i,j}=0(i\not=j)$。记 $G$ 的邻接矩阵 $A_{i,j}=\# e(i,j)$，定理 Laplace （拉普拉斯）矩阵 $L=D-A$，也称 Kirchhoff（基尔霍夫）矩阵，记 $L$ 去掉第 $i$ 行第 $i$ 列后的矩阵为 $L'$，Matrix-Tree 定理说的就是 $G$ 的生成数个数为 $\det L'$，即 $L$ 的 $n-1$ 阶主子式。

对于有向图的情况，设 $L_{\text{out}}=D_{\text{out}}-A$ 与 $L_{\text{in}}=D_{\text{in}}-A$，定理形式为：

• 对于一个根 $x$，以 $x$ 为根的外向生成数个数为 $\det L_{\text{in}}'$
• 对于一个根 $x$，以 $x$ 为根的内向生成树个数为 $\det L_{\text{out}}'$

考虑不严格的证明。这里直接证明有向图的情况，考虑以 $x$ 为根的内向树，生成树的经典方式是对于 $x$ 以外的点 $y$ 确定一个 $fa$ 并且不构成环。考虑容斥，生成了多少环容斥系数就是 $-1$ 的多少次方。考虑钦定若干个环剩下的随便连。尝试将其与 $n-1$ 阶主子式联系起来。考虑一个排列 $a$，如果排列中 $a_i=i$ 说明 $i$ 的 $fa$ 随便连，方案数为其出度；一个大小为 $k$ 的环给逆序对奇偶性带来的贡献是 $(-1)^{k-1}$，然后边权乘积是 $(-1)^k$，这样就凑出容斥系数来了。

day 4

模拟赛

省流：MikeFeng 没有唱歌，严厉谴责！！！

---

T1

有根树，每个点有颜色 $a_i$，求每个子树中颜色出现次数的中位数乘 2.

dsu on tree 板子。

另解：特判阳历然后全输出 2。

---

T2

$n$ 条边 $(u_i,v_i,w_i)$，一开始图是 $h$ 个点，边权为 0 的完全图，$m$ 次询问，每次寻味添加编号 $l,r$ 之间的边后图的最大生成树的边权和。

猫树板子，但是 ST 表比猫树块，只不过需要卡空间，具体方法是利用 vector 动态分布内存。场上不会这个直接挂成暴力分了。代码如下：

using poly=vector<int>;
struct table
{
 poly pos; vector<poly>f; int st[N],ed[N];
 inline void build()
 {
  int siz=pos.size(),lg=__lg(siz);f.resize(lg+1);
  fo(i,0,lg)f[i].resize(siz+1); fo(i,1,siz)f[0][i]=e[pos[i-1]].w;
  fo(i,1,lg)fo(j,1,siz)if(j+(1<<i)-1<=siz)f[i][j]=max(f[i-1][j],f[i-1][j+(1<<i-1)]);
  fo(i,1,n)st[i]=ed[i]=-1;
  int j=0; fo(i,1,n){if(pos.back()<i)break;while(pos[j]<i)++j;st[i]=j+1;}
  j=siz-1; Fo(i,n,1){if(pos.front()>i)break;while(pos[j]>i)--j;ed[i]=j+1;}
 }
 inline int qry(int l,int r){int k=__lg(r-l+1);return max(f[k][l],f[k][r-(1<<k)+1]);}
}tr[55];

---

T3

简单无向图，每个点有颜色 $c_i$ 和权 $w_i$，经过某个点需要花费 $w_i$ 的代价下方一个标记，若 $c_i\not=c_j$ 则 $i$ 处会回收 $j$ 处的标记，要求每刻能量非负，求对于 $x$ 到 $y$ 的最小初始能量。

发现颜色改变时会回收所有标记，先用 $(\min,+)$ floyed 跑出不同色之间的最小距离，然后 $(\min,\max)$ floyed 跑最短路。

---

T4

屎。

兔队板子。

讲课：图论与树上问题

图论：https://www.cnblogs.com/mikefeng/p/18994175
树上问题：https://www.cnblogs.com/mikefeng/p/17459007.html

图论

广义串并联图：不存在同胚于 $K_4$ 的子图的图，人话就是不存在四个点 $a,b,c,d$ 使得这四个点中两两之间都有路径相连并且这些路径互相不交的图。常见的如树，二分图，仙人掌（就是没有一个点在两个环上的图）以及延申。

广义串并联图通过若干次删 1 度点，缩 2 度点，叠合重边，最后一定会仅剩下一个点.碰到广义串并联图可以利用这个方法。

---

[SNOI2020] 生成树

生成树计数直接做最快应该是 Matrix-Tree 定理，这道题想过去需要对图的性质进行分析。原图删边之后是仙人掌告诉我们使用圆方树相关科技是不行的，仙人掌相对更不严格的一个性质是广义串并联图，容易发现这个图是广义串并联图，考虑维护广义串并联图操作。设 $f_e,g_e$ 分别表示 $e$ 这条边在/不在生成树上的方案。删一度点的时候直接将 $f_e$ 乘进答案，缩二度点时 $f$ 相乘，$g_e=g_{e_1}f_{e_2}+f_{e_1}g_{e_2}$，叠合重边的时候这两条边不可能同时存在于生成树上，所以把上个式子里的 $f,g$ 反过来就行了。贴个代码。

const ll N=2e5+5;
ll n,m,ans=1;
map<ll,array<ll,2>> g[N];
queue<ll> q;
signed main()
{
 auto link=[&](int x,int y,array<ll,2> arr)->void
 {
  if(g[x].count(y)){array<ll,2> tmp=g[x][y];g[x][y]=g[y][x]={arr[0]*tmp[0]%mod,(arr[0]*tmp[1]+arr[1]*tmp[0])%mod};}
  else g[x][y]=g[y][x]=arr;
 };
 auto upd=[&](int x)->void{if(g[x].size()<=2)q.push(x);};
 read(n,m);fo(i,1,m){ll u,v;read(u,v);link(u,v,{1,1});}fo(i,1,n)upd(i);
 while(!q.empty())
 {
  int u=q.front();q.pop();
  if(g[u].size()==1)_M(ans,(g[u].begin()->se)[1]);
  if(g[u].size()==2)
  {
   ll x=g[u].begin()->fi,y=g[u].rbegin()->fi;
   array<ll,2> c=g[u].begin()->se,d=g[u].rbegin()->se;
   link(x,y,{(c[0]*d[1]+c[1]*d[0])%mod,c[1]*d[1]%mod});
  }
  for(auto e:g[u]){g[e.fi].erase(u);upd(e.fi);}
  g[u].clear();
 }
 wr(ans);
}

---

删边最短路

https://codeforces.com/problemset/problem/1163/F 是板子题。

分类讨论，如果 $(u,v)$ 不在最短路上，那么它改大了对答案没影响，否则 $ans\leftarrow \operatorname{dis}(1,u)+\operatorname{dis}(v,n)+w'(u,v)$；如果 $(u,v)$ 在最短路上，改小了直接 $ans\leftarrow w'(u,v)-w(u,v)+ans0$，其中 $ans0$ 表示原来的最短路长度。唯一值得考虑的情况是 $(u,v)$ 在最短路上并且改大了的情况。然后这个情况我就不知道了。

---

平面图最小割=对偶图最短路。板子题是 2026 ICPC Beijing R 狼抓兔子但是难点在读入。

树上问题

Archaeology

异 象 石。

---

Surprise me!

莫反套路推得

$$\frac{1}{n(n-1)}\sum_{T=1}^n\sum_{d|T}\frac{d\mu(\frac{T}{d})}{\varphi(d)}\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)\varphi(jT)\operatorname{dist}(b_{iT},b_{jT})$$

不得不枚举 $T$，考虑维护后面的东西。$\sum_{d|T}\frac{d\mu(T)}{\varphi(d)}$ 可以线性筛预处理，后半部分把 $a_i$ 是 $T$ 的倍数的点拉出来建虚树，总共点数是 $O(n\log n)$ 的，我们要求 $\sum_{i=1}^m\sum_{j=1}^m\varphi(i)\varphi(j)\operatorname{dist}(i,j)$，考虑 dp。转移懒得写。

---

Groceries in Meteor Town

既然要算路径上的边权最小值，那么先建出 Kruskal 重构树，然后考虑答案就是 $x$ 与每个白点 lca 的深度最小的点的点权。我们知道，这个点就是 $x$ 与所有白点的 lca 的 lca，由 Company 中的结论，这相当于点集中 dfn 最大点和 dfn 最小点的 lca，seg 动态维护就行了。

---

Campus

考虑怎么做。显然不能动态维护序列值，考虑维护树结构然后查询的时候搞一下。有清零显然离线。对于每个 Class 用森林维护，对于 Class 2，dfs 森林，set 维护第一个会产生贡献的 modify，然后 dfs Class 1 的森林树状数组维护时间 t 时的加法。时间复杂度 $\Theta(n\log n)$。

---

Clockwork Bomb

两边都连对了的自然不用改了，可以把这些缩起来然后随便从一个点开始删就做完了。

---

Cow and Vacation

不会，不如上一个题水黑。

---

String Transformation 2

神秘，不会，挖坑。

day 5

模拟赛

T1

序列，$q$ 次询问 $l_i,r_i$ 内数的乘积是不是完全立方数。

我的做法是数据范围分治+莫队，std 就是把我的莫队改成主席树。赢！

---

T2

给定一个合法的 $\min-\max$ 表达式，其中每个位置的值不确定，$1$ 到 $n$ 各出现一次，求可能取值。

建出操作树来，容易证明每个子树的取值范围是一个连续区间 $[l_i,r_i]$，然后递推。

---

T3

求字典序小于给定序列，长度为 $k$，每个数都为 $[1,n]$ 中整数且它们两两不同的序列个数。

完全无法理解 solution 里面写的是什么。

嗯似乎理解了，大概就是说扫值域然后钦定这个位置前都填满算方案数。

我是奶龙，没看见序列两两不同。

讲课：数据结构

day 6

模拟赛

省流：出成省选场了。

---

T1

给定序列 $\{a_n\}$，你需要从中选出 $k$ 个不相交的连续子段，使每一段长度都是质数，并最小化子段的和的最小值。

二分答案，一个区间 $(j,i]$ 合法当且仅当 $s_i-s_j\geq mid$，扫序列贪心，记前一个选的是 $k$，如果存在 $j\in [k,i)$ 满足 $i-j$ 是质数并且 $s_i-s_j\geq mid$ 那么就一定能划分出一段来。set 维护可选的 $j$，直接遍历，期望 $O(log n)$ 次找到一个质数，时间复杂度 $O(n\log (nV)\log n)$。

---

T2

$k$ 维空间中的 $m$ 个超立方体，每个超立方体用 $[l_1,r_1]\times [l_2,r_2]\times\dots\times[l_k,r_k]$ 表示。认为一个点 $p$ 在超立方体内，当且仅当 $\forall 1\leq i\leq k,p_i\in [l_i,r_i]$。给定正整数 $n,m$，需要求出有多少个超立方体序列 $B_1,B_2,\dots,B_m$ 使得每个超立方体的坐标都是 $[1,n]$ 中整数，并且对任意两个超立方体，不存在点 $P$ 同时属于它们。$1\leq m\leq 6,1\leq n,k\leq 10^9$。

条件相当于 $\forall i1<i2,\exists j,[l_{i1,j},r_{i1,j}]\cap[l_{i2,j},r_{i2,j}]=\emptyset$，存在不好做，容斥转化为钦定若干对 $(i1,i2)$ 不满足上面的条件，其他不管。如果将 $(i1,i2)$ 看作无向图的一条边的话，显然每个连通块是独立的，这 $k$ 维也是独立的，不妨考虑 $k=1$ 的情况，这只需要算出给定若干限制条件 $(u,v)$，选出 $m'$ 个区间使每个条件对应区间都相交的方案数。

但是钦定相交不好维护，我们再做一步容斥，记 $f(S)$ 表示 $S$ 内关系全部有交，别的无交的方案数，$g(S)$ 表示钦定 $S$ 内关系全部无交，别的不管的方案数，另计 $h(S)$ 表示 $S$ 内关系全部无交，$U\setminus S$ 内关系全部无交的方案数，那么 $f(S)=h(U\setminus S)$，并且 $g(S)$ 是 $h(S)$ 的高维后缀和，所以求出 $g(S)$ 再做一遍高维差分就可以了。

考虑求出 $g(S)$。一通尝试之后选择回到值域去求，值域很大但是只有端点有用，而端点的规模是 $2m$，很小，可做。这一步是 D7T2 的完整部分！设 $dp(i,S)$ 表示考虑到第 $i$ 个值，每个区间的状态是未开始/包含这个端点/已结束，然后每个限制条件相当于一些区间不能同时包含这个端点，状态大约是 $O(5^m)$ 的。然后 $g(S)=\sum\binom{n}{i}f_{i,S}$。这样我们就求出了 $k=1$ 的情况，对于多个维度这相当于 $f^k$，考虑 $f$ 的复合，这是 $\text{and}$ 卷积，使用 $\text{FWT}$ 即可。时间复杂度 $O(m2^{m(m-1)/2}5^m)$，实际上跑不满，但疯狂卡才卡过去。

---

T4

给定字符串 S = S1_S_2\dots S_n，有 q 次询问，每次给定区间[l, r]，你需要求出有多少个 k ∈[l, r −1]，使得 $S_lS_{l+1} \dots S_k$ 以及 $S_{k+1}S_{k+2}\dots S_r$ 两个字符串都是回文串。

我不会 PAM。

讲课：动态规划

[AGC061C] First Come First Serve

考虑一种顺序有两个对应的方案，对于一个不同的 $i$，一定不会有其他人在 $(a_i,b_i)$ 中选择，此时 $i$ 选 $a_i,b_i$ 对顺序没有影响，尝试建立顺序到字典最小的方案的映射，可以认为每个顺序对应的选择方案是对于每个选了 $b_i$ 的 $i$，$(a_i,b_i)$ 中有被选择的元素，显然这样的方案是唯一的。考虑容斥，对于每个 $i$，可以选择 $a_i$ 或 $b_i$，系数是 1；也可以选择 $b_i$ 并钦定 $(a_i,b_i)$ 中不被选择，系数是 -1，发现对于每次这个情况，都可以确定一个 $[l,r]$ 内的选择情况，注意到这些区间有交的时候贡献是 0，所以只需要考虑无交的情况。我们要求的答案写出来就是 $2^n\sum_{S\subset U}[\forall i,j\in S,N(i,j)]\frac{1}{2}\sum_{j\in S}(r_j-l_j+1)$，其中 $N(i,j)$ 表示 $[l_i,r_i]$ 与 $[l_j,r_j]$ 无交，我们发现这个形式可以 dp，设 $f_i$ 表示分配了前 $i$ 个的方案数，有转移 $2f_i\rightarrow f_{i+1},f_{l_i-1}\rightarrow f_{r_i}$，时间复杂度 $O(n)$。

day 7

模拟赛

T1

有一个攻击力为 n 个怪兽，你可以做若干次操作，每次选择如下两种之一：

• 将怪兽的攻击力增加 k，k 是一个给定的值。
• 将怪兽的攻击力变为原先攻击力在十进制下的数位和。
  请求出，怪兽的攻击力最小可以变成多少，以及变成这个最小值至少需要做多少次操作。

观察到次数不超过 11，直接爆搜。

---

T2

有 m 个程序，你为了测试它们的正确性，造了 n 组数据。设第 j 个程序在第 i 组数据上的运行结果是 stat(i,j) ，花费的时间是 tc(i,>j) ，空间是 mc(i,j) 。运行结果有如下几种：

• OK：该程序通过了该组测试数据；
• WA/RE：该程序在此数据上答案错误或运行时错误；
• TL：该程序在此数据上超出时间限制，此时一定有 tc(i,j) = 10001；
• ML：该程序在此数据上超出空间限制，此时一定有 mc(i,j) = 10001。

在 OJ 上，提交第 j 个程序的用户所看到的结果是：

• 若所有数据的状态都是 OK，则结果是 OK，花费的时间和空间是所有数据时间或空间的最大值；
• 否则，设编号最小的状态非 OK 的数据编号是 i，结果是该数据的状态，花费的时间和空间是数据编号在 [1, i] 中的所有数据花费的时间和>空间的最大值。

很不幸的是，你造的数据太多，把 OJ 卡爆了。因此，你需要缩减一部分数据。你需要求出，最少需要保留几组数据，使得在仅保留这些数据的情>况下，所有程序的运行结果都不变。你可以删去一部分数据，也可以将剩下的数据重新排列。你必须保留至少一组数据。

首先发现多次添加相同的数据肯定不优，所以限制每组数据最多选 1 次。考虑维护添加了一部分数据后的信息，发现只需要维护 $(S_1,S_2,S_3)$ 分别表示跑到非 OK 的点/最大时限的点/最大空间限制的点的代码集合，并且 $S_1\not\subset S_2$ 或 $S_1\not\subset S_3$ 的状态都是没有意义的，状态数变成 $5^m$，通过预处理可以做到 $O(n5^m)$。

---

T3

$n$ 个点有点权 $R_1,\dots,R_n$，$R_0=R_{n+1}=\infty$。考虑以下过程：

初始时在点 $x$，设左边第一个没被访问过的点为 $l$，右边第一个没被访问过的是 $r$，你需要不断做如下操作，直到访问所有位置，设 $E_x$ 为最小代价。

• 访问 l 或 r，要求权值大于 $R_l,R_r$，代价为 1.
• 权值付为 $\min(R_l,R_r)$，代价为 $k$

q 次操作，每次交换 $R_i,R_{i+1}$ 或查询 $[l,r]$ 内 $E$ 的和。

访问的代价是恒定的 $n-1$，因此只用算更改权值的代价，设为 $f_i$，设 $A_i$ 表示 $[1,i]$ 中后缀最大值的集合，$B_i$ 表示 $[i,n]$ 中前缀最大值的集合，那么 $f_i=|A_i\bigcup B_i|-1$。考虑一个位置值的改变会对多少 $A_i,B_i$ 产生影响，这样交换的时候就需要减去原来的影响，交换过来再加上现在的影响。一个位置 $i$ 在 $b_j$ 中，当且仅当 $\max_{k=j}^iR_k< R_i$，于是可以线段树二分出最左端的位置 $l$，此时只需要讨论 $[l,i)$ 中的点的 $A$ 是否包括了 $R_i$，发现除非 $R_l=R_i$，$i$ 一定会对其中的 $A$ 有贡献，否则不会产生贡献。对于 $A$ 同理，用线段树维护，从大到小把数据塞进去就行了。

讲课：杂题选讲