11 月做题记录 - 洛谷仓库

P14362 [CSP-S 2025] 道路修复 / road

我们可以发现有很多边是用不到的。然后

2^k

枚举，一边归并一边做 Kruskal。

P14363 [CSP-S 2025] 谐音替换 / replace

意外的简单。

注意到能否替换可以等价于“复合串”（二元组一个字符）的匹配，这个匹配还需要满足一个区间限制。

这里的 AC 自动机要使用简化版 + map，可以用势能分析出复杂度是正确的。

O(L \log |\Sigma|^2)

。

P14364 [CSP-S 2025] 员工招聘 / employ

一道纯粹的数数题。

做法一：直接 DP

最朴素的想法是使用

f_{i,j}:=

前

i

天，寄

j

人的方案数。但是显然没办法转移，因为我们不清楚我们可以选哪些人。

考虑加入

k

表示有多少人

c > j

，这样我们起码知道下一天有几种选择。

cnt_j :=

有多少

c=j

，

suf,pre

分别为后缀、前缀和。

$s_{i+1}=1,c>j$ ， $f_{i,j,k} \times (suf_{j+1}-k) \rightarrow f_{i+1,j,k+1}$ 。
$s_{i+1}=1,c\le j$ ， $f_{i,j,k} \times (pre_j-(i-k)) \rightarrow f_{i+1,j+1,k-l}$ ，其中 $l$ 为前 $i$ 天 $c=j+1$ 的人的个数，显然这个信息是无法获知的，故该方法倒闭。

我们发现想要转移，我们仅需要知道

c>j

的人的个数，还要知道

c=j+1

的人的个数，如此下去需要记录所有的

c

的取值，退化为暴力。

于是考虑一个经典 trick：贡献延后计算。

对于

c>j

的那些天，我们不确定具体是哪些人，而是留下空槽，这样到后面结算贡献的时候可以自由地安排哪些是

c=j+1

的。

故

f_{i,j,k} :=

前

i

天，寄

j

人，留

k

个空位，且非空位处都有

c\le j

，的方案数。

$s_{i+1}=1,c>j$ ， $f_{i,j,k} \rightarrow f_{i+1,j,k+1}$ 。
$s_{i+1}=0,c>j$ ， $f_{i,j,k} \times \binom{k}{l} \times \binom{cnt_{j+1}}{l}l! \rightarrow f_{i+1,j+1,k+1-l}$ 。
$c\le j$ ， $f_{i,j,k} \times \binom{k}{l} \times \binom{cnt_{j+1}}{l}l! \times (pre_j - (i-k)) \rightarrow f_{i+1,j+1,k-l}$ 。

做法二：容斥转 DP

https://www.luogu.com.cn/article/6jgvpe05

P12966 [CCO 2025] Asteroid Mining

与 AT_arc201_b 十分相似。

小结：考虑哪些情况一定要拿是对的，但是考虑大的并不能确定出来，要考虑小的。而且一些问题的显然简化没有去做，比如最小体积化成

1

。

CF1988F Heartbeat

数数题。

f_{n,x,y} :=

1 \sim n

的有

x

个前缀最大值，

y

个上升点的排列个数。

g_{n,x,y}

为后缀，可以对称。

转移考虑插入

1

的位置即可。

统计答案枚举最大值的位置，左右合并，要进行大量预处理优化。

ans_n = \sum_{p=1}^n \sum_{i=0}^{p-1} \sum_{j=0}^{n-p} \sum_{x=0}^{p-1} \sum_{y=0}^{n-p} \binom{n-1}{p-1} f_{p-1,i,x} \cdot g_{n-p,j,y} \cdot a_{i+1} \cdot b_{j+1} \cdot c_{x+y+[p>1]}

显然我们需要用一些和式技巧提出一些部分进行预处理，这是经典方法。

这里可能会有把

n

看作常量还是变量的问题，如果拿不准，看成变量是一定不亏的。

