撅逝壕题，拼尽全力无法战胜

Da_Vinci · 2025-01-02 15:15:20 · 个人记录

待补作者已经行将就木（指快要或者已经AFO），不会再补了。

2025.1.2 哈希专题

字符串哈希

CF514C Watto and Mechanism

给出n个模式串，再给m个询问字符串，问是否可以通过改变询问串的恰好一个字符来匹配上任意的模式串。n,m≤3×10^5 ，其中所有字符串的字符属于{'a','b','c'}，且输入总长度 ≤6×10^5。

只需要计算所有的模式串的哈希存储在一个set中，然后对询问串枚举更改哪一个字符并且计算更改后的哈希，在set中查找即可。

这个题卡常见的哈希模数，只需要随机一个大的质数做模数即可通过。

P3763 [TJOI2017] DNA

给出一个模式串S和匹配串T，问S中有多少子串在改变不超过3个字符的情况下可以和T匹配。|S|,|T|\leq 10^5，字符集大小为4。

二分哈希板子题，做3次二分哈希即可，布吉岛为什么有紫。

二分哈希就是二分最大匹配的长度，并且使用哈希来check两个字符串的子串是否相等。可以得到两个字符串的最长公共前缀。

在本题中枚举字符串S的下标，并且拿T进行二分最长公共前缀，匹配失败的时候就跳过那个字母，重新匹配，如果能在3次的二分哈希中匹配完整个T就计入答案。

P2757 [国家集训队] 等差子序列

给定一个[1,n]的排列，问是否存在长度不小于3的等差子序列。多测，n\leq 5\times 10^5。

首先题目可以简化为寻找长度恰好为3的等差子序列。设中项为x，则另外两项就分别为x-k,x+k。要求这两个一个在x左边，另外一个在x右边。暴力枚举很慢，考虑优化。

从左到右的枚举序列，设一个01字符串S，经过一个数a_i就把S[a_i]设为1，那么存在中项为a_i的等差数列的条件就是S关于a_i不对称，可以使用哈希判断，线段树动态维护哈希。

树哈希

树哈希可以用来判断两个树是否同构。

P5043 【模板】树同构（[BJOI2015]树的同构）

给出M个树，第i个树有N_i个节点，对于每个树找出与它同构的最小编号的树，N,M\leq 50。

直接对每次询问做背包显然会超时，考虑先对4种硬币做完全背包，然后对于询问，使用容斥来计算结果就是全部的方案数-一种硬币超过限制的方案数+两种硬币超过限制的方案数-三种硬币超过限制的方案数+四种硬币超过限制的方案数，这样就可以通过本题。

P3270 [JLOI2016] 成绩比较

有n个学生，m门课，以及每门课的最高分u_i 。已知学生B每门课的排名r_i，有k多少学生每门课都比他低，求所有学生得分的情况数的总和，模10^9+7。n,m\leq 100,u_i \leq 10^9,r_i \leq n。

对于本题所求，可以把它分成3个部分：

1. 在n-1个学生中，选择k个每门课都低于B的方案数，显然是C(n-1,k)。

2. 在剩下n-k-1个人中计数有多少种合法方案来指定他们的成绩是否大于B。

对于科目i，成绩比B高的人有r_i-1个，要在那n-k-1个人之中选择，而且每个人都至少要被选择一次。处理这个限制可以使用容斥。记F(p)表示至多有p个人被碾压，这一步总共的方案数。枚举p\in[0,n-k-1)进行容斥就可以求出。

3. 在2的基础上枚举具体分数的方案。

对每一门科目分开讨论，设计函数g(u,a,b)表示有u种可选分数，a个人比B高，b个人比B低。这可以通过枚举B的分数求出，但是由于u的值域太大所以会超时。枚举这n个人有t种不同的得分，就可以使用g(t,a,b)求出。因为g(t,a,b)依然有可能算重，就再次使用一次容斥来去重。即D(t)=(G(t,a,b)−∑ _{i=1}^{t−1}D(i)⋅C(t,i))⋅C(u,t)。

将三种情况来乘起来就可以得到最终的答案。

P4859 已经没有什么好害怕的了

给出长度为n的序列a和b，其中的元素互不相同。将a中的数和b中的数配对，求有多少种情况使得a_i>b_i 的对数比 a_i<b_i的对数恰好多 k，对10^9+9取模。n\leq2000。

由题意不难得出我们要使a_i>b_i的对数为t=(n+k)\div2，看到“恰好”这个性质可以想到要把它转化为“钦定”从而使用二项式反演来处理。将a,b两个数组排序，使用数组dp_{i,j}表示考虑了a的前i个数，钦定了j对a>b的方案数。转移时若a_i不配对，就从dp_{i-1,j}转移，若a_i配对，设p为b中比i小的个数，则可以通过dp_{i-1,j-1}\times(p-j+1)转移。通过二项式反演可以求出，res=\sum_{i=t}^{i\le n} (-1)^{i-t}\times C(i,t)\times dp_{n,i}\times (n-i)!。

[ARC101E] Ribbons on Tree

给定一个大小为 n的树，保证 n为偶数且小于 5000。

您需要给树上的点两两配对，对于一组对子 (u,v)，在树上将 u→v 的路径染色，定义一个配对方案合法当且仅当所有边都有颜色。

求方案数对 10 ^9 +7 取模。

容易想到树形DP。可是朴素的转移是O(n^3)的，所以要寻找更好的方法。

可以发现，在一个大小为2n的联通块里面的所有方案有g(n)=∏_{i=1}^n(2i−1)个，而断开一个边集之后，在得到的一堆联通块里面进行连边，可以得到不合法方案，所以可以容斥。考虑以下的dp：设计dp_{i,j}考虑在i子树上，i所在联通块大小为j的方案数。转移类似树形背包，下面记tmp_i表示进行新一轮 dp 之前的dp_i，如果不进行断边，dp_{x,i+j}+=tmp_i\times dp_{y,j}，如果要断边则dp_{x,i}-=tmp_i\times dp_{y,j}\times g(j)。答案就是\sum_{i=1}^{i\leq n}dp_{1,i}\times g(i)。

P5400 [CTS2019] 随机立方体

有一个 n\times m\times l 的立方体，立方体中每个格子上都有一个数，如果某个格子上的数比三维坐标至少有一维相同的其他格子上的数都要大的话，我们就称它是极大的。

现在将 1\sim n\times m\times l 这 n\times m\times l 个数等概率随机填入 n\times m\times l 个格子（即任意数字出现在任意格子上的概率均相等），使得每个数恰出现一次，求恰有 k 个极大的数的概率。答案对 998244353（一个质数）取模。

首先发现题目限制条件里面有“恰好”，那么通过二项式反演就可以把“恰好”转化成“钦定”的条件，记钦定i个极大的数的方案数为f(i)。

因为一个极大的数会占用他所在的x,y,z坐标，也就是不可能有两个极大数字的x,y,z坐标其中一个是相同的，所以极大数字个数的上限就是\min(n,m,l)。存在i个极大的数字时，就会有i个x,y,z被占用，而剩下的(n-i)(m-i)(l-i)个数则没有任何限制。

对于f(i)可以拆成3个部分来计算：

1. 选出i个极大的数的方案数：当我们选出一个极大的数字时，他所在的x,y,z坐标都要被占据，所以如果还要再选一个极大数只能有(n-1)(m-1)(l-1)个方案，以此类推，所有的选择方案就是\frac{1}{k!}∏_{i=0}^{k−1}(n−i)(m−i)(l−i)种。

2. 填被极大的数影响的数字的方案：设被极大的数影响的数字有g(i)=nml-(n-i)(m-i)(l-i)个，就要考虑那些数字如何进行摆放。因为极大的数的排列顺序任意，所以可以任意的交换他们，于是可以逐步分离较大的值，把他们分解成一个个子问题求解，于是可以得到有k!C(n,g(k))∏_{i=1}^k\frac{(G_i−1)!}{G _{i−1} !}个方案。

3. 填剩下的数的方案，这个就可以任意填了，排列即可。

乘法原理推导，可以得到总方案数∏_{i=0}^{k−1}g_i∏_{i=1}^k\frac{1}{f(i)}，通过线性求逆元卡一下时间就可通过。

2025.1.6 训练题

[ARC156A] Non-Adjacent Flip

给出一个01字符串s，每次操作可以选择两个下标差大于等于二的数翻转。求把所有的1变成0的最小次数，无解输出-1。

