KeBlog

不久前学了整体二分，做了几道题，还在考试上派上用场过几次。
觉得自己大概懂了整体二分，直到一次碰上了强制在线的毒瘤题。。。

整体二分：从离线到强制在线

基础

大概讲讲整体二分吧。

整体二分大概用于这样一个场景：
有多组询问，每个询问可以二分，但是每个询问二分的时间不能接受，
而不同询问的二分有共同点，这时就可以用整体二分把多个询问一起二分。
所以这是个离线算法。

（以下的除号皆表示整除）

用数论函数计算的时候，总会遇到这样一种问题： \(\sum_{i=1}^n f(\frac{n}{i})\) 。 \(O(n)\) 求往往无法满足需要。

但是打表可以发现， n/i 的取值对于一段连续的 i 是一致的， 那么可以考虑一块一块求。

设已知当前块的左端点为 l ，如果知道右端点 r（左闭右开），意味着 \(\forall l<=i<r, \frac{n}{i} = \frac{n}{l}\) ， 这一块对答案的贡献就是 \((r-l) \times f(\frac{n}{l})\) 。

结论是 \(r = n / (n / l) + 1\) 。

证明：

• 对于 l 设 \(n / l = x\)
• 那么由 \(n \bmod l = n - n / l \cdot l = n - l \cdot x\) 可知 $ n - l x $
• 那么若 \(l + 1\) 满足 \(n / (l + 1) = n / l\) ，可知也有 \(n - (l + 1) \cdot x \geq 0\)
• 即 \(n - l \cdot x \geq x\)
• 对于 k 若 \(n / k = n / l\) 而 \(n / (k + 1) != n / l\)
• 那么根据上式可得 k 满足 $ 0 n - k x < x$
• 所以 \(n - k \cdot x = n \bmod x = n - n / x \cdot x\)
• 所以 \(k = n / x = n / (n / l)\)
• 由 k 的定义 \(n / k = n / l \& n / (k + 1) != n / l\) 可知 k+1 即是要求的 r

那么可以枚举块，当前 l,r 可以求得，下一个块的 l 显然是当前 r。

有时候会有点变化：

要求 \(\sum_{i=1}^{min(n, m)} f(\frac{n}{i}) \cdot f(\frac{m}{i})\) 。

还是会存在 \(\forall l \le i < r, \frac{n}{i} = \frac{n}{l} \& \frac{m}{i} = \frac{m}{l}\) 。

所以这样的区间的右端点为：\(r = min(n / (n / l), m / (m / l)) + 1\) 。

所以还是可以一块一块的枚举求和。

这里只是类欧几里得的一种：
快速求下式： \[f(a, b, c, n) = \sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor\]

其中 a, b, c, n 都是正整数。

缩小 a, b 规模

首先的目标是让 a, b 小于 c 。

结论 1 ：
\[\lfloor \frac{Ax+B}{y} \rfloor = \lfloor \frac{A(x\%y)+B}{y} \rfloor + A\lfloor \frac{x}{y} \rfloor\]

证明：
首先用到整除与取模的转换： \(\lfloor \frac{x}{y} \rfloor = \frac{x-x\%y}{y}\) 。
得到原命题等价于：
\[\frac{Ax+B-(Ax+B)\%y}{y} = \frac{A(x\%y)+B-(Ax+B)\%y}{y} + A\frac{x-x\%y}{y}\] \[Ax + B - (Ax+B)\%y = A(x\%y) + B - (Ax+B)\%y + A(x-x\%y)\] \[Ax - (Ax+B)\%y = A(x\%y) - (Ax+B)\%y + A(x-x\%y)\] \[Ax = A(x\%y) + A(x-x\%y)\] \[Ax = A(x\%y) + Ax - A(x\%y)\]
得证。

