Ruins He's house

这段时间老是有许多新人向我问到 ACM 相关的问题。比如它与工作的关系，对我以后的工作到底有没有帮助？还比如说第二年的训练计划应该是什么样的？还有的孩子问到，我寒假玩儿的一个寒假，又该怎么办？

看到这些问题，我自己也感慨万千，一眨眼自己在这方面也涉猎了两年多了，经过那一段时间的纠结，最终还是决定第三年继续。大家选择 ACM 的理由的很多很多，为了以后方便找工作？充实生活？巩固学科基础？不管是为了功利心理也好，还是纯粹的兴趣也罢，最后共同的结果就是我们选择了 ACM 作为自己大学生活的一部分。

这题很经典的动态逆序对问题，我们可以利用树套树来解决它，首先我们得到一个总体的思路

对于每一个操作，我们先利用树状数组求出一个逆序对，然后进行查询统计，对于每一个删除操作，我们只要查询这个元素之前的比它大的还有后面的比它小的有多少，逆序对就减少多少，这个操作可以利用树套树搞定

lrj 的题好囧，这题线段树一直 T，后来想到可以用区间的加减性，写了一个树状数组套平衡树就过了 - -

好久没有写博文了，这题是刚才被 lrj 的题虐了之后写的，这题的题意是告诉你 $N$ 个数的序列，每次修改一个位置的值，动态查询区间第 $k$ 个元素

做法是维护一个线段树，这样我们就可以得到区间的信息，但是这时候我们并不能维护区间有序的序列，所以我们要二分答案，查询 $l$ 到 $r$ 区间内比这个数小的有多少，和 $k$ 做比较，然后最后得到答案，写起来就是一个线段树和一个平衡树，对于平时写数据结构写多的来说代码量一般，我的代码一向都很长，写了 200 行左右。

好吧，这场比赛被完虐，3+3 来的太不容易了，这题在之前见过类似的问题，不过那题至今没过，还是处于 TLE 的状态 - -

题号是 UVA11996，感兴趣的孩子可以去写写

这题的主要思路是利用 splay 维护序列，对于 reverse 和 modify 操作都可以直接利用 splay 来维护，主要的问题是 lcp 的求法，lcp 比较直接的做法是二分长度，然后利用 splay 维护 hash 值。利用数据结构来维护 hash 值，这个在多校里面见过好多次了，最近的一场是 FZU 的 B 题？维护的是前缀 hash 值，和后缀 hash 值 (为了翻转操作)，判断区间的 hash 值是否相同即可，保险一点可以用双 hash。

Manacher 对于最长回文的求法，可以使用 $O(N)$ 的 Manacher 算法 ^[1]。

相对于那些大代码量的题，这题算是较短代码了，主要处理好 splay 的部分，对于求回文，直接把 splay 进行 dfs 下放，然后得到字符串，然后执行 $O(N)$ 的回文即可。

这题需要注意的地方如下：

dfs 的时候要下放，否则会有问题

$l$ 和 $r$ 需要交换，如果 $l>r$ 的话

代码量在 280 左右，splay 的标准线

在图论中经常遇到一些很常见的问题，比如一个非常简单的例子，给你一棵树，每一个点都有一个权值，现在动态更新一个点的权值，叫你查询一个点对路径上所有点权的和，这种问题和图论的 Tree  Problem 非常类似，我们可以利用树形结构转线性结构的方法来处理，我们考虑随便取一个点，比如说 $1$，作为根，这样我们就可以得到一个 DFS 序列，注意我们维护一个长度为 $2 \times N$ 的 DFS 序列，每次访问开始的时候，向序列中加入一个等于当前点权的元素，每次结束这个结点访问的时候，我们加入一个等于当前点权相反数的元素，举一个很简单的例子。

1
2
3
4
5
6
7
8

我们考虑边的序列是这样
3
1 2
1 3
点权是
5 7 10
那么我们得到的序列有可能是
5 7 -7 10 -10 -5

注意一个非常好的性质，我们记录访问开始的时候加入的元素的下标，那么我们可以非常快的利用前缀和来计算出根到一个点的路径上点权和是多少，还是上面的例子，点权和的答案是

1
2

2 : [5 7] -7 10 -10 -5 = 12
3 : [5 7 -7 10] -10 -5 = 15

这样，我们可以维护一个线段树或者树状数组，对于更改点权的操作，假设我要把一个结点点权改成 v，我们在开始访问对应的下标处，把元素值改成 $v$，在其结束访问对应的下标处把元素改成 $-v$，这样还是保证了括号序列的匹配性。

对于查询操作，假设我要求 $u$ 和 $v$ 路径上全部结点的权值之和，我们可以求出 $u$ 和 $v$ 的 LCA，我们记录为 $t$，那么我们可以求出根到 $u$、$v$ 和 $t$ 的权值之和，答案就是 $\sum{u}+\sum{v}-2 \times \sum{t}+w_t$，注意不要忘了加上那个 $t$ 的权值。

此外，Tree Problem 也是一个很经典的问题，对于 Tree Problem，我们可以只记录入点，不记录出点，但是要记录每一个点的管辖范围，注意一个点的子树在 DFS 序列中一定是连续的，那么我们就可以记录下这个点的管辖范围，然后利用树状数组维护这个序列，区间查询就可以了，至于需要查找大于其标号的点的个数， 做法大家应该是都知道了的，还不是很清楚的同学可以自己再想想。

类似的问题有 POJ 的一题，叫做 Apple Tree，可以去做做。

树形结构转线性结构在关于树的统计问题中还有非常多的运用，暑假的时候，大家如果有兴趣，可以去看看，做法很巧妙，代码量不大，是此类问题的共同性质。

所谓的括号序列，就是将一个树形结构转化为线性结构，然后通过线性结构间接地对结点和路径的更新和查询操作。