7.11dp by 一休哥777 orz

P2051

在一个 $n\times m$ 的棋盘上放置若干个互不攻击的炮，求摆放的方案数。$n,m\le100$。

首先发现炮不能互相攻击等价于每行每列最多有 $2$ 个炮。

考虑设 dp 状态 $dp_{i,j,k}$ 表示当前到达第 $i$ 行，且有 $j$ 列放置两个炮、$k$ 列放置一个炮。那么相应的放置 $0$ 个炮的列数就是 $m-j-k$。

不多说直接上题

P1903

给定一个颜色序列，支持一下两种操作：

• 给定 $l,r$ 求区间 $[l,r]$ 内颜色数量。
• 单点修改颜色。

带修莫队板子。

考虑在三维空间里移动询问点 $(l,r,t)$ 表示区间左右端点和处理过的询问的个数。那么就可以直接做，显然移动的复杂度都是 $O(1)$。

前言

大战混凝土。

定义

通常的定义是 $\dbinom nk$ 表示在 $n$ 个元素里挑选 $k$ 个的方案数。

为了拓宽定义，我们先定义下降幂 $r^{\underline k}$ 为：

线段树 1

区间加区间和。看看怎么暴力地分块。

考虑最暴力的做法就是 $O(n^2)$，但是可以将序列中一部分合成一个块来进行处理。

设块长为 $B$，那么就会分出 $\dfrac nB$ 个块，此时修改的时候最多会遍历 $\dfrac nB$ 个整块和 $2$ 个散块。我们在整块上打懒标记修改，在散块上暴力修改，因此此时时间复杂度是 $O\left(\dfrac nB+2B\right)$。

在查询的时候是同理的，我们另外维护每个块的和，整块拿和加上懒标记的影响、散块直接暴力加起来，此时时间复杂度是 $O\left(\dfrac nB+2B\right)$。

系统写一下莫反。

莫反公式

其中 $\mu(n)$ 为莫比乌斯函数，

且该函数为积性函数，即若 $n\perp m$ 则有 $\mu(nm)=\mu(n)\cdot \mu(m)$。证明是显然的。

特别的，我们有

长链剖分是另一种树的剖分方式。其主要用途之一是加速以深度为下标的 dp 到 $O(n)$。

长链剖分过程

类比重链剖分，我们定义树上一个节点的向下深度 $d_u$ 为从这个点出发向下走最大的距离。可以用树形 dp 理解，即 $d_{\mathrm{leaf}}=1$，$d_u=\max\{d_v+1\}$。

同时如果一个点有儿子，我们就定义一个点的长儿子为 $v$ 中 $d_v$ 最大的点，相应的剩余的儿子就是短儿子。定义长链就是一个短点和它的长儿子链成的从上往下的链。

从这个定义中不难发现长链的一些性质：

点分治善于处理大规模的树上问题。

一个使用点分治的特征是：要求的问题与谁是树的根没有太大关系。

点分治思想

点分治 1：

给定一棵树，边有边权，判定树上长度等于 $k$ 的路径是否存在。多次询问，$n\le10^4,m\le100$。

首先考虑暴力，就是枚举 $n$ 对点利用树上差分进行求解，时间复杂度是 $O(mn^2\log n)$，肯定过不去。

平衡树是一种比线段树更加强大的数据结构，它能维护很多线段树无法维护的操作和信息，比如插入、删除、反转。

我是 splay 批

splay

维护的基本信息

• $root\And tot$，根节点和节点个数。
• $ch_{u,0/1}$，左右儿子。
• $val_u$，该节点维护的数值。
• $fa_u$，父亲节点。
• $cnt_u$，该节点重复的次数。（$val$ 一样就重叠在一起）
• $siz_u$，表示该节点子树内有多少个点（计算重点数量）

莫队算法是一种根号复杂度离线算法，也与分块、定期重构并称优雅的暴力。

普通莫队的时间复杂度是 $O(m\sqrt n)$，此外还有许多变种。

普通莫队

当我们遇见一类没有修改的问题时如何处理？

假设我们已经求出了在 $[l,r]$ 上的答案，我们想求出 $[l^\prime,r^\prime]$ 的答案，怎么办？

01-trie 是一种特殊的 trie 树，是将整数作为二进制形式插入到 trie 中形成的字典树，其字符集为 $\{\mathtt0,\mathtt1\}$。01-trie 能够高效地维护许多关于异或的问题。

维护异或最大对

给定一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$，你需要求出最大的异或对，即 $(i,j)$ 使得 $i\neq j$，$a_i\oplus a_j$ 最大。

贪心的想，如果我们知道了所有数的二进制表示，当想求最大的 $a_i\oplus x$ 时，我们只需要让 $x$ 的高位与 $a_i$ 对应的位尽量不同就可以了。（一个高位可以抵得上剩下的所有低位。）

因此我们枚举 $i$，并将 $a_1,a_2,\dots,a_{i-1}$ 全部从高位到低位地插入到 01-trie 中。接下来我们在 trie 中查找答案，从根节点向下跳，如果能走到与 $a_i$ 当前位不同的方向就一定走，否则只能走另一侧。最后走下来的路径异或上 $a_i$ 就是对于 $a_1,a_2,\dots,a_i$ 的最大异或对。