在 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 次操作。