那么通过这个结论可以得知：
\[ \begin{equation} \begin{aligned} f(a, b, c, n) &= \sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor \\\\ &= \sum_{i=0}^n (\lfloor \frac{(a\%c)i+b\%c}{c} \rfloor + i\lfloor \frac{a}{c} \rfloor + \lfloor \frac{b}{c} \rfloor) \\\\ &= f(a\%c, b\%c, c, n) + \sum_{i=0}^n ( i\lfloor \frac{a}{c} \rfloor + \lfloor \frac{b}{c} \rfloor) \\\\ \end{aligned} \end{equation} \]

后面那一段就是一个等差数列求和，于是 a, b 被转换为小于 c 。

转换成子问题减小规模

整除除了用取模代替外，还有一种方法。

结论 2 ：
\[\lfloor \frac{x}{y} \rfloor = \sum_{i=1}^{MAX} [i \leq \frac{x}{y}]\]
其中 MAX 是任意一个足够大的值。
证明？相当于从 1 开始数，感性理解即可。

那么通过这个结论可以得知：
\[ \begin{equation} \begin{aligned} f(a, b, c, n) &= \sum_{i=0}^n \lfloor \frac{ai+b}{c} \rfloor \\\\ &= \sum_{i=0}^n \sum_{j=1}^{(an+b)/c} [j \leq \frac{ai+b}{c}] \\\\ &= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [j + 1 \leq \frac{ai+b}{c}] \\\\ &= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [cj + c \leq ai+b] \\\\ &= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [cj + c - 1 < ai+b] \\\\ &= \sum_{i=0}^n \sum_{j=0}^{(an+b)/c-1} [\frac{cj+c-b-1}{a} < i] \\\\ &= \sum_{j=0}^{(an+b)/c-1} \sum_{i=0}^n [\frac{cj+c-b-1}{a} < i] \\\\ &= \sum_{j=0}^{(an+b)/c-1} (n + 1 - \sum_{i=0}^n [i \leq \frac{cj+c-b-1}{a}]) \\\\ &= \sum_{j=0}^{(an+b)/c-1} (n - \lfloor \frac{cj+c-b-1}{a} \rfloor) \\\\ &= n \lfloor \frac{an+b}{c} \rfloor - \sum_{j=0}^{(an+b)/c-1} (\lfloor \frac{cj+c-b-1}{a} \rfloor) \\\\ &= n \lfloor \frac{an+b}{c} \rfloor - f(c, c-b-1, a, (an+b)/c-1) \end{aligned} \end{equation} \]

那么就得到了一个递归计算 f(a, b, c, n) 的算法，
a = 0 时上式不成立，因为上面的推导有除以 a 的步骤。
因此将 a = 0 作为终止状态，此时 f 的计算是常数数列求和。
复杂度是对数复杂度 log(a)，因为上面的过程规模的减小速度相当于 gcd 。

数形结合

复习的时候看到这么多式子头都大了，但是这个类欧事实上就是数一个三角形内的整点数，第一步很好理解，第二步本质上就是把坐标轴翻转了一下然后用一个正方形的点数减去一个三角形的点数（事实上可以不用这个补集转换），很快就可以得到同样的结论，可以避免冗长的纯式子推导。

放在二维平面上，第一步的本质就是把斜率固定在小于 1 的数，第二步的本质就是翻转坐标轴，翻转后斜率会变为原来的倒数，于是会超过 1 。这样反复进行就可以逐渐数完三角形内的所有整点。

UPD: 准确来说不是三角形，是梯形，但显然两者可以相互转换。

但是更复杂的类欧这个数形结合好像就不管用了，还是得用数学推导。

作用

线段树通过维护序列，可以维护一个承载各种操作的时间轴。

通常用于辅助一些不支持删除操作的数据结构（线性基，并查集），
这种情况可以用线段树分治维护操作影响的时间来巧妙地避开删除。

线段树结构

线段树分治用到的线段树（以下简称线段树）是以询问的时间为键值，
没有权值只有标记的线段树。

也就是线段树的一段区间对应的是一段询问（一段时间）。

这样的线段树只需要支持区间修改（打标记）。
每一个操作都会影响一段时间，对应于线段树的区间修改。

例题

