集训队作业解题报告

1、IOI2009国家集训队作业：otoci解题报告 广东中山一中 方展鹏Otoci解题报告广东中山一中 方展鹏题目描述给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作：1、bridge A B：询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”，并且在结点A和结点B之间连一条无向边。2、penguins A X：将结点A对应的权值wA修改为X。3、excursion A B：如果结点A和结点B不连通，则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。给出q个操作，要求在线处理所有操作。数据范围：1 n 30000,

2、 1 q 300000, 0 wi 1000。时间限制：5s算法分析不难看出，由给出的n个点构成的图在任意时刻都是一个森林。并且由于已经添加的边不会被删除，所以对于任意两个结点x和y，如果在处理完第i个操作后，结点x到结点y的路径为P，那么在处理完第i(ii)个操作后，若结点x与结点y连通，那么结点x到结点y的路径依然为P。因此，如果题目不要求在线处理所有操作，我们可以用如下算法解决本题：1、先读入所有操作，然后利用并查集将处理完所有bridge操作的森林S构造出来。这步的时间复杂度为O(q+n)。2、对于森林S中所有的树T，确定一个根，并且求出T的DFS序列。然后对于每个DFS序列都建一棵线

3、段树，维护DFS序列中某一段序列的结点对应的w值的和。这步的时间复杂度为O(n)。3、对于每个结点x，求出x向上“跳”2k条边后到达的结点的编号。这步是为求LCA做好预处理，时间复杂度为O(nlogn)。4、从前往后处理每一个操作。对于bridge操作，我们可以通过并查集维护连通性来处理，这样处理单次bridge操作的时间复杂度为O(1)。对于excursion操作，我们可以先通过并查集确定连通性，如果不连通则直接输出“impossible”。否则，通过用线段树维护的DFS序列，我们可以较快地求出结点x到它的祖先的路径上的点对应的权值的和。因此，对于操作excursion X Y，我们可以先求

4、出结点X和结点Y的最近公共祖先Z。那么问题就转化为求X到Z以及Y到Z的路径上的点对应的权值和，这个问题可以通过线段树轻松解决，这样处理单次excursion操作的时间复杂度为O(logn)。而对于penguins操作，我们只需要在线段树上修改就可以了，因此处理单次penguins操作的时间复杂度为O(logn)。综上，这步的时间复杂度为O(qlogn)。整个算法的时间复杂度为O(nlogn+qlogn)。虽然题目要求在线处理所有的操作，但是我们依然尝试用上面所说的离线算法的框架来解决这道题目。如果我们依然使用上述算法的框架，下面我们来看看需要维护哪些信息。首先，我们需要知道结点之间的连通情况；

5、其次，为了较快的求出LCA，我们需要知道每个结点x向上“跳”2k条边后到达的结点的编号；最后，我们还需要知道当前所有树的DFS序列以及需要一种较为高效的数据结构来维护某一段序列中的结点对应的权值的和。有了这些信息，我们可以很容易地处理掉excursion操作，因此下面我们主要讨论如何比较高效地维护这些信息。对于penguins操作，只需要维护DFS序列的数据结构支持比较高效的修改操作就可以了，而这一点很多数据结构都可以做到，因此下面我们着重讨论如何处理bridge操作。我们先来看一个例子，看一下bridge操作后DFS序列发生了什么变化。不难看出bridge操作实际上就是重新构造一段DFS序列

6、，然后将该序列插入到另一段DFS序列中的某个位置。另外，我们不难发现bridge操作每次都是将两个不相交的结点集合合并。因此，在处理bridge操作时，我们可以采用启发式合并 合并两个不相交集合时，将大小较小的集合中的元素逐个添加到大小较大的集合中，以此来实现集合的合并。的方法来合并两个点集，可以证明每个点最多只会被处理logn次，这样维护LCA信息的总时间复杂度为O(nlog2n)。而为了维护DFS序列的信息，我们需要一个能够较快地处理插入一段序列，求某一段子序列的和，以及修改序列中某一个元素的值的数据结构。Treap、Square List和Splay Tree都能比较好地胜任上面的操作，其中用Treap维护的时间复杂度为O(nlog2n+qlogn)，用Square List维护的时间复杂度为，用Splay Tree维护的时间复杂度为O(nlogn+qlogn)。考虑到时间复杂度与编程复杂度