初步认识树上差分
学习树上差分的前提是：
- 最近公共祖先（LCA）
- 线性差分
学习了这些之后，我们就可以开始学习树上差分了。树上差分的思想跟差分类似：都是在不得不求前缀和的情况下，将区间操作变为单点操作，降低复杂度。树上差分曾两次在 NOIp 系列比赛中出现过，所以学习树上差分很有必要（我怀疑是出题组不敢出树链剖分，但又要考察选手们对树上操作的熟悉程度，所以采用了这么个坑爹玩意）。我们先来学习一个基本的操作：点的链上区间加。
P1829:「国家集训队」Crash 的数字表格题解
主要思路
首先规定，\(N<M\)。之后写出统计答案的式子：
\[ \sum_{i=1}^N \sum_{j=1}^M lcm(i,j) \\ \sum_{i=1}^N \sum_{j=1}^M \frac{ij}{\gcd(i,j)} \]
然后我们可以试着去枚举最大公约数\(gcd(i,j)=d\)，然后让\(i,j\)成为唯一的两个互质因子。
P3327:「SDOI2015」约数个数和题解
主要思路和推导
这道题还是比较有意思的（啊呀看了好久的题解才会写，真菜），主要就是把\(d\)转换成了：
\[ d(xy) = \sum_{i|x}^x \sum_{j|y}^y [\gcd(i,j) = 1] \]
可以感性理解一下：每一次约数被枚举出来的时候，只有互质的情况下才会被计数，避免了重复计数。 Continue reading →
P2257:YY 的 GCD 题解
LibreOJ 6005:「网络流 24 题」最长递增子序列题解
主要思路
这道题还是很有意思的，建图方式非常的巧妙。首先我们先把第一问的 DP 用 \(O(n \log n)\) 的时间求解一下，顺便搞到一个数组\(f[i]\)，含义是以\(i\)为结尾的最长子序列长度。建图的时候要注意的是，每一个位置对应的点要拆成两个：这是为了保持答案的唯一性。所以对于\(f[i]=1\)的点\(i\)，连边\((s,i)\)；对于\(f[i]=k\)的点\(i\)，连边\((i+n,t)\)。之后，如果对于\((u,v), f[v] = f[u] + 1, arr[u] \leq arr[v]\)进行连边，跑个最大流就可以出答案了。
第三问其实跟第二问的差不多，只需要把点\(1\)和点\(n\)的外向边（到源点或者是汇点的边）的最大流限制改成无穷大即可。
三月份总结 & 新阶段的开始
好久没写博客了，最近忙文化课去了所以没有更新博客。这个月过的还挺好的，学了好久的文化课，被班上巨佬各种吊打，最后月考直接爆炸。这也算是比较平常的事情了，绿茵杯的足球赛还蛮有意思，我班神仙踢得很好。
所以这个月的 OI 基本上碰都没碰，除了参加了一次让自己瞬间自闭的模拟赛之外，就没有其他的事情了。中午和晚上都会在机房度过，神仙学长有的时候会来机房对我进行嘲讽。所以呢，nothing special.
XG 和 crazydave 都去集训了，机房里一直没人，除了一次 Reta 上楼跟我聊了半个晚自习的天。所以，机房就我一个人，比较惨。
月考爆炸之后，我开始对停课的四月份进行规划：
OI
这个月的主要内容就是数学和数据结构了，要了解（模板题&基础题过做掉）的东西如下：
- 离散数学：Catalan 数、生成函数初步、矩阵树定理、母函数、两类斯特林数、容斥原理初步、反演、卷积
- 数据结构：线段树合并、FHQ-Treap、Splay（这俩玩意能搞定我心满意足了）
要掌握（综合题&毒瘤裸题做掉）和复习的东西如下：
- 网络流 24 题之前 18 题
- 数学：莫比乌斯反演、Catalan 数、生成函数初步、矩阵树定理、母函数、两类斯特林数、容斥原理初步、数论杂题
- 数据结构：FHQ-Treap、Splay、李超树、线段树进阶、线段树合并