这玩意需要一个例题才讲的清。
（由于线段树分治用于辅助其他数据结构，再看例题前得先会线性基）

维护一个集合，每次操作可以加入一个数或删除一个已经存在与集合的数。
每次操作后要回答这个集合的最大异或和。
操作次数 1e5 。

暴力线性基

如果只有插入没有删除，这题就是一遍线性基。

但是不巧线性基不支持删除，所以只能在每次删除后重构线性基。
复杂度平方带对数，稳 T 。

时间轴

将每次操作看做时间点，假设数 x 在时刻 l 被插入， r 被删除，
那么 x 只存在于 [l, r) 这段时间，
假如每个时刻开一个线性基，那么将 x 插入 [l, r) 的每个线性基，
这样就可以在最后通过线性基询问得到每个时刻的答案，
复杂度还是平方带对数，稳 T 的离线算法。

线段树优化

比较上述两种算法，
第一种复杂度瓶颈在于重构线性基，实在是没有什么优化空间，
但是第二种算法中，复杂度瓶颈在于将 x 插入到 [l, r) 的每个线性基，
这个操作相当于一个区间修改，可以用线段树优化。

那么一个优秀的算法就出来了：
线段树每个节点维护一个 vector （相当于懒标记），插入 x 将直接加在线段树对应区间的 vector　内。
所有操作过后会得到一个只有懒标记的线段树，
然后考虑如何通过这样一颗线段树得出所有答案。

处理懒标记

懒标记下传？
不存在的，因为懒标记是一个 vector, 下传的复杂度并不是 O(1) ，
不难验证下传所有懒标记会使复杂度重回 n 方。

既然不能下传，那就进行 n 次单点查询？
一个道理，单点查询的复杂度并不是 log(n), 这样做同样对复杂度没有优化。

那就没救了

分治

线段树分治，不能只有线段树，还要分治啊。

现在需要只把每个懒标记访问一遍就得出所有答案。

dfs 整颗线段树（实际上就是分治），深度是 log 级别的，那么对每一个深度开一个线性基。
如能能让 dfs 每个节点时该深度线性基维护的是这个节点到根的所有懒标记，
最后 dfs 到每个叶子节点就可以得到该叶子节点到根的懒标记的线性基，也就可以求出这个叶子节点的答案。

假设当前 dfs 到 u, 深度为 d, 深度对应的线性基已经是维护其到根的懒标记。
dfs 到一个新点 v 一定会使深度 + 1 ，将当前深度 d 的线性基拷贝到下个深度 d + 1 中。
那么 dfs 到 v 后再将 v 的懒标记加到 d + 1 的线性基中，d + 1 的线性基也就满足了要求。
通过这样的过程就能够做到只访问每个懒标记一遍。

这就是线段树分治了。

真 - 例题

这两道题就没有这么裸了。

洛谷八纵八横 （线段树分治 + 线性基）

BZOJ 二分图 （线段树分治 + 并查集）

$ C_n^m $ 在组合数学中的意义：在 n 个元素选 m 个元素的方案数。

公式

公式 1

\[ C_n^m = \frac{n!}{m! * (n-m)!} \]

组合数的通项公式。

当要求组合数模一般模数时 ，通项公式的分母可能没有逆元导致不可行。

公式 2

\[ C_n^m = C_n^{n-m} \]

基本性质，可以由通项公式得出。

公式 3

\[ C_n^m * C_m^k = C_n^k * C_{n-k}^{m-k} \]

公式 4

\[ C_n^m = C_{n-1}^{m-1} + C_{n-1}^m \]

组合数的基本递推式。

当要求组合数模一般模数时 ，常用这种方法预处理组合数。

公式 5

\[ \sum_{i=0}^n C_n^i = 2^n \]

组合意义： n 个元素选任意元素的方案数。 每个数都可以选或不选，所以方案数为 $ 2^n $ 。

同样可以由二项式定理： $ (x + 1)^n = _{i=0}^n C_n^i * x^i $ 得出。

公式 6

