更新于 2016 年 12 月 28 日。

树链剖分是一种维护树上路径信息的算法，它将一棵树剖分成一些不相交的链，保证每个点在且仅在一条链上。并通过线段树、树状数组等数据结构维护每一条链上的信息。

在 OI 竞赛中，可以使用的语言有 C++、C、Pascal，其中 C++ 最大的优势是，它本身提供了一个模板库 —— Standard Template Library（标准模板库），简称 STL。STL 包含一系列算法和容器等，合理地使用 STL，可以在提高编写代码的效率。NOI 系列比赛自 2011 年起允许 C++ 选手使用 STL，所以我们应该利用好 STL，发挥 C++ 语言的优势。

在 Splay 学习笔记（一）中，我们学会了用 Splay 维护二叉排序树，来实现了有序集合的查询 / 修改操作，接下来，我们来研究 Splay 在维护数列中的用途。

上周周四开始学 Splay，一边看《高级数据结构》，一边看 FireStorm 的《Splay学习笔记》，现在终于弄明白最基础的一部分了。

模板请见《Splay 模板 + 详细注释》。

有 N（<= 80000）个宠物或领养者，每个宠物或者领养者有一个特点值 a，每次当宠物或领养者到来时，从已有的当中匹配一个与其特点值相差最小（且特点值较小）的并删除，计算所有的领养特点值差的总和。

背包体积为 V（<= 200,000），给出 N（<= 200）个物品，每个物品占用体积为 Vi，价值为 Wi，每个物品要么至多取 1 件，要么至多取 Mi（> 1）件，要么数量无限，求装入背包内物品总价值的最大值。

有 30000 个元素，初始时每个元素以单独的队列形式存在，支持一下两种操作：

1.动态合并两条队列，将 x 元素所在队列首合并在 y 元素所在队列尾； 2.查询 x 与 y 是否在同一条队列中，若是，查询 x 与 y 间隔元素数量。

共 500,000 次操作。