先统计字符串中1的个数，设为cnt。

若cnt为奇数时无解，若cnt为偶数时分类讨论：

1. 若cnt\neq 2或s中的两个1的下标差大于等于2答案就是cnt\div2。
2. 若s="110"或s="011"无解。
3. 若s="0110"答案为3。
4. 其他情况答案为2。

[ARC156B] Mex on Blackboard

你有一个大小为 N 的多重集 A。

你需要执行 K 次操作，每次选取 S⊆A，然后在 A 中插入 mex(S)，表示 S 内最小没有出现过的自然数。

问最终 A 有多少种可能的结果。答案对 998244353 取模。

考虑集合A的最小排除值，那么每次可以加入的元素就是[0,mex(A)]之间的元素。则每次操作可以有C(mex+k-i-1,k-i+1)个情况，操作完后更新mex，累加即可。

[ARC156C] Tree and LCS

给定一棵 n 个节点的树 T。

我们以下面的方式来定义排列 P 与树 T 的相似度：

对于树 T 上的简单路径 x=(x _1,x_ 2 ,…,x _k )，获得序列

构造一个排列 $P$，使得 $P$ 与 $T$ 的相似度最小。

考虑以下的构造：在树上任意取两个叶子x,y，使P_x=y,P_y=x，然后删除这两个叶子并重复进行这一个过程，不会容易证明这样最大的相似度只有1，此时就得到了一组解。

[ABC200E] Patisserie ABC 2

给出n^3个不重复的三元组(i,j,k)，其中i,j,k\le n，将这些三元组按照以下规则排序：

2. 如果上述和相同，i 更小的优先放在左边。
3. 如果 i 也相同，j 更小的蛋糕优先放在左边。

求从左往右第K个三元组的i,j,k。n\le10^6。

因为n巨大所以枚举三元组排序显然行不通。转而枚举三元组i,j,k的和s，设f(s)为三元组和为s时i,j,k可能的取值数量。容易想到用插板法分割s，但是插板法不能保证每个元素都小于n，于是我们可以使用容斥来处理，即使用所有方案减去钦定一个元素大于n的方案加上钦定两个元素大于n的方案再减去钦定三个元素大于n的方案。于是我们可以计算f(s)并且累加，在临界点找到合适的s，然后枚举i，就可以得到j的上下界，当j达到临界时就可以计算出k，得到答案。

[ARC156D] Xor Sum 5

给定 n 个数的数列 a 和一个整数 k。 对于所有长度为 k，值域为 [1,n] 的数列 p，求出 \Sigma_{i=1}^ka_{p_i}的异或和。

对于一个序列如果它是非回文的，那么它就会被它反转过来那个序列抵消，不会产生贡献，所以只需要统计回文序列的贡献。如果k是偶数，可以把回文串直接分成两半，但如果是奇数就要枚举中间的项加上去然后再分开这个串，定义dp_{i,j}表示将序列分治i次，加上了j的答案，递归求解即可。

[ARC156E] Non-Adjacent Matching

好难的题啊~不会写只会贺题解了

定义一个长度为 n 的序列 X 是合法的，当且仅当存在一个无向图 G 满足：G 无自环（但可能有重边）。

对于所有 1≤i≤n，点 i 的度数是 X_i 。

对于所有的 1≤i≤n，不存在连接 i 和 i+1 的边。这里认为 n+1 是 1。

求长度为 n，序列值域为 [0,m]，且序列的和小于等于 k 的合法序列的个数，对 998244353 取模。4≤n≤3000,m≤3000,k≤nm。

设序列的和为sum，如果一个序列合法，必须满足的条件是：

2. \forall i\in[1,n),x_i+x_{i+1}\leq\frac{sum}{2}

使用容斥，答案就是所有方案数减去钦定一个地方不满足条件2的方案数加上钦定连续的两个地方不满足条件2的方案数。

所有的方案数可以使用容斥求出；对于钦定一个地方不满足的方案使用前缀和dp出n-2个[0,m]变量中凑出<t的方案总和 ，然后钦定a[i],a[i-1]使得和为t，枚举两个位置的分配情况；钦定两个位置不满足要求的,设3个元素为x,t,y，从而用二维前缀和求出数量，然后再通过先前的dp数组计算方案数。

2025.1.8训练题

[ARC144E] GCD of Path Weights

给定 n 个点，m 条边的有向图，图中的任意一条有向边满足 边起点的编号小于边终点的编号。每个点有点权，但其中有些点的点权未知。

你需要找到一种给未知点权值的方案，使得 所有 1\to n 的路径点权和的最大公因数最大，或者告知答案可以无限大。输出这个最大值。

将图进行一个转化，在剔除原图中1号点无法到达的节点或者无法到达n号点的节点之后，把原来图中的每一个点拆分成新图中的两个点，即把原图中的点u变成新的图中的u,u'两个点，若这个点的点权已经确定为w就在u->u'直接连一个权值为w的边，在u'->u连一个权值为-w的边，点权不确定的就不连。

建完图之后，对于新的图的每一个环，如果他们的权值为0，那么答案就可以任意的取。否则把答案复制为其与环的权值的最大公约数，跑完所有的环就可以得到解。

2025.1.9 思维难题解题技巧

CF1688C Manipulating History

有一个长度为1的初始字符串，给出n次操作，每次操作把子串s_i替换成t_i。将s_i，t_i全部打乱后给出，再给出操作后的最终字符串，求初始的字符串。

只需要对这2n+1个字符串中的所有字符统计出现次数即可，如果一个字符在某个t_i中出现又在另外一个s_j中抵消或者出现在最终字符串中，那它就会出现偶数次，当且仅当一个字符是初始的字符，它才会出现奇数次。

QOJ 8574. Swirly Sort

给出一个长度为n的序列。有两种操作：

1. 选择k个下标

   1\le i_1<i_2<\cdots<i_k\leq n

   然后让

   a[i_k]\to a[i_1],a[i_1]\to a[i_2],\cdots,a[i_{k-1}]\to a[i_k]

   代价为0。

2. 选择任意的a[i]使a[i]\pm1\to a[i]，代价为1.

问要把这个序列变得有序的最小代价。

分类讨论：

gym105588G GCD

懂不懂什么叫QOJ上面-92个赞的比赛的含金量啊。

给定两个整数a和b，你每轮可以执行以下两种操作之一：

• 若a>0，则令a的值减小\gcd(a,b)。
• 若b>0，则令b的值减小\gcd(a,b)。

问使 a 和 b 均变为0最少需要的轮数。

从题解中可以注意到，答案不会大于26。直接 BFS 爆搜即可。

ECF2024I (无题源)

给出一颗树，需要将其进行黑白染色，使得每条路径上面黑白差不超过3，而且黑点和白点个数相等。

对除了叶子以外的点全部进行二分图染色，然后通过指定叶子的颜色使得两种颜色个数相等即可。

CF2057G Secret Message

给定一个 n\times m 的网格，网格中的一部分格子已经被填充，用 . 标记，其他格子称为自由单元格，用 # 标记。

记 A 为自由单元格的集合，s 为自由单元格的数量，p 自由单元格的并集形成的网格图形的周长。

寻找一个 A 的子集 S 满足：

• |S|\le \frac 15(s+p)
• 任意一个自由单元格要么在 A 中要么和 A 中的其中一个单元格共享一个边

如果有多个答案，输出任意一个。

使用五种颜色对整个图进行染色，使得点(x,y)的颜色是(x+2y)\mod5。

对于每种颜色，统计落在该颜色上面的#的面积与周长总和sum，取sum最小的那个集合中的#即为答案。

gym105588C Coin

又是-92的题。。。

有n个数字，每次从第一个开始每隔k个拿走一个，问最后剩下的一开始是第几个。

看到这个数据范围就会想到根号分治。可以将问题分成两个子问题求解：

1. 总轮数是几轮？
2. 某一轮位于第x位的人，前一轮位于哪里？

两个问题都可以使用根号分治解决，当k\le\sqrt n时使用比较暴力的%你就可以解决，当k>\sqrt n时就可以用一些类似整除分块的技巧求解。