\[ \sum_{i=0}^n (C_n^i)^2 = C_{2n}^n \]

公式 7

\[ C_{n+m}^k = \sum_{i=0}^k C_n^i * C_m^{k-i} \]

从组合数学上的定义出发，在 n + m 个元素中选 k 个， 相当于先在前 n 个元素中选 i 个再在后 m 个元素中选 k - i 个。 枚举这个 i 把方案数相加就能得到最终方案数。

公式 8

\[ \sum_{i=0}^n C_{k+i}^k = C_{k+n+1}^n \]

进一步可以得到下式：

\[ \sum_{i=0}^n \sum_{j=0}^m C_{i+j}^i = C_{n+m+2}^{m+1} - 1 \]

类似的还有：

\[ \sum_{i=0}^n C_{i}^k = C_{n+1}^{k+1} \]

Lucas 定理

\[ C_n^m \% p = C_{n/p}^{m/p} * C_{n \% p}^{m \% p} \% p \]

常用于模数较小的组合数取模。

（以下除号皆表示整除）
对于一些式子复杂度大的数论题，或许用莫比乌斯反演可以高效解决问题。

前置技能：

• 基本数论函数

• 狄利克雷卷积

莫比乌斯函数满足 \(\mu \times I = \epsilon\)

即 \(\sum_{d|n}\mu(d) = [n = 1]\)

表达式为：

\[ n = 0 : \mu(n) = 1 \] \[ n = \prod_{p|n\,and\,p\,is\,prime} p : \mu(n)=(-1)^k \] \[ otherwise : \mu(n)=0 \]

证明：
暂时不会

莫比乌斯反演：
对于数论函数 \(f(n)\) ，设 \(F(n) = \sum_{d|n}f(d)\)
即 \(F = f \times I\)
则有 \(f(n) = \sum_{d|n}F(d)\cdot\mu(\frac{n}{d})\)
即 \(f = F \times \mu\)

证明：

\[ \because \; F = f\cdot I \] \[ \therefore \; F\cdot \mu = f\cdot I\cdot \mu \] \[ \because \; I\cdot \mu = \epsilon \] \[ \therefore \; F\cdot \mu = f\cdot \epsilon \] \[ \therefore \; f = F\cdot \mu \]

莫比乌斯反演好像主要是用来推式子，F 比 f 好做的话，就可以试试莫比乌斯反演。

另外事实上只需要熟知 \(\mu\) 函数的性质，直接推式子就行了，
绝大多数情况下（至少是我遇到的所有情况下）并不需要莫比乌斯反演。

另外莫比乌斯反演有个很简单的 \(O(nlogn)\) 实现，不需要筛 \(\mu\) ，直接按定义枚举每个数的倍数去筛即可。

前置知识

首先要知道关于 多项式 的一些知识。

其次要对复数有一些了解。

点值表示法

从 多项式 中， 已经知道了多项式乘法的朴素算法时间复杂度为 $ O(n^2) $ 。 原因在于多项式是用系数表示法定义的。

重新定义 n 次多项式 a 为满足 $ k (http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform) 。

迭代实现

上述过程用递归实现常数较大，因而有一个迭代实现 FFT 的快速版本。

蝴蝶操作

FFT 的每个值都是由子问题的两个值转化而来，且这两个值可以转换成两个需要的值（ FFT 复杂度的保证）。 若用一个数组 a 表示多项式。 那么蝴蝶操作形如：

1
2
3
4

complex Wn; // 单位根的幂
complex a0 = a[x], a1 = a[y];
a[x] = a0 + a1 * Wn;
a[y] = a1 + a0 * Wn;

这样取出了数组中两个值后再修改相应位置的两个值，就是蝴蝶操作。

Rader 排序

Rader 排序的目的是让表示多项式的数组可以进行蝴蝶操作。

盗图一张：

摘自洛谷：

剩下的问题就是把初始的数组变成最后一层的样子了。
先别急着写一个递归函数暴力把位置换过去。
来观察一下最后序列的编号的二进制表示000, 100, 010, 110, 001, 101, 011, 111，
是不是与原来 000, 001, 010, 011, 100, 101, 110, 111 相比，
每个位置上的二进制位都反过来了？
这样的变化叫做 Rader 排序。

