HNOI 2016 解题报告
Tuifei_oier
不得不说 HNOI 2016 不愧为数据结构场，几乎每道题都沾点数据结构，出现最多的算法还是莫队和分块这类根号科技。
6 题做完下来还是颇有收获的。
T1 网络
这道题还是偏重于应用，没有太套路的东西，但是用到了一个可能容易被遗忘的小 trick。
考察点：线段树上二分+LCA。
首先想到用二分答案来转化问题，即检验是否权值 \(\ge mid\) 的路径都经过了点 \(x\)。
然后，关键在于如何检验，考虑维护一棵以权值为下标的线段树，每个节点维护路径交。
我们可以快速地求出树上两条路径的交，显然路径交还是路径，可以把二分过程搬到线段树上，于是这道题就做完了。
时间复杂度 \(O(n\log n)\)。
关键还是要想到可以用线段树维护路径交的想法。
T2 大数
也是偏向于应用的，着重于锻炼思维。
考察点：分析+数据分治+莫队。
考虑答案的计算，设 \(f_i\) 为 \(1-i\) 这个前缀组成的数，则：
\[\sum_{i=l}^r\sum_{j=i}^r[f_j\equiv f_{i-1}\times10^{j-i+1}(\bmod p)] \]于是，我们考虑两种情况：
- \(p\not|10\)。
- \(p|10\)，即 \(p=2\) 或 \(p=5\)。
第一种情况，有 \(f_j\times10^{-j}\equiv f_{i-1}\times10^{1-i}\)，相当于询问区间内有多少个同余的数 \(f_x\times10^{-x}\)，可以方便地用莫队来维护，时间复杂度 \(O(n\sqrt n)\)。
第二种情况，我们只需算出区间内有多少个以 \(0,2,4,6,8\) 或者 \(0,5\) 结尾的子串，随便做一下就可以了，用树状数组可以做到 \(O(n\log n)\)。
T3 矿区
这道题就偏向于考察知识点了，在了解知识点后就比较模板了。
考察点：平面图转对偶图。
首先不难想到每次相当于要求一个连通块内的面积平方和与面积和，考虑首先转对偶图，每个节点就可以算出它代表的原图中的区域的面积及面积平方。
对于平面图转对偶图，关键的想法在于规定方向性，对于这道题，由于询问的输入是逆时针给出，我们考虑一种这样的构建方式以方便查询：每条双向边拆成两条单向边，每条边求出一个后继边：\((u,v)\) 的后继定义为将边 \((v,u)\) 绕着 \(v\) 顺时针旋转碰到的第一条边。如图所示：
\((s,t)\) 的后继为 \((t,w)\)，\((v,t)\) 的后继为 \((t,s)\)。
如果把每个点的出边极角排序，实际上，当前边的后继就是反边的上一条边。
这之后，如果从任意一条边出发，不断走后继，最终一定会回到该边，并且此时围出的闭合图形就是对偶图上的一个点，并且由于我们的构造方式，每个有界域的边界都是逆旋转的，而最外面的无穷域为顺时针旋转。
这样，我们就可以 \(O(m\log m)\) 建出对偶图。
考虑查询，我们每次询问一个封闭图形，在对偶图上就是一个割边形成的连通块，并且无穷域永远不会出现在这个连通块中。
因此，我们以无穷域为根，任意建出一棵对偶图的生成树，求出子树的面积和与子树面积平方和。
询问给出的每一条边看成是割掉对偶图上的边，因此：
- 如果询问的边不是树边，忽略。
- 询问的边为树边，则我们割断这条树边，判断这条边连接的两个节点中我们是要计算父亲的答案还是儿子的答案，然后计入答案即可。
时间复杂度 \(O(Q+m\log m)\)。
这道题最关键的地方在于两点：对偶图的建立和割边模型的转化，主要是积累对偶图的建立方式了。
T4 树
比较有意思的一道题，有两种可能做法。
考察点：主席树求静态区间第 \(K\) 大+树上 LCA。
一个暴力的做法是可持久化平衡树维护欧拉序，时空复杂度均为 \(O(n\log n)\) 级别，在此不多赘述。
考虑一个简单一些的做法，我们维护一个“树套树”，即维护一棵大树，大树上每个节点都是一棵模板树的子树。
这样一来，问题就简单了，我们只需要每次询问时先在大树上倍增，跳进同一个节点后再在小树中倍增即可，处理好一些细节就行了。
时空复杂度 \(O(n\log n)\)。
关键点是维护大树和小树的想法。
T5 最小公倍数
一个据说很经典的 trick，主要是学习这个套路。
考察点：分块+并查集。
实际上我们是要查询一个矩形中所有的修改是否能够连通点 \(u,v\)，且 \(u,v\) 所在的连通块满足某些要求。
对于这类含有两种属性 \(a,b\) 的问题，一个常用的处理方法是：首先将修改按 \(a\) 排序，将询问按 \(b\) 排序，然后将修改分块，把每个询问放到编号最大的 \(a\) 维度符合条件的块中。
处理一个块内的询问时，首先将之前块的所有修改按 \(b\) 排序，此时 \(a\) 维度必定满足条件，而 \(b\) 维度单调，就可以用双指针法插入所有满足当前询问的修改。
然后，对于每个块内询问，考虑同一块内的修改的影响，暴力插入满足条件的修改即可，之后再暴力删除。
这样子的复杂度为 \(O((\dfrac{m^2}{B}+QB\times g)\times f)\)，其中 \(f\) 为应用修改的复杂度，\(g\) 为查询的复杂度。
对于这道题，我们也可以这样处理，用可撤销并查集维护连通性和连通块信息，时间复杂度为 \(O(\dfrac{m^2}{B}+QB\log_2n)\)，取 \(B=\sqrt{m\log_2n}\) 时复杂度最优。
T6 序列
这道题也是侧重于思维。
考察点：预处理+单调栈。
首先，我们可以对每个点用单调栈处理出其左边第一个比它小的位置，记为 \(pre_x\)。
接着，考虑一个这样的 DP：\(f_x\) 表示区间 \([1,x],[2,x],...,[x,x]\) 的贡献和，则转移：
这之后，我们对于一个区间，首先求出区间最小值所在下标 \(p\)，那么所有跨过 \(p\) 的区间答案都为 \(a_p\)，还需考虑左右端点都在 \(p\) 左边、右边的情况。
以都在右边为例，此时的答案应为：
左边类似。
使用 ST 表求区间最值，时间复杂度为 \(O((n+m)\log n)\)。
解题关键在于从最小值入手，分别考虑左右。
这一年的考题数据结构的成分是相当浓的，因此码量也不小，但整体上难度并不算太大，也积累了一些方法和套路。