ans_n = \sum_{p=1}^n \sum_{j=0}^{n-p} \sum_{x=0}^{p-1} \sum_{y=0}^{n-p} \binom{n-1}{p-1} g_{n-p,j,y} \cdot b_{j+1} \cdot c_{x+y+[p>1]} \sum_{i=0}^{p-1} f_{p-1,i,x} \cdot a_{i+1}

记

u_{p-1,x} = \sum_{i=0}^{p-1} f_{p-1,i,x} \cdot a_{i+1}

。类似的，记

v_{n-p,y} = \sum_{j=0}^{n-p} g_{n-p,j,y} \cdot b_{j+1}

。

\begin{aligned} ans_n &= \sum_{p=1}^n \sum_{x=0}^{p-1} \sum_{y=0}^{n-p} \binom{n-1}{p-1} u_{p-1,x} \cdot v_{n-p,y} \cdot c_{x+y+[p>1]} \\ &= \sum_{p=1}^n \sum_{y=0}^{n-p} \binom{n-1}{p-1} v_{n-p,y} \sum_{x=0}^{p-1} u_{p-1,x} \cdot c_{x+y+[p>1]} \end{aligned}

记

w_{p,y} = \sum_{x=0}^{p-1} u_{p-1,x} \cdot c_{x+y+[p>1]}

。

最终

ans_n = \sum_{p=1}^n \sum_{y=0}^{n-p} \binom{n-1}{p-1} v_{n-p,y} \cdot w_{p,y}

小结：考虑求满足某要求的排列个数是正确的，按值域顺序，从“插入”角度对排列进行 DP 也是正确的，也想到了以最大值为分界左右合并，但我是插入

n

，而不是

1

，这样转移方程十分复杂。

P10067 [CCO2023] Real Mountains

首先发现最终结果是唯一的，以最大值为分界，左边取前缀 max，右边取后缀 max。

注意从最小的没有达到目标的数开始，然后按值域做类似观草的扫描线。

P1972 [SDOI2009] HH 的项链

经典题。

之前我以为数据结构里抽象的扫描线和求矩形面积并的扫描线是不同的东西，其实把信息放到二维平面上就发现是一样的了。

当然这道题可以用二维平面也可以不用。

P3582 [POI 2015 R1] 影迷 Movie-goer

和 P1972 差不多。

P2824 [HEOI2016/TJOI2016] 排序

考虑二分答案（不太容易想到），我们可以判断第

q

位的值和

mid

的大小关系，具体的，我们把

\ge mid

的记为

1

，

< mid

的记为

0

。

P6090 [CEOI 2019] 立方填词

我是先考虑了二维的问题。

我们发现以

4

个对顶的点为中心，可以用

4

个三叉结构拼成一个立方体，可以记

f_{a,b,c}

表示三个分叉的顶端字母分别为

a,b,c

的方案数。统计也是简单的。

AT_m_solutions2019_e Product of Arithmetic Progression (NOIP 1 T2)

显然

a,d

可以先对

P

取模。

对于

d=0

，

ANS=a^n \bmod P

。

否则

(d,P)=1

。

若

d=1

，可以用阶乘实现，否则因为

d

存在逆元，可以把

d

提出来，

ANS=d^n \prod_{i=0}^{n-1}(\frac{a}{d}+i) \bmod P

。

在

n

比较大时

ANS=0

。

加强版：模数变为合数。

首先用 CRT 转为模质数幂，记为

p^k

。然后把

d

中的

p

提出来，

d=d' \times p^l

，

d'

有逆元可以提出。

问题变为

\prod_{i=0}^{n-1}(a+i\times p^l) \bmod p^k

。

对于每个

a

，数列

(a+i\times p^l)\bmod p^k

的循环节为

p^{k-l}

，我们考虑对每个

a

预处理数列，但

a

比较大，我们对

a

做带余除式

a=a'+c \times p^l, a' \in [0,p^l)

。

