2023.3 做题记录

注：只摘录具有较高思考价值以及较高思维含量的题目（说白了就是颓出来的题）。

[JSOI2008] 火星人

我们只考虑查询操作，方法很多，例如 KMP、哈希、SA。

此时考虑修改，由于 KMP、SA 不好维护修改后的数组，因此考虑哈希。

我们利用二分答案的方式求出长度，利用哈希检查即可。

现在考虑 2,3 操作，由于有插入，我们考虑用平衡树维护哈希值。

显然如果这样考虑，我们是按下标排序。

接下来考虑如何求出哈希值，也就是怎么写 pushup。有下列式子：

这样我们利用平衡树维护一下就行了。

• 注意不保证 \(x<y\)
• 注意 \(x\) 可能是叶子结点，因此修改时需要同时修改 \(val\) 和 \(hs\)。

[TJOI2013] 最长上升子序列

首先有这样一条显然但就是看不出来的性质：

新插入的数必然比前面的数要大。

因此根据朴素的转移方程 \(dp_i=\max\{dp_j\}+1\)，我们只需要将当前位置前面的最大值加一就是当前位置新的 \(dp\) 值。

又由于上面的性质，所以只会影响当前节点，对前后都没有影响。

接下来考虑插入操作，显然使用平衡树。

那么我们使用区间平衡树维护区间最大值，也就是维护 \(dp\) 和 \(maxdp\)。

此时两者的求法就很显然了。

星系探索

（其实这道题 \(80\%\) 都是自己想的）

首先这是一个树上问题，并且不能用树剖简单求解。

考虑将这棵树转化为序列。那么常用方式有两种，DFS 序和欧拉序。

经过一点点推理可以发现，欧拉序实现起来较为简单。

如果你学过树上莫队，那么应该对欧拉序的处理方式比较熟悉。将第一次出现的位置 \(st_i\) 记为正，第二次出现的位置 \(ed_i\) 记为负。

于是查询操作就很简单了，对区间 \([1,st_i]\) 求和即可。

同时子树修改也应该较为简单，将区间 \([st_i,ed_i]\) 内的元素加上 \(q\) 即可。

现在就剩下换父亲了。经过模拟以及一些感性理解可以得到，将 \(x\) 的父亲换成 \(y\) 在欧拉序上表现为将区间 \([st_x,ed_x]\) 移到 \(st_y\) 的后面。

（其实也可以是移到 \(ed_y\) 的前面，区别就在于你接到哪个子树上）

对于这种平移区间的问题，考虑平衡树求解。

Splay 可以维护，但是 FHQ-Treap 可以直接分裂合并，比较方便。

剩下的全是细节了。

（好像这是一个数据结构叫 ETT）

• 注意要开 long long。