在数列 a 中,逆序对即是满足 \(i < j\) 且 \(a_i > a_j\) 的数对。 许多情况下你推式子推着推着就推出个 \(\sum_{i=1}^n \sum_{j=i+1}^n a_i> a_j\)， 这就是逆序对的数量。

暴力

朴素的求法自然是 \(O(n^2)\) 地枚举 \(i, j\) 统计，这里不再赘述。

归并

前置技能：归并排序。

这应该是最主流的求逆序对的方法了。

要求一个区间内的逆序对数，假设已经递归求出两个子区间的逆序对数， 接下来要做的就是求一个在左区间，一个在右区间的逆序对数。

考虑归并排序的过程，在两个指针比较大小时进行统计。

设左右区间的当前比较指针（下标）为 p1, p2, 当找到第一个 p2 使 \(a_{p1}< a_{p2}\) 时，可知 \(\forall i\in [p1max+1, p2),\;a_{p1}> a_{p2}\) 。 那么横跨两个子区间的以 p1 为左端点的逆序对就有 p2-p1max-1 个。 对所有 p1 统计和即可。

值得注意的是，p2>r（区间右端点）退出时， 此时左区间未处理的数对答案都有 r-p1max 的贡献因为此时左区间剩下的数都比右区间所有数大。

复杂度 \(O(n \cdot log_2n)\) 。

线段树/树状数组：

前置技能：线段树（或树状数组）。

以线段树为例。

做法 1

用线段树维护区间内有效数的个数。 之所以是有效的数，是因为要从小到大删数。 如果一个数 \(a_i\) 是最小的，那么以其为右端点的逆序对就是 1 至 i-1 的数的个数。

接下来呢？ 在线段树中删掉最小的数（单点修改 -1）， 那么第二小的数 \(a_j\) 在此时就是最小的数，同样有 1 至 j-1 的数的个数（区间查询）的贡献。 以此类推从小到大一个个删数即可。

复杂度\(O(n \cdot log_2n)\)。

做法 2

离散化后用线段树维护一个桶。

从左到右依次计算每个数为右端点的逆序对并加入桶，即对每个数求该数左边比该数大的数的个数。 设第 i 个数左边有 \(f_i\) 个比 \(a_i\) 大的数，那么 \(f_i\) 的值即是当前线段树上 \(a_i+1~a_{max}\) 的询问。

同样复杂度是 \(O(n \cdot log_2n)\)。

这种做法稍稍改变可以高效解决一种特殊的问题：

对于 01 串求串中 1 的数量比 0 的数量大的区间的数量。

比较容易想到的做法是将 0 看成 -1，区间中 1 比 0(-1) 多等价于区间和大于 0 。 区间和可以转换为前缀和 s，那么 l,r 这一区间和大于 0 等价于 \(s_r - s_{l-1} > 0 (r >= l)\)。 移项后即是 \(s_r > s_{l-1} (r > l-1)\)，所以题目可以转换为求前缀和的逆序对， 复杂度 \(O(n \cdot log_2n)\) 。

但是 这个问题有特殊性，由 01 串的至可知相邻两个前缀和的差值一定是 1 ， 利用这一个性质可以有更高效的方法。

用做法 2 求逆序对，从左到右依次扫，对于当前 \(a_i\) 一定比 \(a_{i-1}\) 大 1 或者小 1， 利用到这个差值，比 \(a_i\) 大的数相当于当前线段树 \(a_i+1\) 到 \(a_{max}\) 的询问， 若 \(a_i = a_{i-1}+1\) ，那么 \(f_{i-1}\) 就是 \(a_i\) 到 \(a_{maxn}\) 的询问，否则就是 \(a_i+2\) 到 \(a_{max}\) 的询问。 那么 \(f_i\) 与 \(f_{i-1}\) 的差只在 \(a_i\) 或 \(a_i+2\) 中，长度为一， 完全没必要用线段树，用数组维护桶即可。