(a'+c\times p^l + i\times p^l)=(a'+(i+c)\times p^l)

。

问题变为

\prod_{i=l}^r (a+i\times p^l) \bmod p^k

。

看起来和原来区别不大，但是

a

变小了，序列总长度为

p^l \times p^{k-l}=p^k

。

查询类似分块，散块可以用线段树之类的数据结构，有

O(1)

做法，类似阶乘相除，但我不会。

NOIP 1 T3

题面。

考虑直接用线段树。但是原问题不好直接维护，可以用容斥进行转化，

ANS=\text{总区间数}-\text{不包含某个数的区间数}+\text{只包含某个数的区间数}

。

然后直接线段树做即可。

同余最短路：P2371 [国家集训队] 墨墨的等式

跟牛场围栏几乎一样，但是太久没碰同于最短路没反映过来。

我们要求的是“能组合出多少种数字”，但是这个数字的范围太大了，考虑利用模术缩小范围。具体地，如果

b

能被表示出，那么

b+i\times a_k

，其中

k

是某个固定的数。

于是我们只需要求出模

a_k

余

0 \sim a_k-1

的最小数即可，可以用最短路求解。

证明题：P3907 环的异或

我们将一个非树边和若干树边构成的环称为基本环。

结论：任意环可以由基本环做异或（对称差）得到。

证明：我们考虑任意一个环，不断重复如下操作：选择一个非树边，用该边对应的基本环与之做异或。由于每个非树边只被反转一次，且每次操作完剩余的图仍然是环，所以最终一定留下了一个空图。该过程的逆过程就是由基本环构建环的过程。

TC 选择将环的拓宽成允许重边，本质是一样的。

NOIP 2 T3 飞翔 (fly)

题面。

这种变种的 MST 最短路，一般来说，要么是魔改经典算法，要么是建图。

这题建图可以拿 80pts（他们称为分层图）。

正解需要魔改 Dijkstra。

我们思考 Djikstra 做了什么：

选择 $dis$ 最小的点，它不会被更新得更小，所以最优。
用其更新其他相邻点的 $dis$ 。

观察这道题的答案结构，发现形如 xxxxyyyyyzzzz...，其中

x>y>z

，且每一段的段首一定是原图的边对应边权。原本的 Djikstra 是更新相邻的点，而这里我们用邻边更新所有点。具体地，假装所有边都变成邻边的边权，往后更新。

这样算出来的

dis

表示的路径形式如上，但可能比合法路径要大，但是显然其中最小的一定是合法的。正确性同 Dijkstra（也许只要

dis

通过更新递增都是正确的？）。

注意：不要忘记暴力的 Dijkstra，其在稠密图上优于堆优化的。

经典题：k 小区间中位数

题意：有

n

个数

a_1,\dots,a_n

，求所有区间中位数中第

k

小的值。

先提一个平均数技术，一个数列可以将每个数减去平均数，使得平均数变成

0

，从而忽略个数限制，例题。

中位数也有相似技术：对于某个

A

，

<A

的记为

-1

，

=A

的记为

0

，

>A

的记为

1

。则中位数为

A

当且仅当和为

0

，中位数

<A

当且仅当和

<0

，中位数

>A

当且仅当和

>0

。

二分答案，查询有多少区间的和

<0

，这个是二维偏序。最终

O(n\log^2 n)

解决。

跟 P2824 非常地像。

小结：对于这两题，都通过将已知信息根据和某个数字

A

的大小关系进行重赋值，从而得到高效的检验方法。

AT_tenka1_2014_final_d 高橋君

首先答案就是组合数求和，接下来要支持多次查询。

这里居然可以使用莫队，首先

k

变动时答案的改变是简单的。

n

变动时使用加法公式即可。

P6076 [JSOI2015] 染色问题

正难则反，我们发现如果考虑某些条件不符合，计数是容易的，然后就是裸容斥。

