- 阅读剩余部分 -

在 Codeforces 上看了一些新姿势，但还不是很懂，先备份一下
[[1]Efficient and easy segment trees](http://codeforces.com/blog/entry/18051)
[[2]Non-recursive Implementation of Range Queries and Modifications over Array](http://codeforces.com/blog/entry/1256)
注意他们用的是左闭右开区间，我们的zkw用的是全开……

总体说来比我平时实现的 zkw 多了一些良好的特性

• 空间非强制2的幂
• 支持懒标记（要维护点到根的前缀和，代码还没看懂……）

懒标记真没懂啊……
[1]中用d[]维护当前点tag，t[]维护当前点和；每次modify()的时候两端点从根push()下来到全部结点，然后处理完后再build()上去。
这里一个疑问就是build()只对直系祖先进行更新，而被修改结点不在端点的直系祖先里啊……他们的祖先没有更新到啊……

[UPD]懂了懂了。这两次build()保证了所有标记的最顶上的节点的父亲会被更新到。往上均是正确的标记，而每次query()的push()会将这些还未向下更新的标记下推并更新，正确性得到！

这样一来有标记下传就无需标记永久化了~没有了普通zkw标记必须满足无覆盖性的要求~
欸等等push()真的不是 $ O(|r-l|)=O(n) $ 的吗！？？？？

[UPD]想了一中午，感觉可以这么做：
考虑各标记之于待查询区间的关系。
1° 完全被待查询区间包含：结点值已是最近，毋需下推。
2° Otherwise: 注意到结点所用到统计的量的结点是左右端点直系祖先的兄弟节点。只对左右祖先到根的链从上到下进行下推即可，就可以保证复杂度为$ O(\lg n) $了。

啊啊不太想特别去实现呢~遇到题再说吧~

逛知乎看书发现了一些有趣的结论。
没有时间去研究背后的学科分野，但还是得做点笔记才能不会忘记啊w
大概覆盖面……初/高等数学、离散数学方向的吧……
还有一些高中各科的……嗯……姑且称作是技巧方面的工具吧。
说不定还有解析图论之类的黑科技呢x

离散数学

Theorem 1.1 最小链覆盖=最长反链
Theorem 1.2 (Sperner's) 有限集的子集族中两两不包含的子集族的个数是 $ {n} \choose {\lfloor \frac{n}{2} \rfloor} $
1、2的推论是两两包含的最小覆盖数的个数也是可以求的。

他学科技巧

自动配平基

Definition 2.1 矩阵$ \mathbf A $的零空间（null space）指$$ ker(\mathbf A)=\\{ \mathbf x \in \mathbb C^n : \mathbf A\mathbf x=\mathbf 0 \\} $$
一个例子是高斯消元中系数矩阵与值向量构成的增广矩阵即是此处 $ \mathbf A $ ，解即为 $ \mathbf x $.
但这里毋需方阵，即允许存在自由变量。

Example 2.1 离子、化学方程式的配平。已知生成物和产物，将各粒子作为各列，各元素和电子作为各行，每个矩阵元素表示粒子中各元素的个数，由元素守恒定律和电子守恒定律易得该矩阵零空间即为化学式/离子式中的各项系数。自由变量即为催化剂。
来看这张表，这是酸环境下高锰酸根与亚硫酸根发生反应：

$$ \begin{array}{c|cccccc} n & \text{MnO}\_4^- & \text{SO}\_3^{2-} & \text{H}^+ & \text{Mn}^{2+} & \text{SO}\_4^{2-} & \text{H}\_2\text{O} \\\\ \hline \text{Mn} & 1 & 0 & 0 & 1 & 0 & 0 \\\\ \text{O} & 4 & 3 & 0 & 0 & 4 & 1 \\\\ \text{S} & 0 & 1 & 0 & 0 & 1 & 0 \\\\ \text{H} & 0 & 0 & 1 & 0 & 0 & 2 \\\\ \text{e}^-& -1 & -2 & 1 & 2 & -2 & 0 \\\\ \end{array} $$

零空间为$ \mathbf x=k (2, 5, 6, -2, -5, -3)^T $，即
$$ 2\text{MnO}\_4^- + 5\text{SO}\_3^{2-} + 6\text{H}^+ = 2\text{Mn}^{2+} + 5\text{SO}\_{4}^{2-} + 3\text{H}\_{2}\text{O} $$
继续考虑反应物为$ \text{C}, \text{O}\_{2} $ ，生成物为 $ \text{CO}, \text{CO}\_{2 }$ 的反应：

$$ \begin{array}{c|cccc} n & \text{C} & \text{O}\_{2} & \text{CO} & \text{CO}\_{2} \\\\ \hline \text{C} & 1 & 0 & 1 & 1 \\\\ \text{O} & 0 & 2 & 1 & 2 \\\\ \end{array} $$

解得$ \mathbf x={{k_1(-1, -1, 0, 1)} \choose {k_2(-2, -1, 2, 0)}}^T $.我们知道这个反应物有两种可能，一种只生成$ \text{CO} $，一种只生成$ \text{CO}_2 $，剩下的就是二者的线性组合；而零空间可以帮我们直接分解好线性基的这两个部分。

Example 2.2 物理公式的推算。给描述某物理过程的若干物理量，求该过程某个未知物理量的表达式。物理量一多不知道怎么推的话我们回想从单位入手……将各物理量单位作为列，国际标准单位作为行就和配平一样了……
已知$ t, r, p, \rho $，求 $ E $。

$$ \begin{array}{c|ccccc} n & E(J) & t(s) & r(m) & P(Pa) & \rho(g/m^3) \\\\ \hline L(m) & 2 & 0 & 1 & -1 & -3 \\\\ M(g) & 1 & 0 & 0 & 1 & 1 \\\\ T(s) & -2 & 1 & 0 & -2 & 0 \\\\ \end{array} $$

解得$ \mathbf x=(^{k_1(-1, -2, 5, 0, 1)}_{k_2(-1, 0, 3, 1, 0)})^T $.多出来一组基说明条件给多了……看着用就可以了……

以上为待定系数法使用线性代数观点以及各学科归一化式子的一般化结果。是不是看起来比起以前的办法简单呢？但是首先，你得会手算零空间……
用程序实现也特别简单，名字就叫 自动配平基！
参考了这个知乎答案.

- 阅读剩余部分 -

看很多人都被数列折磨的很惨，但实际上这个时候缺少的应该是一个高观点的领悟。
这种领悟可是做多少归纳都难以企及的。所以我来造福一下大众。

数列教程

基本定义

数列是一列数按顺序的排列，分别记作 $ a_1, a_2, \cdots, a_n $，一般简写为 $ \\{ a_n \\} $。
数列可以看作定义域在正整数的离散函数。

事实上，数列与函数之关系将会是我们认识连续量与离散量的第一步。后续我们将进一步探讨他们的关系及各自的性质。

通项公式是一个式子用来给出数列中任意项 $ a_i $ 关于 $ i $ 的关系的式子，即 $ a_i = f(i) $。由形式上可以轻易看出在函数中它被称为解析式。

在不混淆的情况下，下面将不对数列与定义域在正整数的函数做更多的区分。

上面是高中课本出现的术语，接下来将不限于此。

进一步的定义

差分是对数列相邻两项做差得到的新数列，即 $ b_i=\Delta a_i=a_{i}-a_{i-1} $。
求和/累和/和分/前缀和是数列的前若干项的和，即 $ a_i=\Sigma b_i = \Sigma_{i=1}^n b_i $。
注意变化后定义域带来的变化。

解数列是指给出原数列各项满足的关系，需要由这些关系得到原数列的通项公式。若这个关系中含有数列的其他项，则这个形式被称为差分方程（离散）/递归方程（离散/连续）/迭代方程（离散/连续） / 函数方程（连续）。
事实上连续的定义均可被离散套用，上面只是注明语言上的偏好。

解数列

高中研究的内容。

情形1 $ a_n=a_{n-1}+p, a_1=a $

易知 $ a_n=(n-1)p+a $。

情形2 $ a_n=pa_{n-1}, a_1=a $

易知 $ a_n=ap^{n-1} $。

情形3 $ a_n = pa_{n-1}+q, a_1=a $

考虑待定系数转为形式1或形式2，有$ a_n-r=s(a_{n-1}-r) $，易得$ s=p, sr+r=q $