复杂度 \(O(n)\)。

数论函数推式子是真的玄学， 乱七八糟的一脸懵逼， 好不容易看懂了转身又 tm 忘了， 这里列出一些我见过的。

持续更新。

update: 证明都删掉了，这是篇整理，目的是让结论更一目了然。需要证明联系我我免费讲解

常见数论函数卷积

\[ \mu \cdot I = \epsilon \]

\[ \phi \cdot I = id \]

\[ \mu \cdot id = \phi \]

\[ id \cdot I = \sigma \]

常见数论函数 f(ij) 化简

\[ d(i \cdot j) = \sum_{x|i} \sum_{y|j} [gcd(x, y) = 1] \]

\[ \sum_{d|ij} f(i \cdot j) = \sum_{x|i} \sum_{y|j} [gcd(x, y) = 1] f(\frac{iy}{x}) \]

\[ \phi(i \cdot j) = \phi(i) \phi(j) \frac{gcd(i, j)}{\phi(gcd(i, j))} \]

常见数论函数求和

\[ \sum_{i=1}^n d(i) = \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \]

互质条件转换

\[ [gcd(i, j) = 1] = \sum_{d|i,d|j} \mu(d) \]

\[ \sum_{i=1}^n \sum_{j=1}^m f(i, j) [gcd(i, j) = 1] = \sum_{d=1}^{min(n, m)} \mu(d) \sum_{i=1}^{n/d} \sum_{j=1}^{m/d} f(id, jd) \]

先喷一句，没有大样例，差评。
再喷一句，数据水，好评。

预计 80' ，实际 110' 。

我真是个奇葩实际分比预计分高。。。

Day0-

省选前三天教练每天给我们推一道题，都是主席树应用（教练曰“线段树模板”）。
都是看了题解的思路才做出来的，自己想就找不到用主席树维护的地方。

不知道为什么这三天效率都挺高，这三天我 A 的题目估计有我平常一个星期的 A 题数。。。

然而还没来得及复习每个知识点，省选就来了。

Day1

预计 70' ，实际 40' 。

fish

我看到这题的时候就意识到我只能打暴力了。
计算几何？我对这块一片空白。
好吧，硬要说思路我大概想得到枚举线段，按斜率搞个什么数据结构？
然后真的不会，敲暴力滚粗。

预计 20' ，实际 20' 。

jojo

前缀和后缀相同？求 KMP 的 fail 数组嘛。
暴力求，一次加几个字符就求几次 fail, 全加起来就是答案。
可持久化？版本树像个 AC 自动机，但是没管这么多，无脑写了个可持久化数组。
因为是把每个字符暴力求的，只能过前 50' 。 结果我后面 30' tm TLE 了？ $ O(n log(n)) $ 的时空复杂度跑 1e5 要 6 秒？

预计 50' ，实际 20' 。

polygon

什么鬼畜题啊，简化一波题意。
把线段看做一个区间，除 (x, x + 1) 外每个区间一定可以划分成两个子区间。
然后把每个区间看做一个点，相当于有了一个满二叉树。
然后旋转操作就相当于把一个点 blablabla 换一下位置。
旋转次数可以贪心，方案数不会，大概要 DP ？
然后想着就求旋转次数吧，看看数据范围。。。
沃日 90% 的数据都要求方案数？小 W 的心情得多差啊。。。
当时我还没打其他题，感觉比较亏，就先做前面的题了，结果最后都没打。

预计 0' ，实际 0' 。

Watering

下午直接去机房颓废，死神 vs 火影真好玩。
还有被 lyy 安利太阳系争夺战，画风清新，内容硬核。

Day2

emm, 我是来测数据湿度的。。。
结果真被我水过去了。。。

预计 10' ，实际 70' 。

所以说有想法就要实现 不然就没事干了 2333 。

tour

