模板及讲解

简介

$DFT$：离散傅里叶变换
$IDFT$：离散傅里叶逆变换
$FFT$：快速傅里叶变换，计算多项式乘法 (卷积)
$FNTT/NTT$：快速傅里叶变换的优化版，优化常数及误差

BZOJ 2299
题意：一次考试共有$n$个人参加，第$i$个人说：「有$a_i$个人分数比我高，$b_i$个人分数比我低。」问最少有几个人没有说真话(可能有相同的分数)

没有相同的分数的话就是水题……虽然本题DP好像也挺水的
有相同分数考虑将这个相同分数的区间拎出来($1$到$n$范围内)
设$s(i,j)$为$[i,j]$为相同分数, 有几个人说自己是这个分数。
这个显然可以预处理出来，具体看代码实现
题目所求答案可以补集转化，即求最多有几个人说实话
设$dp(i)$为排名前$i$个人的最多有几个人说实话
那么
$$
dp(i)=\max(dp(i-1),dp(j-1)+\min(i-j+1,s(j,i)))
$$
$j$为当前这个名次的最左边的一个人，即从上一个名次转移过来
这里相当于将每个分数的人按顺序变成几个块来处理。

BZOJ 4071
题意：$[0,10^9]$范围有$n$个区间，要求选一个点$x$或两个点$x,y$，对于任意区间$i$代价为$\min(|l_i-x|+|r_i-x|, |l_i-y|+|r_i-y|)$，求最小代价

对于只选一个点的，设选了$p$点，则
$$
ans=\sum_{i=1}^n |l_i-p|+|r_i-p|
$$
将端点视为同等的，那么答案即为
$$
ans=\sum |x-p|
$$
这是一个中位数的模型，直接取中位数是最优的。

对于选两个点的，考虑每个区间$[l,r]$会过离$\frac{l+r}{2}$最近的桥，所以我们可以将区间按照$l_i+r_i$排序，然后顺序枚举每个区间作分界点，左边右边分开处理，变成一个点的做法。

那么我们需要支持一个动态中位数。显然可以用 Splay / 主席树 求第$k$大($k=\frac{n}{2}$)
然而这里只需要求出一个前缀、后缀的中位数，那么可以考虑不用主席树而是权值线段树代替之。
在权值线段树上找$k$大，然后再分类讨论求所有点到中位数距离即可。

另外这题还满足单峰性质，那么三分套三分枚举桥位置即可。

知识点：
1、中位数的运用：多个点到某个点距离和最近
2、权值线段树 / Splay / 主席树动态中位数的方法

BZOJ 1260 CQOI2007 涂色
题意：给定一个$n$长序列，你可以每次选择一段区间染色，请问从空状态转移到目标最少要多少步。

Hdu 2476 String painter
题意：给定一个$n$长序列，你可以每次选择一段区间染色，请问从初始状态$A$转移到目标$B$最少要多少步。

Codeforces 1114 D. Flood Fill
题意：给定一个$n$长序列，你要最开始选择一段连续区间，然后每次可以修改初始区间块的颜色，请问将区间变为一个颜色最少要多少步。

对于 Bzoj 1260，我们可以设$dp(i,j)$为$[i,j]$修改的最少步数。则可以列出
$$
dp(i,j)=\min(dp(i,k)+dp(k+1,j))
$$
对于$a_i=a_j$，我们可以列出
$$
dp(i,j)=\min(dp(i+1,j), dp(i,j-1))
$$
相当于$[i,j]$可以在前面先修改，可以证明这是最优的。$dp(i+1,j)$等价于$[i+1,j]$修改时可以带上$i$, 后面同理。

对于 Hdu 2476，要从初始状态出发，我们先求出 Bzoj 1260 的 DP 值，然后设$f(i)$为前$i$个位置修改的最少步数。
则
$$
f(i)=f(j)+dp(j+1,i)
$$
而对于$a_i=b_i$，那么$i$可以不涂，则
$$
f(i)=f(i-1)
$$

对于 CF 1114 D，我们必须改初始块的颜色，所以可以设$g(i,j)$为$[i,j]$修改的最小步数。
则
$$
g(i,j)=\min(g(i + 1, j), g(i, j-1))
$$
对于$a_i=a_j$，则
$$
g(i,j)=\min(g(i+1,j-1)+1)
$$

这三题都运用了区间DP的套路转移
$$
dp(i,j) \Leftarrow dp(i,k), dp(k+1,j) \\
dp(i,j) \Leftarrow dp(i+1,j), dp(i,j-1) \\
dp(i,j) \Leftarrow dp(i+1,j-1) \\
$$
以及区间覆盖的相关性质。

Bzoj 1058
题意：有一个长度为$N$的整数序列，并且有以下三种操作：
INSERT i k：在原数列的第$i$个元素后面添加一个新元素$k$；如果原数列的第ii个元素已经添加了若干元素，则添加在这些元素的最后（见下面的例子）
MIN_GAP：查询相邻两个元素的之间差值（绝对值）的最小值
MIN_SORT_GAP：查询所有元素中最接近的两个元素的差值（绝对值）

本题如果原数列的第$i$个元素已经添加了若干元素，则添加在这些元素的最后非常关键，因为这样我们就可以每个位置维护一个数组，然后对每个位置处理即可。
对于MIN_SORT_GAP，就是bzoj1588 & 1208，直接开个 set 维护
对于MIN_GAP，我们每个位置维护$\min(a_i-a_{i-1})$, $a[1,g]$是每个位置维护的数组
然后再将后面的一个位置的第一个数的值和这个位置维护的数组的最后一个值的最小值更新
然后将这些位置的值都插进一个multiset里面维护最小值即可。