P4061 [Code+#1] 大吉大利，晚上吃鸡！

给定一个无向图和起点终点，问有多少个二元组(a,b)满足起点到终点的最短路要么经过a，要么经过b，且不能都经过。

原题数据范围较小，我们使用一种随机化技巧可以解决更大的数据范围，还比题解区主流解法要好写。

将每个边随机扩增成若干条边，然后进行最短路计数，记cnt(x)表示扩增之后经过x的最短路的数量，如果两个点(a,b)满足cnt(a)+cnt(b)=cnt(s)=cnt(t)那么这个点对就是合法的。使用map进行统计即可。

[ABC240G] Teleporting Takahashi

三维空间中初始在(0,0,0)，每次移动可以将x,y,z坐标其中之一加上或者减去1，求n步走到(x,y,z)的方案数。

首先简化问题到二维情况，可以将直角坐标系旋转45\degree来让x,y坐标相互独立，就可以通过组合数O(1)计算二维情况的答案，然后枚举z坐标变换次数即可。

AT_kupc2019_k One or All

三维空间中初始在(0,0,0)，每次移动可以将x,y,z坐标其中之一加上或者减去1，或者将三维坐标同时加减1，求在\mod m下n步走到(x,y,z)的方案数。

看起来和上面那个题目很像，其实做法也很像，考虑旋转坐标系使得

此时(x',y',z')可以移动到(x'\pm1,y'\pm1,z'\pm1)，当m为奇数的时候可以直接计算，但是如果m为偶数，就要计算\mod 2m下的答案。

EOlymp - 10766 Абсолютно неадекватні операції

给定一个序列a，每次可以进行以下的操作：

• 选择三个连续的数a_{i-1},a_{i},a_{i+1}，使

\begin{cases} a_{i-1}+a_{i}\to a_{i-1}\\ -a_{i}\to a_{i}\\ a_{i+1}+a_{i}\to a_{i+1} \end{cases}

求通过任意次操作可以得到的最终序列数量。

通过阅读题解容易发现，操作等价于交换前缀和数组相邻的两项。组合计数即可。

[ARC072E] Alice in linear land

在数轴上面一个人从点 D 往原点走，给出数组 a，每次行动如果行动后会使其更加接近原点它就会向原点走 a_i 步。

有 q 次询问，每次给出一个下标 x，询问是否可以通过修改 a_x 来让人无法到达原点。

使用 s_i 来表示走第 i 步到第 n 步可以到达 0 的位置集合，t_i 表示走前 i 步最终到达的位置，对于每个询问如果 mex(s_{x+1})\le t_{i-1} 那么就可以通过修改a_x使人到不了原点。只需要对于i\in[1,n]预处理出mex(s_i)和t_i即可。

CF1458C Latin Square

给你一个n\times n的矩阵，每行每列都是[1,n]的排列，有m个操作，包括将矩阵往一个方向循环移动一格以及将矩阵每行/列变为逆。求最终的矩阵。

对于矩阵每一个位置和对应的元素可以通过三元组(i,j,x)表示，其中i,j为下标，x为这个位置的值，那么操作就等效于将(i,j,x)线性变换成(i\pm1,j,x),(i,j\pm1,x),(x,j,i),(i,x,j)中其中一个，维护变换矩阵即可。

CF618F Double Knapsack

给你两个可重集 A, B，A, B 的元素个数都为 n，它们中每个元素的大小 x\in [1,n]。请你分别找出 A, B 的子集，使得它们中的元素之和相等。

把可重集合按照序列处理，下面令a为A,B两个可重集合里面和较小的一个对应的序列，同理b则为和较大的。设sa_i为a中下标在[1,i]之间的元素的和，sb_j为b中下标在[1,j]之间的元素的和。枚举a的下标i，求出b最小的下标j使得sb_j\le sa_i\le sb_{j+1}。记\Delta=sa_i-sb_j，使用std::map维护\Delta到(i,j)之间的映射，初始std::map里面只有0\to(0,0)一组映射。如果在std::map里面发现\Delta已经出现过，那么用当前下标减去std::map里面存储的下标就是答案所在的区间。使用鸽巢原理容易证明答案一定存在。

挖坑待填（序列上的常见算法和数据结构）

因为去清华厕所拿铁了，所以没上课，待补

1.16 思\uparrow维\downarrow题\to选讲

CF1775E The Human Equation

给定 n 个数 a_1...a_n，随后你可以进行若干次操作，每次操作步骤如下：

• 选出 a 中一个子序列（可以不连续）。

• 把子序列中的奇数项减一，偶数项加一；或者奇数项加一，偶数项减一。

求把 n 个数全部变成 0 的最少操作次数。

对原来序列进行前缀和操作，容易发现操作等效于选择一个前缀和序列里面的子序列加或减1，那么答案就是前缀和数组里面的最大正值减去最小负值。

QOJ # 8939. Permutation

交互题，有一个长为n的未知的排列，每次操作可以询问一个区间[l,r]里面的次大值的下标，求全局最大值的下标。要求询问次数不超过1.5\log n，询问总长度不超过3n。

看到\log就容易知道是二分，对于区间[l,r]和中点mid，那么如果[l,r]的次大值等于[l,mid]的次大值，那么次大值在[l,mid]，否则在[mid+1,r]。可以发现如果最大值在区间[l,mid]那么只需要额外的1次询问，否则需要2次，于是我们使两边的区间长度不相等，当划分区间的比例为黄金分割比\frac{\sqrt5-1}{2}的时候最优。

CF1477C Nezzar and Nice Beatmap

• 给定平面直角坐标系上的 n 个点 A_1,A_2,\dots,A_n ，求一个排列 p_1,p_2,\dots,p_n 使得对于任意一个 i\in(1,n),i\in \Z 都有 \angle A_{p_i-1} A_{p_i} A_{p_i+1} < \dfrac{\pi}{2} 。

• 若无解，输出 -1 。

• 若有多个答案，输出任意一个即可。

我们可以从一个任意的排列开始进行操作来得到满足题意的排列，如果有三个点i,i+1,i+2满足\angle P_{i}P_{i+1}P_{i+2}\ge90\degree，那么就交换P_{i+1}和P_{i+2}，对整个序列重复n次以上操作就可以得到满足题目要求的排列。

CF2053D Refined Product Optimality

有两个长度为 n 的序列 a,b。

有 q 次修改，每次修改给出两个整数 o,x：

设 p 是 b 的一种排列，在第一次修改前和每次修改后，你需要求出所有满足条件的 p 中 \prod\limits_{i=1}^n \min(a_i, p_i) 的最大值。

由于答案可能很大，所以对 998244353 取模。

首先可以发现当两个序列都是有序的时候答案最大。维护原来的序列和排序的序列，先预处理出初始答案，每次操作就使用std::upper_bound在排序序列上面找到对应的数字并且使用逆元消除原来的影响，然后乘上新的值，如果有多个相同的数字就对最后一个进行操作，就可以在O(\log)的复杂度解决单次操作。

gym104768B. The Game

给出两个可重集合A,B，大小为n,m，每次操作在A中选择一个元素加上1，并删除A里面最小的元素，问A是否可以通过若干次操作变成B。

先对A,B里面的元素进行排序。可以钦定B里面的元素是由A里面前m大的元素变成的，于是要有解就要满足以下的两个条件：

• \forall i\in[1,m], A_{n-m+i}\le B_i
• \sum_{i=1}^mB_i-\sum_{i=n-m+1}^nA_i\leq n-m

使用std::multiset维护A中较小的n-m个数和较大的m个数，模拟操作的过程即可。

QOJ # 6503. DFS Order 3

有一个n个节点的树，已知从每个节点出发的 DFS 序，求原树。

每个节点的 DFS 序末端的节点都是树的叶子，找到叶子之后从叶子节点的 DFS 序可知它的父亲，逐层确定叶子及其父亲即可。

CF1696F Tree Recovery

给定一棵 n 个节点的树，节点编号为 1\sim n。

树的形态是未知的，但我们知道：

• 所有边的边权都为 1。
• 第 i 行信息由 n-i 个以空格隔开的 01 字符串组成。
• 定义 d(x,y) 为树上 x,y 两点之间的距离。我们约定字符串下标从 1开始。
• 对于第 i 行的 第 j 个字符串 s，s_k=0 表示 d(i,k)\neq d(i+j,k)，s_k=1 表示 d(i,k)=d(i+j,k)。

求原树。

枚举一条边(1,i)，如果已经确定边(x,y)，且dis(x,y)=dis(y,z)则y,z之间也有边，这样就可以从一条边推断其他边的连接情况，然后计算距离检查是否合法即可。

1.17练习题

[ABC255D] ±1 Operation 2

给定序列 a_n ，存在两种操作， a_i \leftarrow a_i - 1 和 a_i \leftarrow a_i + 1 ， q 次独立询问给定 x ，求将原序列所有数均变为 x 需要多少次操作。

容易发现就是把比x大的给减到x，把比x小的加到x，对a,x两个序列排序，双指针维护小于等于当前x的部分即可。

[ABC256E] Takahashi's Anguish

存在 n 个人，你需要确定一个序列 P_n 表示这 n 个人的排列，对于每个人，第 i 个人有且仅有一个 x_i ，表示不喜欢 x_i 站在 i 的前面，若 x_i 站在 i 的前面则会产生 c_i 的不愉悦值，你需要确定排列以最小化不愉悦值之和，求最小值。

把i\to x_i看成是图上面的边，会发现最终的图是一个内向基环森林，对于每个环找出环上面最小的值相加即可。

[ABC255E] Lucky Numbers

给定长度为 n - 1 的序列 S ，存在序列 a_n 满足 a_i + a_{i + 1} = S_i ，给定 m 个幸运数字 x_1, x_2, \cdots, x_m 。你需要确定一个合法序列 a 使其中有最多的数字为幸运数字，求最大值。

容易发现只要知道了序列上面的某一个值就可以唯一确定整个a序列，枚举i\in[1,n],j\in[1,m]，可以O(1)的计算a_i=x_j的时候对应的a_1，使用std::map可以统计每个a_1对应的序列的幸运数字数量，取最大值即可。

[ABC256F] Cumulative Cumulative Cumulative Sum

已知一个长度为 N 的序列 A，你需要进行Q 次操作，它们是以下两种之一：

• 1. 1 x v：将 A_x 改为 v。
• 2. 2 x：令 B_i=\sum_{j=1}^iA_j,C_i=\sum_{j=1}^iB_j,D_i=\sum_{j=1}^iC_j，求出 D_x 对 998244353 取模的结果。

考虑逐层的推，

化简可以得到

只需要使用 @SegmentTree_ 来维护i^2a_i,ia_i,a_i即可。

[ABC255G] Constrained Nim

如果当前的位置没有限制那么该处的 SG 函数值就是\max_{i\le x}SG(i)+1，否则对于一个有限制的x的地方的 SG 函数值会突变，于是有限制的 SG 函数就是一个分段函数，每一段都是斜率为1的一次函数，使用std::map维护拐点就可以快速计算任意位置的 SG 函数。计算突变点x时可以找到并删除所有的SG(x-y)并且统计出现次数，在非突变点上都是恰好出现一次，只需要统计在突变点上的出现次数即可。

[ABC255Ex] Range Harvest Query

给定一片 N 格的农田，从第 0 天开始，第 i 格农田每天会长出 i 的作物。

给出 Q 个询问，每次询问以 D,L,R 的格式给出，表示询问在第 D 天，收割 [L,R] 的农田，会获得多少作物？答案对 998244353 取模。注意询问相互依赖，即在每一次收割后，[L,R] 的作物应当清零。

感觉 Ex 严格小于 G。

发现[L,R]的范围很大，难以使用常规数据结构来维护，操作是区间覆盖，可以使用 ODT，在每次操作的时候统计答案并且进行区间覆盖。

[ABC233D] Count Interval

给定一个数组 a，问有多少个区间满足区间里所有的数的和是 k。

有牢大建议降欧润之的纯纯大水题

做前缀和，使用std::map维护前缀和为s时对应方案数即可，每次答案加上和为s_i-k的方案数。

[ARC153B] Grid Rotations

有一个 H 行 W 列的矩阵，矩阵中每个位置都有一个小写字母。每次操作给出 a,b，含义是在第 a,a+1 行之间切一刀，再在 b,b+1 列之间切一刀，这样能得到四个矩阵；每个矩阵旋转半周，最后把四个矩阵拼起来得到新矩阵。

有 n 次操作，每次形如 a_i,b_i，希望输出操作后的矩阵

可以发现x坐标和y坐标是互相独立的，于是就开两个文艺平衡树来分别维护x坐标和y坐标的反转操作即可。

[ABC233F] Swap and Sort

给你一个长度为 n 的排列和 m 种操作. 每个操作形如 (u,v) , 表示将 a_u 和 a_v 交换 .

请问是否存在一种方案, 经过适当操作, 把这个排列变为 (1,2,3,\dots,n)? 如果可以, 请给出一种构造, 要求长度不超过 5 \times 10^5. 否则请输出 -1.

可以将题目转化成图论问题，a_u 和 a_v 交换等价于u,v连边，在a_i上面有一个棋子要走到i，求最小的总步数。

首先如果a_i和i不联通那么肯定无解，否则找出那个图的任意一棵生成树，在生成树上从叶子节点开始逐步的满足每个点的条件即可。

[ABC233G] Strongest Takahashi

给定有一个 N \times N 的地图 S，若 S_{i, j} 是 #，则位置 (i,j) 上有障碍。

高桥可以进行下面的操作 0 次或更多次：

• 首先，在 1\sim N 之间选择一个整数 D，并在地图内选择一个 D \times D 的子矩阵。
• 消耗 D 的代价摧毁子方格内的所有障碍。

求摧毁所有障碍所需的最少代价。

使用记忆化搜索/dp来解决，设状态dp_{lx,ly,rx,ry}表示全部消除lx,ly,rx,ry这一片区域里面的#的最小花费。如果我们在这个区域里面发现了一整行或者一整列连续的.就可以沿着这一行或者这一列把区域分成两半递归搜索。复杂度 O(n^6) O(能过)

1.19 高♂级数据结构

Baby Seokhwan

维护n个m维向量，Q次操作把第k∈[l_i,r_i] 个向量的第p_i 位改成x_i。求n个向量按字典序排序后的结果。

可以使用主席树的结构来维护向量，但是如果我们直接对向量进行排序是很慢的，于是可以利用主席树的分治结构，从深到浅的逐层排序，排序后合并信息到上一层的节点，这样复杂度是O(n\log^2)的，可以通过这道题了。使用线性的排序方法可以做到单个\log但是没必要我懒。

P6109 [Ynoi2009] rprmq1

有一个初始全0的n×n(n≤5×10^4)矩阵。先选择m(n≤5×10^4)个子矩形做加法，然后

离线下来扫描线，就变成了1.7绝赞%你赛的T2。

题解和代码扒自绝赞%你赛。

题解

本题是 [Ynoi2009]rprmq1 的改编。

考虑直接使用线段树解决这个问题。对于每次 2 操作，将其操作的区间定位到线段树上 O(\log n) 个节点后，在这些节点上分别新建一个“观察者”。接下来，我们考虑一次修改对一个“观察者”的影响：

1. 修改的区间包含了“观察者”所在的节点对应的区间。此时“观察者”观察的区间会整体加上一个数。
2. 修改的区间与“观察者”所在的区间相交，但不是第一种情况。
3. 修改的区间与“观察者”所在的区间无交。此时不会产生任何影响，可以忽略。

若仅有情况 1，那么“观察者”所在的区间只会经历若干次整体加。显然，我们只需要关注最终整体加上了多少，以及在若干次整体加的过程中，整体加法标记的最大值是多少，就足以计算其对“观察者”的影响。于是，我们可以将情况 1 的影响抽象成一个标记 (add, maxadd)，而且这个标记是可以快速合并的，可以在线段树上使用标记下传的方法来维护。

在情况 2 发生时，修改操作在线段树上进行区间定位时会经过“观察者”所在的节点。于是我们只要在 pushup 时计算当前区间最大值对“观察者”的影响即可。综上，在情况 1、2 同时存在时，我们只要在每次打标记、下传标记以及 pushup 的同时，计算这次事件对当前节点的“观察者”的影响。

具体实现分析

那么，对于一个节点，其上只会发生如下两种事件：

1. 新建一个新的“观察者”。初始其观察到的权值为 -\infty 。
2. 用一个数 x 更新当前节点的所有“观察者”的权值。

由于更新总是对当前存在的所有“观察者”同时进行的，越先被加入的“观察者”权值就越大。于是我们可以使用单调栈来快速地维护上述两个事件。具体的，我们将当前权值相同的“观察者”缩成一个点，每次更新时不断弹出栈顶，最后将所有权值发生变化的“观察者”缩成一个新点加入栈中。

std 使用了并查集来方便地维护这一过程。

如果配合线性复杂度并查集的技巧，我们可以做到 O(n \log n) 的复杂度（n, m 同阶）。不过 std 只实现了路径压缩并查集。

参考代码

const int N=1<<18;
const ll inf=0x3f3f3f3f3f3f3f3fll;
ll a[N],c[N],die[N*26],val[N*26],lst;
vector<int> w[N];
int n,m,k,cnt,tot;
pair<int,int> p[N];
namespace seg{
struct node{
int l,r,i;
ll mx,lz,lzm;
inline void operator+=(pair<ll,ll> p){
ckmx(lzm,lz+p.second);
lz+=p.first;
}
}t[N<<2];
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define val(p) val[t[p].i]
inline void pushup(int p){
t[p].mx=max(t[ls(p)].mx,t[rs(p)].mx);
ckmx(val(p),t[p].mx);
}
inline void pushdown(int p){
ckmx(t[p].lzm,t[p].lz);
ckmx(val(p),t[p].mx+t[p].lzm);;
t[p].mx+=t[p].lz;
if(t[p].l^t[p].r){
t[ls(p)]+={t[p].lz,t[p].lzm};
t[rs(p)]+={t[p].lz,t[p].lzm};
}
t[p].lz=t[p].lzm=0;
}
inline void build(int p,int l,int r){
t[p].i=++cnt,val(p)=-inf;
if((t[p].l=l)==(t[p].r=r))return t[p].mx=a[l],void();
int mid=(t[p].l+t[p].r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
pushup(p);
}
inline void modify(int p,int l,int r,int v){
pushdown(p);
if(l<=t[p].l&&t[p].r<=r)return t[p]+={v,v},pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
pushdown(ls(p)),pushdown(rs(p));
if(l<=mid) modify(ls(p),l,r,v);
if(r>mid ) modify(rs(p),l,r,v);
pushup(p);
}
inline void place(int p,int l,int r,int v){//place observers on the node
pushdown(p);
if(l<=t[p].l&&t[p].r<=r){
die[t[p].i]=++cnt,t[p].i=cnt,val[cnt]=-inf;
w[v].emplace_back(cnt);
return pushdown(p);
}
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid)place(ls(p),l,r,v);
if(r>mid) place(rs(p),l,r,v);
}
inline void update(int p,int l,int r){
pushdown(p);
if(l<=t[p].l&&t[p].r<=r)return;
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) update(ls(p),l,r);
if(r>mid ) update(rs(p),l,r); 
}

} inline int query(int p){ if(!die[p])return p; int fa=die[p]; die[p]=query(die[p]);

val[p]=max(val[p],val[fa]);
return die[p];

}