u = v 或者 s[u] = s[v] 且 u, v 相邻的时候 (u, v) 一定是可行的。
其他点对 (u, v) 可行当且仅当 s[u] = s[v] 且存在 u -> u2, v -> v2 且 (u2, v2) 可行。
DP ？有环。
然后就只能把一个点对看做一个点，对于新的点建图，如果从初始的可行点能跑到 (u, v) 则 (u, v) 可行。
点数 $ O(n^2) $ ，边数 $ O(m^2) $ ，复杂度 $ O(n^2 + m^2 + q) $ 。
然而第一档暴力 m 就有 1e4 ， 纯随机数据开O2 本地测了一下跑 5s, 真棒。

预计 0' ，实际 30' 。

dance

好迷啊，看了看 n = 1 有 40' ，就去想 n = 1 怎么做，
推了推就是个式子： $ ans_i = _{j=0} C_L^{i+j k} W^{i+j k} $ 。 把每个 $ C_L^x W^x $ 算一遍，快速幂复杂度 $ O(L log(L)) $ ，
然而 L 有 1e8 。。。
线性都跑不过去吧这，但我实在没别的思路，就想试试线性。
做法就是预处理，预处理 L 以内的逆元和 $ W_i $ ，再线性求一排的组合数。
时空复杂度都是 $ O(L) $ ， 开 O2 本地测试 17s, 就算不 TLE 都得 MLE 。

预计 0' ，实际 30' （考完后再放本地测可以水 40' woc）。

看了看实际的 L 只有 1e7 到 2e7 左右，真棒。 至于空间，我还算有点脑子搞了波动态开空间，不然直接开 1e8 的数组肯定得炸。

sequence

b 是整数的话还能枚举枚举。分数？没救了感觉。
于是只打了 10' 的整数 DP 。

预计 10' ，实际 10' 。

Watering

下午本来打算去黄兴街打游戏的，先去麦克唐纳德吃中饭，吃完后发现就已经 3 点多了没什么时间。
于是放弃了 xbox 又回到机房颓废，死神 vs 火影昨天已经玩熟练了，打起来比较轻松。

Day3+

省选完了，结果并不想想象的那样，即使运气眷顾了我还是 wei 的一批。
实力不够啊，说啥都是扯淡。

常规欠下的帐也该还了，滚回去学文化课啦，接受作业的洗礼。

One Year Later

update on 2020.04.08

一年过去了，重新审视了去年的 HNOI ，再次分别总结一下吧。 （从去年省选到现在，这些题碰都没有碰过）

新一轮省选不远了。

fish

咕咕咕。

jojo

去年，我甚至不知道均摊数据结构是不能可持久化的，打了一个主席树满以为复杂度一个 log 。
可事实上 KMP 的最坏复杂度是 \(O(n)\) ，可持久化后复杂度可以到 \(O(n^2)\) 。

可是现在我还是不会做 jojo ，甚至看题解也看不懂，现在上考场估计也还是 20pts 。

polygon

这题不难的啊，至少现在我看来如此。
不考虑修改的话就可以分治处理这个问题，考虑上修改就动态维护分治的树状形态即可。
而方案数就是分治树的拓扑序数量。

A 了，现在上考场有信心拿到 100pts ，只不过可能得花上至少 2h 的时间。

tour

思路很妙，同类型的边的偶环是没有意义的，可以删边使得同类型的边偶环不存在进而把边数控制在 \(O(n)\) 。
可惜我没能独自得到这个结论，还是看了题解的，看了后有一种恍然大悟的感觉。

现在上考场也许还是只会 \(O(m^2)\) 暴力吧，时间足够的话说不定能想到正解，但没有把握，大概拿 30pts 。

dance

现在看来这个式子并不难推，推完后就是对一个多项式求单位根上的点值。
但是在直到看题解前我都完全没听说过 bluestein ，算是技不如人，只能拿 60pts 。

sequence

花了 30min 打了个 50pts 的暴力 \(O(nm)\) ，发现简直白给。
不过 100pts 确实难了不少，我觉得就算考场想到了也无法在考试时间内写对。