ANS = (c+1)^{nm} - \sum_{u=1}^{n+m+c} (-1)^{u-1} \sum_{i+j+k=u,i\le n,j\le m,k\le c} \binom{n}{i} \binom{m}{j} \binom{c}{k} (c+1-k)^{(n-i)(m-j)}

复杂度

O(nmc)

。

可以做到

O(nm)

，但我不会。

P6189 [NOI Online #1 入门组] 跑步（分拆数模板）

7 月用五边形数过了这题，现在将一个根号分治的 DP 做法。

我们设

n=a_1+a_2+\dots

，并且

a_1 \ge a_2 \ge \dots

。我们将物品分成两类，

a_i > B

的一类，

a_i \le B

的一类。

我们把

a

放到条形图上考虑，条形图的面积和为

n

。

其中第一类至多

n/B

个，直接完全背包。第二类的值域较小，纵向做完全背包。

B=\sqrt n

，总复杂度

O(n\sqrt n)

。

P11676 [USACO25JAN] DFS Order P

OBS 1：生成树是 DFS 树当且仅当不存在横插边（显然）。

OBS 2：树的 DFS 序可以为

[1,\dots,n]

当且仅当任意子树的编号连续（归纳证明）。

然后我们显然可以先把所有边删掉。

基于如上观察，我们可以进行区间/树上 DP，

f_{l,r}

表示点

[l,r]

构成符合要求的以

l

为根树最小花费。

转移考虑分出一个子树，连树边和非树边。

NOIP 3 T2 很多集合（sets）

题面。

首先我们有暴力，然后如果考虑每个元素在哪些集合，我们就有了另一个暴力。然后发现总和为

2n

，考虑根号分治。

当然如果不能提前预见，也要主动考虑。

然后将集合分成大集合和小集合，以

B

为分界。

查询时，只要其中一个为小集合，就能直接暴力，

O(qB)

。

两个大集合可以

O(n^2 / B^2)

预处理答案，用 map 存。

平衡一下复杂度，大约取

B=(n^2/q)^{1/3}

时最小，这里可以用三元均值（

qB+n^2/B^2=qB/2+qB/2+n^2/B^2 \ge 3\sqrt[3]{q^2n^2/4}

）不等式或者求导。

忽略 map 的 log 是

O(n^{4/3})

。

NOIP 3 T3 子序列们（sub）

题面。相关题目：agc024e、abc435f。

OBS 1：删除连续段中不同位置得到的结果是相等的。

推论：两个答案不同当且仅当生成过程中存在一次删除了不同段中的数。

于是我们的每个答案与每次删段首的删除方案一一对应。

但是删除可能使得段相连，无法高效计算，我们需要重新刻画方案。

经典 trick：用每个位置的删除时间

t_i

来描述一个删除过程，

t

是一个排列。

本题的删除还应满足段首限制，对应到

t

上，就是对于任意

i

，其左边第一个满足

t_j > t_i

的

j

，有

a_i \neq a_j

。

然后考虑 DP 统计合法

t

的个数。我们考虑如何分解子问题，注意如果

t_k

是最大值，那么其左边和右边是互不干涉的，所以使用区间 DP。

而且这题和一般的排列类不同，它的限制条件是跟绝对位置有关的，所以不好一个一个插入。

f_{i,j}

表示在

[i,j]

填入

[1,j-i+1]

，并且

t_{i-1} > j-i+1

的方案数。

f_{i,j} = \sum_{k=i}^j f_{i,k-1} \times f_{k+1,j} \times \binom{j-i}{k-i} \times \left[ a_{i-1} \neq a_k \right]

NOIP 3 T4 五重原题（mex）

题面。相关题目：P7447、P4587。

经典结论：

a

升序排列，若

\forall 1\le i\le n, \sum_{j=1}^{i-1}a_j \ge a_i+1

，则

\left[0,\sum_{i=1}^n a_i \right]

都是可被表示的。

这题不方便排序，我们考虑一个算法：

$x \leftarrow 0$
不断执行： $x \leftarrow \#\{y \mid y\le x+1\}$
答案为 $x+1$

这个迭代轮数是

O(\log V)

的，因为

x

的增长严格快于斐波那契数列，具体地

x_i \ge x_{i-1}+x_{i-2}+2

。

然后使用树状数组套权值线段树可以做到

O(q \log n \log^2 V)

。

运用值域倍增分块优化到

O(q \log n \log V)

：

我们对值域分块：

[1,2),[2,4),\dots,[2^k,2^{k+1})

。

OBS：如果选择了一个块中的元素，则整个块中的元素都会被选择。

引理：若当前答案为

x

，则

\forall u \le x, \sum_{a_i\le u}a_i \ge u

。否则

u

一定不能被表示。

根据引理，设

x+1 \in [2^k,2^{k+1})

。已知

[1,2^k)

中的和

\ge 2^{k}-1

，若

[2^k,x+1]

中有元素

y

，则

x+y+1 \ge 2^{k+1}

，这意味着

[2^k,2^{k+1})

中的数全部被选择。否则若没有元素，算法终止，整个快都没有被选择。

根据这个观察，我们对每个块开一个下标线段树来满足区间限制（树套树的内外两层通常可以调换），需要区间求 min 和 sum。时间

O(q \log n \log V)

，空间

O(n \log V)

。

最后用线段树底层分块把空间优化成

O(n \log V / \log n)

。

P5339 [TJOI2019] 唱、跳、rap和篮球

第一步显然容斥。

$O(n^3)$ 做法：从组合角度计算，

f_{i,j}

表示前

i

个颜色填

j

个空的方案数。

$O(n^2)$ 做法：Meet-in-Middle，和 CSP-S 2022 T1 同款技巧。

枚举

x\in [0,a-u],y\in [0,b-u]

用

1/(x!y!)

给

f_{x+y}

做贡献。然后

u+1

的时候，相当边缘部分被减去。

g

表示后两种颜色，然后组合即可。

P11563 【MX-X7-T4】[LSOT-3] 命运

应该评紫的蓝题。

首先当然建图，

G_p=(V,E_p)

为按

p

建图，

G_a=(V,E_a)

为按

a

建图。

观察一下限制条件的本质是什么：

\left< x,y \right> \in E_p \Rightarrow \left< x,y \right> \in E_a

或

\left< y,x \right> \in E_a

。

于是我们发现

p

边的方向无关紧要，遂改成无向边。然后重边可以删掉一条，这样图中没有二元环了。

接下来我们要求

a

的数量，一个方案包含了对

p

边进行定向，以及连接而外边。

考虑

G_p

中的基环树（未退化为环，可以基自环），它们的贡献是

0

（乘算），树的贡献也是

0

。自环有

1

的贡献，其他环有

2

的贡献。

最复杂的是链，除了定向，还要连边。设有

m

条链，看似答案是

2^m \times m!

，但样例 1 就是错的。

原因是长为

1

的链在连接自己时会算重。

下面的步骤移步容斥原理。

记录一下 flying 老师的思路（虽然对我而言有些不可模仿，非常直觉）：一个二元环算了两次，我们需要

-1

，于是有几个二元环就乘几个

-1

，用二项式系数枚举。

NOIP 4 T3 候车

题面。

首先观察两个人产生矛盾的条件，对一个人我们考虑

4

个属性，

l',l,r,r'

分别表示删掉左边的墙走到的最左位置，不删墙走到的最左位置，不删墙走到的最右位置，删右边墙走到的最右位置。

两个人矛盾，假设

l_1 < l_2

，当且仅当

r_1'>l_2

或

r_1>l_2'

。

我们现在就是选择尽量多的人不产生矛盾。理论上人的个数是无限的，但很多信息是相同的，我们可以只保留一个。

具体地，我们从上到下扫描线就能求出，本质不同的人的个数为

O(n)

。

将人按

l

排序，再 DP 即可，转移的条件是一个二维偏序，利用枚举顺序解决一维限制，再用 BIT 解决另一维即可，这是经典的。

小结：提炼信息。

NOIP 4 T4 并行运算（parallel）

~~我常常追忆过去~~

思路同

O(nq)

一样，需要在修改时维护答案，

O(1)

查询，总复杂度为

O(nq/\omega)

。

把

x

数组转化为

cnt

形式，显然可以模

2

。设当前插入元素为

z

，我们对

x

按

z

分段，即

0,1,\dots,z-1,z,z+1,\dots,2z-1,2z,2z+1,\dots,3z-1,\dots

。

我们维护

ans_z

表示查询

z

时的答案。更新过程显然就是取出

x

的每一段

kz,kz+1,\dots,(k+1)z-1

，加到

ans

的

0,1,\dots,z-1

位。

显然可以使用 bitset 优化，但是需要手写，因为 STL 不支持以

O((r-l)/\omega)

取出

[l,r]

。

P10141 [USACO24JAN] Merging Cells P

和 NOIP 3 T3 子序列们（sub）一样的用时间戳刻画合并情况。这样次一个解就对应一个排列。

我们考虑先枚举答案

ans

，再考虑

f_{l,r}

表示

[l,r]

中

ans

胜出的概率。我们也开始可能会把

ans

放状态里，然后发现转移中

ans

是不变的。

f_{l,r} = \sum_{i=l}^{r-1} \frac{1}{r-l} \left( f_{l,i} [S(l,i)>S(i+1,r)] + f_{i+1,r} [S(l,i)\le S(i+1,r)] \right)

其中

S(l,r)

是区间和。初值为

f_{ans,ans}=1

。

关于推法我个人采用偏组合的方法推导。但大部分人从概率论角度直接相乘，可我感受不出这个正确性。

这样做复杂度

O(n^4)

，不太好优化了。我们从计算角度观察这个 DP 的本质：从

[ans,ans]

到

[1,n]

的路径权值的乘积和。

既然如此，那么反过来计算也是正确的。

g_{l,r}

表示从

[l,r]

走到

[1,n]

的权值乘积和。

并且反过来起点是唯一的

[1,n]

，不需要外层枚举，复杂度

O(n^3)

。初值

g_{1,n}=1

。

g_{l,r} = \sum_{i=r+1}^{n} \frac{1}{i-l} g_{l,i} [S(l,r)>S(r+1,i)] + \sum_{i=1}^{l-1} \frac{1}{r-i} g_{i,r} [S(i,l-1) \le S(l,r)]

其实

g_{l,r}

也有组合意义，就是

[l,r]

中的人胜利的概率（现在我发现这个好像是错的，因为

\sum_{i=l}^{r}g_{i,i} \neq g_{l,r}

）。但这种方法不需要任何思考。

现在做朴素的 DP 优化即可。我们考虑计算顺序为

l

从小到大，

r

从大到小，容易验证这是合法的拓扑序。

这样的优势是

l,r

单独变动的时候，可以利用上一次转移的信息。

r-1

的时候，

i

的范围变化都是单调的。第一个和式可以用后缀和维护，第二个和式可以对每个

r

维护前缀和，在

l+1

时对所有

r

更新。

最终复杂度

O(n^2)

。

AT_arc189_d [ARC189D] Takahashi is Slime

首先贪心地左右合并显然是对的。

做法一：只能说不要轻易打发自己的念头，因为很可能是对的。

非常地像 NOIP 3 T4 五重原题（mex）：考虑一次将所有能吃的吃掉。如果发现一个原本不能吃的现在能吃了，说明下一步大小至少会翻一倍，否则程序终止。

线段树二分可以做到

O(n \log^2 n)

，跳笛卡尔树

O(n \log n)

。但如果想到笛卡尔树，基本就能想到下一个解法了。

做法二：说到表述序列的顺序关系和大小关系，笛卡尔树呼之欲出。

考虑做法一最后一步跳笛卡尔树，一个点最终跳到的位置一定不会超过其父亲最终跳到的位置，要么原地不动，要么继承父亲答案，于是

O(n)

建树 +

O(n)

DFS 一次即可。

AT_abc237_g [ABC237G] Range Sort Query

P2824 的弱化版，求一次

<X

的位置，再求一次

\le X

的位置即可。

CF1418G Three Occurrences

虽然这题不放在二维平面是完全没有问题的，但还是推荐这么做。

首先显然扫描线。

对于每个数，画出包含

0

次或

3

次的区间，然后不同数的集合求交。即求出有多少个位置被覆盖了数字种类数次。

转换成 DS 问题：区间加，区间

=A

的个数。自己做的时候以为树套树就做完了，然后发现其实不能做（说是能规约成矩乘）。

转化为区间最大值的个数即可。这个套路挺重要的，记得之前似乎吃过不会这个的亏，但忘了哪题了，要统计

0

和

1

的次数。

变式问题

问题改为：每个数出现

3

的倍数次。

我们考虑给每种数字对应位循环的赋予权值，使得出现

3

的倍数次和为

0

，否则非

0

。赋

x,y,-x-y

即可，还要选取一个模数

P

。这就是和哈希。

或者用

x,y,x\oplus y

做异或哈希，

x,y

在 ull 范围内随机选取。

然后求和为

0

的区间数即可。

9 月做 AT_abc424_f 的时候发明过和哈希。

关于异或哈西的冲突概率：我们每一个

x,y

都是在

[0,2^64)

中均匀选取，可以证明

x \oplus y

的分布也是均匀的。

考虑一个区间的异或和，设第

i

种颜色为

z_i

，总异或和为

z_1 \oplus \dots \oplus z_k

。每个

z_i

都是从赋的三个数中选出

1

个或

2

个，因此均匀分布，于是

z_1 \oplus z_2

均匀分布，

z_1 \oplus z_2 \oplus z_3

均匀分布。以此类推，区间的异或和是在

[0,2^64)

均匀分布的。

一次区间查询的冲突概率是

1/2^{64}

，

n^2

次有一个

n^2/2^{64}

的上界。冲突率相当小，但如果不用 ull 就不行了。

P12389 COmPoUNdS

先考虑查询，我们需要用线段树维护哈希值，这个套路之前没见过（但想到了）。

修改对区间不好做，我们直接差分变成单点修改。

同样的套路也用于求区间 GCD。

拓展：序列

A

的字典序小于

B

的字典序，当且仅当

A

的差分序列小于

B

的差分序列。

该结论显然可以延申到任意阶的差分和前缀和。

CF1634F Fibonacci Additions

和上一题使用了同样的套路。这里区间加了一个斐波那契数，我们运用

b_i=a_i-a_{i-1}-a_{i-2}

就能把

F_i

给“配平”。

CF1997E Level Up

$O(n \log^2 n)$ 做法：考虑离线枚举

k

，每一次直接主席树二分往后跳，复杂度就是一个调和级数加主席树。注意这个主席树值域在外，下标在内。

$O(n \log n)$ 做法：考虑对问题进行转置，枚举怪物，维护人，即把

1

到

k

看作不同人，怪物放到时间轴上，按时间顺序集体打一个怪物。

一个关键是把人的等级的增长视作连续的，即每次增加

1/k

。

选取任何一个时间切片人的等级都是随

k

的增加递减的。我们发现每打一个怪物，就是选取人的一段后缀，使其等级的分子

+1

。

由于这个单调性，我们实际上可以用线段树维护区间

\max

（一般情况是不可做的）。选取后缀的过程可使用线段树二分。

查询在二分后即可求出。

*CF1784C Monsters (hard version)

感觉挺难的，不知为何评蓝。

P11807 [PA 2017] 抄作业

做法一：主席树维护哈希值并树上二分。

用这个定义 cmp 函数带进 sort，复杂度

m \log m \log n

。

做法二：pp_orange 说未来可能会叫“动态注意力”。

分治，类似 SA 的倍增求法。从中间劈开，左右各求一个

rk

，基数排序。

但如果直接暴力第

k

层总数为

2^km

。

注意没层只有一个数字变动，所以有些相邻段是一样的，我们合成一块。实际上，块的总数为

m

，于是可以

O(m\log n)

。

AT_arc180_d [ARC180D] Division into 3

扫描线。

经过观察，发现答案只会是

[1,n,1]

或者

[n,1,n]

的形态。前一种是简单的，后一种考虑最大值在前一个“n”中（后一个“n”中的 case 可以反向做一遍），答案已经被固定一部分了，设当前查询区间为

[l,r]

，最大值在

x

，那么就是求

a_i + \max(i+1,r)

的最小值。

利用线段树维护答案，

r+1

时用单调栈做区间加更新。

单调栈其实就是模拟求后缀最大值的过程。

Division into 4 也是可以做的，Division into 5 比较困难。

NOIP 5 T2 作业 (homework) 是用到了类似的技巧，退单调栈使用区间加（区间覆盖也能做但十分劣，一般都是区间加更优）。

*CF702F T-Shirts

经典题，可以平衡树直接做，可以证明复杂度正确。

*UOJ979 决战库尔斯克

神仙题。

发现差在两倍以内的时候取模就是相减，由此启发值域倍增分块，块内都是两倍以内。由此确定了一个答案的下界，即每个块的极差。然后枚举模数和块，发现每个块有值的部分至多只跨越两个循环节，然后二分。

小结：一些未知作用的剪纸一定要做，因为可能起到决定性作用。之前做 P12966 和 AT_arc201_b 的使用已经体会过了。

*UOJ462 新年的小黄鸭

DP 状态十分简洁，

f_x

即可。

按深度顺序或 DFS 顺序维护线段树优化 DP。

*QOJ4241 Angle Beats 2.0

4 拆 2，转化为“二选一”模型。

二选一模型：用边的定向来描述选哪个。

*QOJ2554 AND PLUS OR

集合意义上的四边形不等式。

注意四边形不等式的差分理解，十分好记。

*AT_agc017_d [AGC017D] Game on Tree

发现游戏过程类似于在子树上做子游戏，但不完全是，事实上加上

(u,v)

边就完全是了。经过观察可以发现带

(u,v)

子树的 SG 函数值为原值

+1

。

最长上升子序列的另一解法

介绍：

O(\sum_i cnt1_i \times cnt2_i \times \log n)

，其中

cnt1,cnt2

分别为

a,b

中每个数字出现的次数。在排列中表现为

O(n \log n)

，在随机数据下表现优秀。

描述：

f_{i,j}

表示

a_1,\dots,a_i

和

b_1,\dots,b_j

的 LCS，只对

a_i = b_j

有定义。

f_{i,j} = \sum_{p<i,q<j} f_{p,q} + 1

维护一个数据结构，第

j

位表示

f_{i,j}

的最小值，区间求 min 即可。

AT_agc016_d [AGC016D] XOR Replace (NOIP 6 T2)

模拟赛 T2，没做出来，发现 2023 年做过。

一个技巧是把异或和看作第

n+1

个元素，这样会简洁一些，当然没有这个转化也无所谓。

做法一：我的考场做法，似乎也是 23 年做法。直接

b_i \rightarrow a_i

，一个回路对应一系列推挤。

做法二：flying 老师的做法，将相等元素区别开，使用环，并查集合并环。

AT_arc108_f [ARC108F] Paint Tree (NOIP 6 T3)

3 题题解：https://b1bznc26af6.feishu.cn/file/P0ytbIzTqoxeE5xnnpSc8RjlnQc

AT_arc152_f [ARC152F] Attraction on Tree (NOIP 6 T4)

*CF1481F AB Tree