void solve(){ fr(n),fr(m),fr(k); for(int i=1;i<=n;i++)fr(a[i]); seg::build(1,1,n); while(m-->0){ int op;fr(op); switch (op){ case 1:{ int l,r,v; fr(l),fr(r),fr(v); l^=lst,r^=lst,v^=lst; seg::modify(1,l,r,v);

        break;
    }
    case 2:{
        int l,r;
        fr(l),fr(r);
        l^=lst,r^=lst;
        p[++tot]={l,r};
        seg::place(1,l,r,tot);
        break;
    }
    default:{
        int i;
        fr(i);
        i^=lst;
        ll res=-inf;
        seg::update(1,p[i].first,p[i].second);
        for(auto j:w[i]){
            query(j);
            res=max(res,val[j]);
        }
        fw(res),pc('\n');
        lst=k*res;
        break;
    }
    }
}

}

### [時をかけるビ太郎 (Bitaro, who Leaps through Time)](https://www.luogu.com.cn/problem/AT_joisc2019_i)

>给定一条长度为$n(≤3×10^5)$ 的链，只能在$[L_i,R_i)$ 间的某一时刻花费单位时间从$i$出发走到$i+1$(或者反过来走)。一次技能可以让时光倒流单位时间。
>
>$Q(≤3×10^5)$次操作：修改某一条边的$L,R$；询问在$B$时刻从$A$出发，在$D$时刻之前到达$C$至少需要使用多少次技能。