知识点：
这种操作读文字的字符串大小数好，开够数组

BZOJ 1861
题意：给定一个排列，求对排列支持以下操作

• Top S，将排列中的$S$放到排列最前面
• Bottom S，将排列中的$S$放到排列最后面
• Insert S T：若$S$的前面有$X$个数，则这个数放回去后它的前面有$X+T$个数 ($T∈(-1，0，1)$)
• Ask S：询问$S$前面有几个数
• Query S：询问从前往后第$S$个数是什么。

显然 Splay 可做，kth可以定每个数在排列中的位置
然后因为这里是排列，所以可以建立一个数组映射，即每个数在Splay上的点编号和数对应。
然后将Splay上的某点转到根之后的左子树大小即为该点在排列中的位置。

知识点：
1、函数功能写清楚
2、实在调不出来/想不出来可以放下来之后再看
3、Splay 的序列区间最好都建在 $[1,n+2]$，避免与$0$冲突，加上虚节点非常有用
4、Splay 维护序列一定要用build函数
5、对于维护序列的数据结构，可以通过某个操作来得到整个序列来查程序的错误

BZOJ 1226
题意：见上。

看见$B_i \leq 7$就要留意状压了。(本蒟蒻没想到)
这题一个状态和前和后都有关，这样状压DP就排上用场。前面DP顺推，后面的状态状压记录。
然后可以设$dp(i,st)$为$[1,i-1]$吃完饭了，$[i, i+7]$是否吃饭的状态
发现这样无法转移，不能算出做菜时间，那么加一维$k$表示上一层吃饭的人相对$i$的位置的距离$k \in [{\color{red}{-8}}, 7]$
注意要到$-8$，因为可以后面$7$个人都吃完再轮到$i$吃。
转移考虑$i$是否吃了。
1、吃了的话，则
$$
dp(i+1,st / 2, k-1)=\min(dp(i,st,k))
$$
其中$st / 2$意义为左移，$k-1$的原因是之前吃的位置相对$i+1$是远了。
这两个式子表示的意义实际是一样。
2、没吃，就枚举$h\in [0,7]$吃
$$
dp(i, st | h, h)=\min(dp(i, st, k) + T(i+k,i+h))
$$
其中$T(x,y)=x \operatorname{xor} y$，即题目中的$x\operatorname{or} y - x \operatorname{and} y$

还要考虑容忍度。因为每个人的$B_i$不同，所以边扫描边维护最小的容忍区间，即代码中的bd

因为这题又刷表又递推，$i$要循环到$n$，注意集合的最大值为1<<8

bzoj 3126
题意：给定数轴$[1,n]$，有$m$个区间，每个区间有且只有一个黑点。不被任何区间包含的点也算黑点。求黑点最大个数。

可以差分约束，建立$a(r)-a(l-1)=1,0 \leq a(i)-a(i-1) \leq 1,-1 \geq a(i-1)-a(i) \geq 0$，但是本题卡SPFA

DP做法：

设$dp(i)$为$i$位置，$i$位置必黑的最优方案。
则
$$
dp(i)=\max_{l[i] \leq j \leq r[i]}(dp(j)+1)
$$
对于$j$的取值集合$[l[i], r[i]]$，我们可以预处理出来。
显然对于一个区间$[x, y]$，在$y+1$位置向左最远选点位置是$x$(否则$[x,y]$没黑点)
在$y$位置向左最近选点位置是$x-1$(否则$[x,y]$有多个黑点)

然后$r$没有加入区间时默认$r[i]=i-1$
区间加完后就做个前缀$\max$和后缀$\min$

然后单调队列优化DP即可。

Codeforces 1106E
题意：给定一个$n$长值域为$m$的序列，你要将其组成尽可能多的三元组$(a, b, c)$满足$a=b=c$或者$b=a+1,c=b+1$。

一开始读错题了。
先将所有数存在一个桶里，按数大小来DP。
显然对于一种方案$(a,b,c)$，他只会重复至多$2$次。
那么对于一个方案$(i,i+1,i+2)$，他最多只会有$2$个
那么设$dp(i,0/1/2,0/1/2)$为前$i$个数，第一个数是$i$的三元组个数，第二个数是$i$的三元组个数的最大个数。
转移
$$
dp(i,a,b)=\max_{0\leq c \leq 2}(dp(i-1,b,c)+c+(cnt-a-b-c) / 3)
$$
其中$cnt$为$i$数的个数。

后面$(cnt-a-b-c) / 3)$等价于将多余的$i$组成三元组$(i,i,i)$

hdu 5608
题意：给定$n$和函数$f, g$满足
$$
g(n)=n^2−3n+2\\
g(n)=\sum_{d|n} f(d)
$$
求
$$
\sum_{i=1}^n f(i) \mod 10^9+7
$$

显然$f * I = g$，杜教筛即可。
即
$$
S(n)=\sum_{i=1}^n g(i) - \sum_{i=2}^n S(\lfloor \frac nd \rfloor)
$$
将$g$每个项分离出来，用平方数列前缀和公式+等差数列公式即可求解。

对于前$n^{\frac 23}$的$f$，反演一下即可。即
$$
f(n)=\sum_{d|n} g(d) \mu(\frac nd)
$$
注意这个式子不是很常用。