如果$A<B$，令$L_i,R_i$ 都减去$i$，这样可以看作是移动不需要花费时间，可以方便后续的讨论。特判掉$A=B$，如果$A>B$就反着再进行一次处理。

可以发现每一段路径都可以使用下列两种形式中的其中一种表示：

- 区间$[l,r]$：表示这个路径可以在$[l,r]$时间区间内通过。
- 三元组$[l,r,x]$：表示从$l$时刻进入，$r$时刻退出，使用$x$次技能。

发现三元组和区间是可以任意合并的，这个性质启发我们可以使用 @[SegmentTree_](https://www.luogu.com/user/716260) 。对于三元组/区间的合并，对三元组/区间的相交情况，进行分讨即可。

### [P4632 [APIO2018] 新家](https://www.luogu.com.cn/problem/P4632)

>给定$n(≤3×10^5)$个街上商店的信息，四元组表示每个商店的位置，类型，开门时间和关门时间，有$q(≤3×10^5)$次询问，每次问一个时间点上的一个位置的代价，代价指所有类型商店到这个点的最小距离的最大值。

先离线下来，把商店的开门和关门以及询问按照时间排序，进行扫描线。容易发现答案具有可二分性，二分区间长度，就转化成了一个判断区间中是否存在所有类型的商店这个问题。记$pre(i)$表示$i$左边的第一个与$i$同种颜色的商店，对于一个询问区间$[l,r]$，我们寻找$\min_{pos_i>r}pre(i)$，如果这个值小于$l$区间中就没有出现所有颜色的商店。可以使用@[SegmentTree_](https://www.luogu.com/user/716260) 或者平衡树来维护这个，但是平衡树会更加方便一点，因为不需要离散化了。

### [UOJ #218. 【UNR #1】火车管理](https://uoj.ac/problem/218)

> 有$n$个栈，支持$m$次以下操作：求第$L$到$R$个栈的栈顶元素和；对第$x$个栈$pop$；对第$L$到$R$个栈$push(x)$
> 
> 强制在线，$n,m≤5×10^5$

这个题可以使用主席树来求解，求和直接线段树查询，$push(x)$就建立新的版本，弹出栈就寻找当前栈顶的元素之前的一个元素并且在新的版本中使用它覆盖栈顶即可。

## 1.21练习题

### [[ARC106B] Values](https://www.luogu.com.cn/problem/AT_arc106_b)

> 有一个由 $N$ 顶点和 $M$ 边构成的简单无向图。第 $i$ 条边连接顶点 $c_i$ 和顶点 $d_i$。
> 
> 开始时，顶点 $i$ 的值为 $a_i$。您希望通过执行以下操作(至少一次)，使操作后的每个顶点的值分别为 $b_1,b_2,⋯⋯,b_N$。
> 
> 您每次可选 $1$ 条边。当选择的边连接顶点 $x$ 和顶点 $y$ 时，可进行以下任意一个操作。
> 
> 让 $a_x-1,a_y+1$，或者让 $a_x+1,a_y-1$
> 
> 确定是否有操作可以达到您的目的。

使用 DFS 遍历每一个联通块，统计块内$\sum a$是否等于$\sum b$，如果所有块都满足条件答案就是`Yes`。

### [[ARC106D] Powers](https://www.luogu.com.cn/problem/AT_arc106_d)

> 给定长度为 $n$ 的序列 $a$，以及一个整数 $k$。
> 
> 对于每个 $1\le x \le k$，求出如下式子的值：
> $$\sum_{l=1}^{n-1}\sum_{r=l+1}^n \left(a_l + a_r\right)^ x$$
> 
> 答案对 $998244353$ 取模。

首先可以将$ \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X$初步转化为$ \frac{\sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X-\sum_{i=1}^{N} (A_i+A_i)^X}{2}$，接下来主要求的是$\sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X$，通过二项式定理可以将其转化为$ \sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{k=0}^{X} \binom{X}{k}A_i^k A_j^{X-k} $，拆掉组合数可得$\sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{k=0}^{X} X! \cdot \frac{A_i^k}{k!} \cdot \frac{A_j^{X-k}}{(X-k)!} $，然后整理得到$ X! \sum_{k=0}^{X} \left(\sum_{i=1}^{N} \ \frac{A_i^k}{k!}\right ) \left(\sum_{j=1}^{N} \frac{A_j^{X-k}}{(X-k)!} \right ) $。

花$O(nk)$的时间算出$ \displaystyle \sum_{i=1}^{N} \ \frac{A_i^k}{k!}$，然后就可以在$O(k^2)$的时间内求出每一个答案了。

### [[ARC106E] Medals](https://www.luogu.com.cn/problem/AT_arc106_e)

> 你有 $n$ 个朋友，他们会来你家玩，第 $i$ 个人 $1...A_i$  天来玩，然后 $A_i+1...2A_i$  天不来，然后 $2A_i+1...3A_i$ 
> 又会来，以此类推
> 
> 每天你会选一个来玩的人，给他颁个奖，如果没人来玩，你就不颁奖。
> 
> 你要给每个人都颁 $K$ 个奖，问至少需要多少天

容易发现答案上界为$2nk$，并且具有可二分性质，于是考虑如何设计 check 函数，直观的想法是进行二分图完美匹配，将$n$个人，每个人拿$k$个奖项总共$nk$个点放在二分图左边，将天数放在另外一边，如果有完美匹配就为真。不过这样子二分图匹配和网络流都太慢了，要考虑更加快速的算法。

正好我们有一个东西叫做[霍尔定理](https://baike.baidu.com/item/Hall%E5%AE%9A%E7%90%86/5111749)，即对于一个二部图$G~(X,Y)$，$X$存在一个匹配的充分必要条件为对于$X$的任意子集$S$，$S$的邻居个数$N(S)$必须大于等于$S$的大小$|S|$，证明~~我不会~~证他干嘛呢，只需要知道在本题背景之下$n$很小所以可以方便的使用状压来枚举子集，所以可以在本问题背景下快速的解决这个问题，先对$[1,2nk]$中每一天预处理好哪些人可以来，因为$n$很小可以状压存储；每次 check 先将$[1,mid]$范围之内的可以来的人的集合做一个[高维前缀和](https://www.cnblogs.com/heyuhhh/p/11585358.html)，然后枚举每一个子集使用霍尔定理判断即可。

### [[ARC106F] Figures](https://www.luogu.com.cn/problem/AT_arc106_f)

>有 $N$ 个点，每个点有 $a_i$ 个**互不相同、可被区分**的孔，每次可以选择两个不同点，连接两个未被连接过的孔，有多少中方案使得最后形成一棵树。

有科技哥靠着~~坚持与努力~~[ prufer 序列](https://oi-wiki.org/graph/prufer/)与[生成函数](https://oi-wiki.org/math/poly/ogf/)场切了（当然也有入靠着注意力~~与题解~~场切了），我不会科技也没有注意力，所以只能在赛后~~贺题解~~补题了。

记$\textstyle sum=\sum_{i=1}^na_i$，如果$sum<2(n-1)$就没法把图变得连通，方案为0；否则我们为每个点选择一个特殊的孔，进行$n-2$次以下操作：

从未使用的非“特殊”洞中选择一个，从其他连通分量中选择一个未使用的“特殊”洞，连接这两个洞。

最后连接剩下两个未连接的特殊孔，可以算得有$\prod_i d_i \times \left(S-N\right)\left(S-N-1\right)\cdots\left(S-2N+3\right) \times \left(N-1\right)!$种连接方法，但是每种图形都可能被重复计算，所以答案为$\prod_i d_i \times \left(S-N\right)\left(S-N-1\right)\cdots\left(S-2N+3\right)$。

### [[ARC153E] Deque Minimization](https://www.luogu.com.cn/problem/AT_arc153_e)

> 对于一个各位数字均 $\neq 0$ 的正整数 $X$，定义 $f(X)$ 为如下过程所能得到的最小的 $Y$：
> 
> - 对于初始为空的字符串 $S$，依次将 $X$ 的十进制表示从左到右的每一位插入 $S$ 的最前端或最后端。设 $Y$ 为 $S$ 表示的正整数。
> 
> 给出 $Y$，问有多少个 $X$ 满足 $f(X) = Y$。答案对 $998244353$ 取模。

考虑如何从$x$求到$f(x)$，贪心的，若$x$的当前字符小于队首就加到队首，否则加到队尾。对$y$进行一个区间 dp,设$dp_{l,r}$为有多少个$x$进行变换之后可以得到$y_{l,r}$。可以进行以下的转移：

-   if $Y_L \leq Y_{L+1}$,  $\text{dp}_{l+1,r} \to \text{dp}_{l,r}$
-   if $Y_L < Y_R$,  $\text{dp}_{l,r-1} \to \text{dp}_{l,r}$

答案为$dp_{1,n}$，这样可以$O(n^2)$的解决问题。

此时如果$y=12234433442$，那么 dp 进行的过程如下图所示;
![](https://cdn.luogu.com.cn/upload/image_hosting/u2jkoxql.png)

可以发现有很多状态实际上到不了$dp_{1,n}$，将这些状态剪枝之后可以得到如下的示意图：

![](https://cdn.luogu.com.cn/upload/image_hosting/0gac3ftv.png)

可以发现，在序列$y$里面只有前面一段不降的子段有用，所以我们枚举$y_l$，只需要枚举前面那一段不降的子段中的每一种字符，因为字符集是数字所以最多只有$10$个，进行转移时使用 NTT 加速，使用 atcoder 头文件里面的`convolution`函数进行卷积可以省很多工夫。

## 1.23 高级数据结构

### [P6604 [HNOI2016] 序列 加强版](https://www.luogu.com.cn/problem/P6604)

>给一个序列 $A$，每次询问给定 $l,r$，问区间 $[l,r]$ 的所有子区间的最小值之和。
>
>$n ≤3×10^6,q ≤10^7$

数据范围其实是 loj 上面的二阶加强版的。

使用 $ans_{i,j}$ 表示 $[i,j]$ 这一段的答案，对于一个询问$[l,r]$先求出其最小值位置$p$，然后把子区间分成三类：
1. $[l, p − 1]$ 的子区间
2. $[p +1,r]$ 的子区间
3. 经过 $p$ 的区间，这些的最小值都是 $a_p$。

考虑 $1，2$ 如何求，这里以 $1$为例，$2$ 可以反过来做一遍。

我们先计算后缀的答案 $S(i)=ans_{i,n}$，这个利用单调栈，很容易递推。

则 $\displaystyle ans_{l,p-1} = S(l)−S(p)−(p−l)\min_{k≥p}a_k，O(1)$ 算出即可。

此时发现瓶颈在于 RMQ，使用$O(n)-O(1)$的 RMQ 方法才能通过，但是我太菜了不会严格$O(n)-O(1)$ RMQ，所以只能采用一个均摊$O(n)-O(1)$的做法：

对序列进行分块，块长为$\sqrt n$。对于每一个块，在块的内部求前缀 $\min$ 和后缀 $\min$ ，并且对于任意两个块求出它们之间所有块中元素的 $\min$。

查询 $[l,r]$ 时如果 $[l,r]$ 不在同一个块里面，就查询 $l,r$ 之间的整块中的 $\min$，并且在 $l,r$ 所在的块中分别查询后缀，前缀 $\min$，时间复杂度为 $O(1)$。如果在同一个块里面就暴力做 $\min$，复杂度为 $O(\sqrt n)$，但是 $[l,r]$ 在同一个块里面的期望只有 $\sqrt n$，所以均摊下来就是 $O(1)$ 的。

### [P6623 [省选联考 2020 A 卷] 树](https://www.luogu.com.cn/problem/P6623)

> 给定一棵 $n$ 个结点的有根树 $T$，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$。
> 
> 设 $x$ 号结点的子树内（包含 $x$ 自身）的所有结点编号为 $c_1,c_2,\dots,c_k$，定义 $x$ 的价值为：
> 
> $
> val(x)=(v_{c_1}+d(c_1,x)) \oplus (v_{c_2}+d(c_2,x)) \oplus \cdots \oplus (v_{c_k}+d(c_k, x))
> $
> 
> 其中 $d(x,y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数，$d(x, x) = 0$。$\oplus$ 表示异或运算。
> 
> 请你求出 $\sum\limits_{i=1}^n val(i)$ 的结果。

常规的方法是用 Trie 处理。要求u的 Trie，可以先递归求所有儿子的 Trie，再合并，再将所有数 $+1$，再插入 $v_u$。

合并就是普通的 Trie 树合并，与线段树合并类似。

关键在于 $+1$ 的处理，普通的 Trie 似乎不好处理这个问题。

进一步分析，可以发现，$+1$ 相当于将最低的若干个 $1$ 变成 $0$，再将前一个 $0$ 变成 $1$，以此考虑，则可以划分为 $O(\log a)$ 个数集，同一数集中数的改变量相同。

因此，我们可以令低位靠近根，高位远离根这样建 Trie（与普通的 Trie 刚好相反）

$+1$ 时，递归到点 $u$，则交换 $0$ 与 $1$ 对应的子树 $p,q$，再递归点 $ p$ 即可。

求答案只需在 Trie 上每个点记录子树的答案，pushup 即可。
复杂度 $O(n\log a)$。

在题解区看到了一种更加容易理解和实现的做法，但是真的想不到。

对所有的数的某一位进行分析，发现它们的第 $i$ 位是由 $i-1$ 个 $0 $ 和 $i-1$ 个 $1$ 组成的循环。考虑一个节点对其祖先答案的贡献，对第$k$位而言，就是将与其距离满足循环条件的祖先异或上 $2^k$。

这个问题可以想到树上差分，但是因为区间很多，常规的树上差分不能解决本题，于是将差分数组定义为 $c_{k,i}$ 也就是深度 $dep \:\bmod 2^k=i$的点的差分数组。 

求某个点的差分值，就是 dfs 进入该点时和退出该点时的 $\Delta c_{k,dep}$。复杂度为 $O(n\log a)$。

### [loj #503. 「LibreOJ β Round」ZQC 的课堂](https://loj.ac/p/503)

> 简化题意：给定一个序列 $A$，三种操作：
> 1. 指针左移/右移。
> 2. 修改指针位置的值。
> 3. 设 $A$ 的前缀和序列为 $S$，问有多少个位置 $i$ 满足 $S_i\times S_i−1<0$.
> 
> $n ≤10^5,|a_i| ≤ 500$ , 保证 $S_i \neq 0$

发现 $S_i\times S_i−1<0$ 这个鬼东西并不好来维护，于是考虑使用容斥，
$$cnt_{S_i\times S_i−1<0}=cnt_{all}-cnt_{\max(S_i,S_i−1)<0}-cnt_{\min(S_i,S_i−1) > 0}$$

如果当前的指针指向 $p$，那么前面的元素都不会被相加操作影响，后面的元素都会受到相加操作的影响。考虑对 $\max,\min$ 分别维护被影响的数字，支持全局加，插入一个数，删除一个数，询问小于 $0$ /大于 $0$ 的数字数量。全局加只需记录偏移量，然后用平衡树维护即可。
## 1.25 网络流

### [P7425 [THUPC 2017] 机场](https://www.luogu.com.cn/problem/P7425)

> 我们有 $n$ 架飞机和 $m$ 个停机坪，其中 $a$ 个停机坪是“好的”，剩下的 $m−a$ 个是“坏的”。每架飞机有不同的降落时间、起飞时间和乘客数量。每个停机坪在每个时刻只能停一架飞机，且在一个停机坪中起飞和降落不能同时进行。
> 
> 飞机可以在两个时刻之间从一个停机坪移动到另一个停机坪。如果飞机的乘客数量为 $x$，则移动将花费 $⌊xp⌋$ 的费用，其中 $p$ 是一个确定的常数且 $0<p<1$。
> 
> 飞机在降落时可以降落在任意一个停机坪上并瞬间完成登机。如果登机在“坏的”停机坪上进行，且飞机的乘客数量为 $x$，则完成登机将花费 $x$ 的费用；否则，无需费用。
> 
> 最小化总费用。

先特判掉无解的情况。可以发现，一个飞机要么不会移动，要么只会移动一次，也就是登机完成之后从一个好的停机坪移动到一个坏的停机坪。使用费用流建图解决问题，对一个时间设置一个点，对一个飞机设置一个点，在相邻的时间之间连流量为 $a$，费用为 $0$ 的边表示随着时间流逝，好的停机坪上面飞机的变化，对于每架飞机：

- 从起点到飞机到达的时间点连一个流量为 $1$，费用为 $0$ 的边表示这个飞机到达了一个好的停机坪。
- 从飞机对应的点到终点连一个流量为 $1$，费用为 $0$ 的边表示飞机起飞。
- 从飞机到达的时间点到飞机对应的点连一个流量为 $1$，费用为 $x$ 的边，表示飞机一直在一个坏的停机坪上面停着。
- 从飞机起飞的时间点到飞机对应的点连一个流量为 $1$，费用为 $0$ 的边表示飞机一直在一个好的停机坪上面停着。
- 从飞机到达的时间点 $+1$ 到飞机对应的点连一个流量为 $1$，费用为 $⌊xp⌋$ 的边表示飞机一开始停在一个好的停机坪上面，然后转移到了一个坏的停机坪上面。

跑费用流即可得到答案，注意向下取整不要直接转 `int` 而是使用 `floor()` 函数避免可能的精度问题。

### [P4003 无限之环](https://www.luogu.com.cn/problem/P4003)

> 有一个 $n×m$ 的网格状棋盘，有些方格上有水管，水管可能在方格某些方向的边界的中点有接口，如果两个相邻方格的公共边界的中点都有接头，那么可以看作这两个接头互相连接。
> 
> 水管有以下 $15$ 种形状：
> 
> ![](https://cdn.luogu.com.cn/upload/pic/12049.png)
> 你可以选定一个含有非直线型水管的方格，将其中的水管绕方格中心顺时针或逆时针旋转 $90\degree$。给出一个初始局面，请问最少进行多少次操作可以使棋盘上不存在漏水的地方。

撅逝嚎题，网络流中码量最大，大%你中思维最难（

使用费用流，其中流量表示水管是否漏水，费用表示需要操作的次数。

先将原图中的每个点拆成5个，分别表示它的上下左右接口，以及它本身。将每个节点的上下左右分别与相邻节点的下，上，右，左连边。

然后对图进行一个黑白染色，使得每个黑点四周的都是白点，每个白点四周的都是黑点。对于白点将其自身与 $s$ 连边，黑点则与 $t$ 连边，再根据该点的接口数量和方向，将其与对应方向的接口连边。

对于可能进行的旋转操作及其代价，通过连接带有费用的边来处理：

- 对于有 $1$个接口的水管，如果该水管方向向上，就将代表其上方的节点与代表其左右的节点连一条费用为 $1$ 的边表示旋转一次，与代表其下方的节点连一条费用为 $2$ 的边表示要旋转 $2$ 次。其他三种情况同理。

- 对于有 $2$ 个接口且不是直线的水管，如果该水管方向向右上，就将代表其左侧的点与代表右侧的点连费用为 $1$ 的边，将代表其下方的点与代表其上方的点连费用为 $1$ 的边。其他三种情况同理。

- 对于有 $3$ 个接口的水管，如果该水管方向朝上，就将代表其下方的节点与代表其左右的节点连费用为 $1$ 的边，与代表其上方的节点连费用为 $2$ 的边。其他三种情况同理。

完成建图之后就进行最小费用最大流，如果不满流就无解，否则需要进行旋转的次数就是总的费用。

## 2.7线性代数

### [CF24D Broken robot](https://www.luogu.com.cn/problem/CF24D)

>$n$ 行 $m$ 列的矩阵，现在在 $(x,y)$，每次等概率向左，右，下走或原地不动，但不能走出去，问走到最后一行期望的步数。

容易想到动态规划，但是直接 DP 并不可行，因为有后效性。在$\color{blue}\text{蓝书}$中提到，后效性的 dp 可以通过高斯消元处理完具有后效性的部分再正常转移，这就是处理本题的基本思路。  

但是正常的高斯消元是三次方复杂度的，处理 $n$ 行就是四次方复杂度，明显过不去，此时我们发现一个高斯消元矩阵中每行只有 $4$ 个元素非 $0$ ，只考虑这些元素就可以在 $O(n)$ 中完成消元，最终复杂度 $O(n^ 2)$。

### [P6624 [省选联考 2020 A 卷] 作业题](https://www.luogu.com.cn/problem/P6624)

> 给定一个 $n$ 个点的无向带权图，求他的所有生成树的权值之和，权值为
> $$
> val(T)=\left(\sum\limits_{i=1}^{n-1} w_{e_i}\right) \times \gcd(w_{e_1},w_{e_2},\dots,w_{e_{n-1}})
> $$

非常好的题，综合了数论，线代，还有一点多项式(?)，给我写爽了。

看到鸡希地，可以使用反演把他拆开。因为 $\displaystyle x=\sum_{d|x}\varphi(d)$，可以得到
$$
val(T)=\left(\sum\limits_{i=1}^{n-1} w_{e_i}\right) \times \sum_{d|\gcd(w_{e_1},w_{e_2},\dots,w_{e_{n-1}})}\varphi(d)
$$

然后更改求和顺序，把枚举 $d$ 提前，得到

$$
\sum_{d}\varphi(d)\times\sum_{T}(\sum w_e)
$$

此时可以枚举 $d$，但是发现普通的矩阵树定理只能处理 $\sum_{T}(\prod w_e)$，于是我们需要想办法使用 $\sum_{T}(\prod w_e)$ 来求 $\sum_T(\sum w_e)$。

构造一个只有常数项和一次项的多项式 ~~（少项式？）~~ ，使用一次项的系数来表示 sum，其他项均不用考虑。在此之上运用矩阵树定理，对以多项式为元素的矩阵计算行列式得到答案，最后乘上 $\varphi$ 求和即可。

### [UOJ #36. 【清华集训2014】玛里苟斯](https://uoj.ac/problem/36)

> 给 $n$ 个数字，求子集的异或和的 $ k$ 次方的期望。
>
> 
> $n≤10^5,k≤5$，保证答案小于$2^{63}$。

使用线性基可以把 $n$ 个数消到只有 $\log$ 个数来覆盖原来 $n$ 个数的子集，这时进行暴搜 $k$ 位计算，因为此时数很少，而且答案小于 $2^{63}$ 所以状态数不会太多。

##  02.20 常见技巧和结论

### [P6835 [Cnoi2020] 线形生物](https://www.luogu.com.cn/problem/P6835)

> 给定一个有向的链，上面有若干条返祖边，每次在当前节点的出边里面等概率随机的选择一条，求从 $1$ 走到 $n$ 的步数期望。

我们记从 $i$ 到 $i+1$ 的期望步数为 $E_i$，记从 $1$ 到 $i+1$ 的期望步数为 $S_i$。

则：
$$
E_x=1+\frac{1}{\deg_x+1}\sum_{y\in e_x}\sum_{i=y}^xE_i\\

=1+\frac{1}{\deg_x+1}\sum_{y\in e_x}\sum_{i=y}^xS_x-S_{y-1}\\

=\deg_x+1+\sum_{y\in e_x}\sum_{i=y}^xS_{x-1}-S_{y-1}
$$

就可以使用 dp 在 $O(n+m)$ 时间内计算得到答案 $S_n$。

### [P3320 [SDOI2015] 寻宝游戏](https://www.luogu.com.cn/problem/P3320)

> 给定一棵树，边有正边权。
> 
> 维护一个点集，支持插入或删除一个点，询问从点集的某个点出发经过其他点集内的点至少一次并回到这个点的最短路径长度。出发点和经过顺序都可以自己指定。
> 
> $n, m ≤10^5$。

先计算树的 dfn 并使用 `std::set` 维护，加入点 $x$ 就寻找 dfn 在它前面的第一个点 $pre$ 以及它后面第一个点 $nxt$，将答案加上 $dis(x,pre)+dis(x,nxt)-dis(pre,nxt)$，并将这个点的 dfn 放进 `std::set`。删除同理。

### [QOJ #3770. Minimum Spanning Tree](https://qoj.ac/problem/3770)

> 给定一张无向连通图，每个边有参数 $a_i,b_i$。$t$ 时刻第 $i$ 条边边权为 $a_i+b_it$。
> 
> 求时刻在 $l,l +1,··· ,r$ 之间，最小生成树边权和的最小时的值。
> 
> $n ≤10^5，n ≤2×10^5，0≤l ≤r ≤10^6，1≤a_i ≤10^6，|b_i|≤10^6$。

容易发现当 $t=l$ 或者 $t=r$ 的时候最优。做两次 kruskal 即可。

### [QOJ #8936. Team Arrangement](https://qoj.ac/problem/8936)

> 有 $n$ 个人，要求划分为若干队伍。第 $i$ 个人所在的队伍人数必须在 $[l_i,r_i]$ 内。每一支人数为 $c$ 的队伍战斗力为 $w_c$，要求最大化队伍战斗力总和。
> 
> $n ≤60，|w_i| ≤ 10^7$。

$n\le60$ 可以想到分拆数复杂度。。爆搜即可。

### [P6845 [CEOI 2019] Dynamic Diameter](https://www.luogu.com.cn/problem/P6845)

> 给定一棵树，要求支持修改边权，查询直径。
> 
> $n ≤10^5，m ≤10^5$。

修改边权等效于修改子树中的节点离根节点的距离，树剖完之后使用树状数组维护这个距离即可。

现在瓶颈在于求直径，~~学 OI~~ 朴素的 dfs 求直径的算法是没有前途的。考虑直径的一个性质：对于两个树，将它们连接在一起得到的树的直径的两个端点是这两棵树的直径的四个端点的其中两个。

所以可以对 dfn 序列维护一个线段树，节点对应一个联通块的直径信息，根节点就存储整棵树的直径的两个端点，使用线段树的 `pushup` 操作来更新直径。每次修改之后就对修改的部分更新。

复杂度是 $n\log^2n$ 的，还带大常数，**但是能过**。

### [CF1578A Anti-Tetris](https://www.luogu.com.cn/problem/CF1578A)

> 给定一个无重力无消除俄罗斯方块的最终局面，判断它是否可以被形成，并构造一种形成方案。
> 
> 注：所有块都从顶部开始出现，并且每一步只能向左/右/下移动，移动过程不能与其他块重叠。可以在任何时刻停止，停止后不能移动。
> 
> $n, m ≤50$。

考虑从最终局面拿走方块。模拟即可。

### [CF1622E Math Test](https://www.luogu.com.cn/problem/CF1622E)

> 有 $n$ 个人，第 $i$ 个人在一场考试的作答可以用一个长度为 $m$ 的 $01$ 串 $s_i$ 表示（$0$ 表示错误，$1$ 表示正确），他的预估得分是 $a_i$。
> 
> 已知题目分数是长度为 $m$ 的排列，构造一种分数方案，设第 $i$ 个人得分是 $b_i$，最大化$ ∑_{i=1}^n|a_i − b_i|$。

$n$ 很小，指数级枚举绝对值的正负即可。

### [Gym104128 J. Perfect Matching](https://codeforces.com/gym/104128/problem/J)

> 给定 $n$ 个点，每个点有参数 $a_i$，两点 $i,j$ 之间有连边当且仅当 $(i−j)^2=(a_i−a_j)^2$。构造一个完美匹配或证明它不存在。
> 
> $n ≤10^5$ 且为偶数，$|a_i|≤10^9$。

两个点有连边当且仅当 $i −a_i =j −a_j$ 或 $i +a_i =j +a_j$。考虑一个二分图，所有形如 $i-a_i$ 的在二分图左边，$i+a_i$ 的在二分图右边。

连边完之后对每个联通块进行搜索，如果联通块中边数为奇数就无解，否则对联通块进行 DFS 并且逐一匹配。

### [P4745 [CERC2017] Gambling Guide](https://www.luogu.com.cn/problem/P4745)

> 给定一张无向图，你要从 $1$ 走到 $ n$。每个点都有一个售票机，当你买票的时候会随机给你一张去往相邻点的票。
> 
> 要求你制定一个策略，使得购票次数期望最小。
> 
> $n, m ≤3×10^5$。

类似迪杰斯特拉的使用优先队列维护期望，从 $n$ 走到 $1$ 即可。

### [QOJ #9854. Find the Maximum](https://qoj.ac/problem/9854)

> 给定一棵树，点有点权 $b_i$。找到一条边数至少为 $1$ 的路径和一个实数 $x$，最大化路径上 $−x^2 +b_ux$ 的平均值。
> 
> $n ≤10^5，|b_i| ≤ 10^5$。

可以注意到会出现在最终答案里面的路径不会超过 $3$ 个点，计算所有 $2$ 个点或者 $3$ 个点的路径点权平均值的 $\max$，答案就是它的平方除以四。

## 02.23 思维难 ~~(史)~~ 题解题技巧