划分树

首先，Orz一下AHdoc神犇，本沙茶是看他的总结才搞懂划分树的。
原文地址

划分树，就是每个结点代表一个序列，设这个序列的长度为len，若len>1，则序列中前len/2（上取整，这里数学公式不好打，真囧）个元素被分到左子结点，左子结点代表的序列就是这些元素按照根结点中的顺序组成的序列，而剩下的元素被分到右子结点，右子结点代表的序列也就是剩下的元素按照根结点中的顺序组成的序列；若len=1，则该结点为叶结点。划分树最重要的应用就是找区间第K小（只是查找，不包括修改）。

写划分树时主要有两个函数：建树和找区间第K小。由于后者AHdoc神犇已经总结了，所以这里只总结建树的函数。

设目前结点为[l..r]（l<r，就是目前的结点是原序列不断划分后得到[l..r]这一段，其实也就是a0[l..r]打乱顺序后得到的，a0为原序列递增排序后的序列）首先找到中值，就是a0[mid]，mid=l+r>>1。然后可以得到，[l..r]中小于中值的的元素一定被划分到左子结点，[l..r]中大于中值的元素一定被划分到右子结点，而[l..r]中等于中值的元素则不确定，有的被划分到左子结点，有的被划分到右子结点，这就需要先找到应被划分到左子结点的等于中值的元素个数sm（从mid开始不断往左，直到找到边界处或者找到一个小于中值的元素为止，或者说，sm就是a0[l..mid]中等于中值的元素个数），然后开始划分，小于中值分到左子结点，大于中值分到右子结点，等于中值的，若目前还没满sm则分到左子结点否则分到右子结点。另外中间有两个值需要记录（找区间第K小时必须要用到）：sl和sr。sl[i]表示[l..i]中被分到左子结点的元素个数，sr[i]表示[l..i]中被分到右子结点的元素个数（这里l<=i<=r。显然sl[i]+sr[i]=i-l+1，其实sr[i]可以不用记录的，这里只是为了在找第K小操作中减少计算次数，起到空间换时间的作用）。
建树代码：
int mkt(int l, int r, int d)
{
    T[++No].l = l; T[No].r = r; int mid = l + r >> 1; T[No].mid = mid;
    if (l == r) return No;
    int midv = a0[mid], sm = mid - l + 1; rre2(i, mid, l) if (a0[i] < midv) {sm = mid - i; break;}
    int x = l, y = mid + 1;
    if (a[d][l] < midv) {
        a[d + 1][x++] = a[d][l]; sl[d][l] = 1; sr[d][l] = 0;
    } else if (a[d][l] == midv && sm) {
        a[d + 1][x++] = a[d][l]; sl[d][l] = 1; sr[d][l] = 0; sm--;
    } else {
        a[d + 1][y++] = a[d][l]; sl[d][l] = 0; sr[d][l] = 1;
    }
    re3(i, l+1, r) {
        if (a[d][i] < midv) {
            a[d + 1][x++] = a[d][i]; sl[d][i] = sl[d][i - 1] + 1; sr[d][i] = sr[d][i - 1];
        } else if (a[d][i] == midv && sm) {
            a[d + 1][x++] = a[d][i]; sl[d][i] = sl[d][i - 1] + 1; sr[d][i] = sr[d][i - 1]; sm--;
        } else {
            a[d + 1][y++] = a[d][i]; sl[d][i] = sl[d][i - 1]; sr[d][i] = sr[d][i - 1] + 1;
        }
    }
    int No0 = No; T[No0].lch = mkt(l, mid, d + 1); T[No0].rch = mkt(mid + 1, r, d + 1); return No0;
}
这里a是每层划分后的序列。
查找区间第K小的代码：
int Find_Kth(int l, int r, int K)
{
    int i = root, d = 0, l0, r0, mid0, s0, s1;
    while (1) {
        l0 = T[i].l, r0 = T[i].r; mid0 = T[i].mid;
        if (l0 == r0) return a[d][l];
        if (l == l0) s0 = l; else s0 = l0 + sl[d][l - 1]; s1 = l0 + sl[d][r] - 1;
        if (K <= s1 - s0 + 1) {
            i = T[i].lch; l = s0; r = s1; d++;
        } else {
            K -= (s1 - s0 + 1); if (l == l0) l = mid0 + 1; else l = mid0 + sr[d][l - 1] + 1;
            r = mid0 + sr[d][r]; i = T[i].rch; d++;
        }
    }
}

【具体题目】PKU2104、PKU2761（两道任选一道）

posted @ 2011-06-27 20:54 Mato_No1 阅读(2820) | 评论 (1) | 编辑 收藏

Splay Tree处理区间问题的几道好题及总结

（1）Robotic Sort（HDU1890、ZJU2985）
本题主要考察的是对此类问题，序列中给定值的索引问题。
当Splay Tree用来处理一个序列的时候，其关键字就是序列中元素的下标，而不是元素的值。这样，如果要查找序列中给定的值的位置（假设序列中任意两个元素的值不相等）看起来就无法实现。其实也是有办法实现的：因为元素在树中的下标是永远不变的！也就是，设这个序列为A，如果A[i]在插入Splay Tree时的下标为j，那么在A[i]被删除之前，其下标一直是j，永远不会变（注意元素在序列中的下标和在树中的下标是不同的）。利用这一性质可以解决给定值的索引问题。
对于本题，每次将从序列中第i小的元素到序列中第i个元素（这里假定元素下标是从1开始的，而不是从0开始）之间的所有元素反转，并输出第i小的元素在反转之前的在序列中的下标。设B[i]为第i小的数的初始位置，S[i]为初始位置在第i位的元素的下标，B[i]和S[i]都可以通过预处理得到。然后，每次交换前，求出S[B[i]]在树中的排名（基本操作），再减1（因为有边界结点）就是该元素目前的位置，而序列中第i个元素就是树中第(i+1)小的元素，再执行交换即可。
不过需要千万注意的是本题的标记问题，在求S[B[i]]在树中的排名时，有可能其祖先结点上有标记，需要先遍历其所有的祖先结点，再逆向下放标记（标记只能自顶向下传）。另外在交换的时候需要求出S[B[i]]的后继，在求后继的过程中需要查找，此时千万别忘了下放标记（总的说，凡是有查找的地方，就有dm）
代码（本沙茶太弱了，是抄别人的，因此其算法和上面总结的可能有差别，神犇不要鄙视）

（2）SuperMemo（PKU3580）
本题的6个操作中，add、reverse、insert、delete、min都不难搞，而revolve操作需要涉及到区间交换。
可以发现，所谓的旋转其实就是交换两个相邻区间，这对于功能极强的Splay Tree来说根本不难搞。
设这两个相邻区间为[x, y]与[y+1, z]，假设它们均非空（也就是x<=y<z，因为若其中至少有一个区间是空区间，则交换没有意义），先找到树中x的前趋P与z的后继S（这里x、z等指的都是对应的结点，下同），将P伸展到根、将S伸展到根的右子结点处，则S的左子树就表示区间[x, z]。然后，设S的左子树的根结点（也就是S的左子结点）为N，在这棵子树中找到第1小的结点P0与第(y-x+2)小的结点S0（这需要涉及到找子树内第K小的操作，只要把找整棵树第K小的操作的root改为N即可），它们分别表示x与(y+1)，这样将P0伸展到N处，将S0伸展到N的右子结点处，显然P0无左子树，S0的左子树T1表示区间[x+1, y]，S0的右子树T2表示区间[y+2, z]。然后，先将S0从P0的右子结点移动到P0的左子结点，再将T1作为P0的右子树（注意移动是两步：插入和删除）。这样整棵子树的中序遍历结果变成了S0->T2->P0->T1，也就是[y+1, z]∪[x, y]。
另外本题的标记有点难搞，只需注意rev是逆向标记，以及查找与dm共存就行了。
代码
（3）Play with Chain(HDU3487)
这个米有神马好说的，里面的操作在SuperMemo里都有；
代码
（4）AHOI2006 文本编辑器(editor)
这题在这一类题里面算水的。对于光标，只要用一个值来维护就行了。
另外注意本题极为猥琐的2点（题目中米有说明）：一是最初的文本并不是空的，而是有一个空格；二是执行GET操作时光标可能位于文本末尾，此时应输出空格；
代码
（5）HFTSC2011 高精度计算器(apc)，题目见这个帖子；
这题反映出了一个很囧的问题：有些信息会被rev整体破坏。
本题中的操作都是常见操作，但是本题所需要维护的信息却不是那么容易维护。本题要求维护一棵子树中所有结点所表示的元素序列（中序遍历结果）模一个指定的M的值。设F[i]为R^i mod M的值（这里R是进制，也就是题目中的K），则有：
T[x].mod = (T[T[x].c[0]].mod * F[T[T[x].c[1]].sz + 1] + T[x].v * F[T[T[x].c[1]].sz] + T[T[x].c[1]].mod) % M;
这个式子其实是很好理解的。
关键是，本题的猥琐之处并不在此。注意本题的rev操作，它会整体改变树中所有结点所记录的mod值，这时，如果再用上面这个式子来维护T[x].mod，就会出错，因为此时引用到的T[T[x].c[0]].mod和T[T[x].c[1]].mod都是过时的。解决这一问题只有一种方法：记录“逆mod”(rmod)，意思是将整个元素序列反转后的mod，即：
T[x].rmod = (T[T[x].c[1]].rmod * F[T[T[x].c[0]].sz + 1] + T[x].v * F[T[T[x].c[0]].sz] + T[T[x].c[0]].rmod) % M;
这样，在反转某序列的时候，直接将根结点的mod值和rmod值交换就行了。
像mod这样会被反转操作整体破坏的信息还有很多，比如NOI2005 sequence里面的lmax和rmax。如果真的遇到这类信息，只有采用上面的方法。
另外，本题第6、9、10个点有误。
代码

现在Splay Tree差不多弄完了，接下来还有N多知名的、不知名的高级数据结构……时间MS有些不够用了囧……

posted @ 2011-06-25 11:21 Mato_No1 阅读(4959) | 评论 (2) | 编辑 收藏

平衡树调试技巧

平衡树操作，尤其是Splay Tree的区间操作（当线段树用的那种），代码长且极易搞疵，当操作多的时候，甚至可能调试的时间比写代码的时间都长！
这里来总结一下平衡树在实际应用（编程）中的易疵点和调试技巧。
【平衡树（这里主要指Splay Tree）的操作】
这个MS前面已经总结过了，主要分以下几类：
（1）基本操作：查找、单结点插入、单结点删除、找第K小、求结点的排名、找指定结点的前趋和后继；
（2）进阶操作：找给定的值在树中的前趋和后继、对一个序列建平衡树、插入整棵子树、删除整棵子树；
（3）区间操作（与线段树的结合）：标记（自顶向下）；
（4）区间操作（与线段树的结合）：最大值、总和等自底向上维护的信息；
（5）一些特别猥琐的操作（比如PKU3580的revolve）；
【主要函数及其易疵点】
（1）void sc(int _p, int _c, bool _d);
将_p的_d子结点（0左1右）置为_c，这个就三句话，应该不会搞疵；
（2）void upd(int x);
更新x记录的一些信息（自底向上维护的信息，包括大小域sz），这个，有几个信息就写几句话就行了，不易搞疵；
（3）void rot(int x);
旋转操作，将x旋转到其父结点的位置。这个函数中有两个易疵点：一是若x的父结点为根，则需要在旋转后将根置为x，且将x的父结点置为0（特别注意这个）；二是若x的父结点不为根，则需要将x的父结点的父结点的对应子结点（原来是x的父结点的那个）置为x；另外旋转完成后别忘了更新；
（4）void splay(int x, int r);
伸展操作，将x伸展到r的子结点处，这个操作是最核心的操作，只要记住了过程，且rot不搞疵，这个也就不会搞疵；
（5）void dm(int x);
对于有标记的结点的下放标记操作，极易疵！
首先，对于任何结点，标记一打上就必须立即生效，因此除了将x的标记取消、x的两个子结点（如果存在的话）打上标记外，还要更新两个子结点的一些域（当然这里更新千万不能用upd更新）；
其次，要搞清楚x的每一个标记的类型，是叠加型标记（如整体加上某一个数的标记）、覆盖型标记（如整体置为某一个数的标记）还是逆向标记（如是否翻转过的标记，因为翻转两次等于没转），然后在下放标记的时候注意写法（因为x的子结点原来可能也有标记，此时只有覆盖型标记需要将x的子结点的原来的标记覆盖掉，对于叠加型标记，应为加法运算，对于逆向标记，应为取反操作，还有其它类型的标记分别处理）；
最后还有一点，就是x的左子结点或右子结点可能不存在（0），此时就不能对这里的0号结点下放标记。
（6）int Find_Kth(int x, int K);
在以结点x为根的子树中找第K小的结点，返回结点编号；若省略x，默认x=root（即在整棵树中找）；
这个一般不会搞疵，注意两个地方即可：一是有mul域的时候需要考虑mul域，二是结点如果有标记，需要在找的时候下放标记。（凡是查找操作，包括插入新结点时的查找，在查找过程中必须不断下放标记，因为查找之后很可能就要伸展）；
（7）void ins(int _v);
       void ins(int x, int _v)
插入一个值为_v的结点。前者是普通插入，后者是用Splay Tree处理序列（当线段树用）时的插入，表示在第x小的结点后插入；
前者注意有三种情况：树为空；树非空且值为_v的结点不存在；树非空且值为_v的结点已存在；
后者需要注意，在将第x小的结点伸展到根，将第(x+1)小的结点伸展到根的右子结点，再插入后，需要upd上述两个结点（注意upd顺序）；
（8）void del(int x);
将结点x删除。这个一般不会搞疵，唯一要注意的一点是删除后的upd；
（9）打标记操作（add、reverse、makesame等）：
其实打标记操作的代码量是很少的，关键就是对于不同标记要分别处理，同（5）；
（10）各种询问操作：
这个直接调出相应的域即可，几乎不可能搞疵；
（11）极其猥琐的操作（revolve等）：
这个属于最易疵的操作（否则就体现不出其猥琐了）：
首先要搞清楚这个操作的具体过程，不要连具体过程都搞疵了，这样写出来的代码肯定是疵的；
然后，注意一些非常猥琐的细节问题（很多时候，本沙茶都是栽在细节上的）；
另外，这些操作中一般都会出现多次伸展，别忘了伸展后的upd；
（12）其它易疵点：
[1]“移动”是由“插入”和“删除”两部分组成的，因此凡是涉及到“移动”类的操作（如将某棵子树或某个结点移动到另一个位置等），必须要同时出现“插入”和“删除”，而不能只插入不删除；
[2]注意检查主函数main()中是否有搞疵的地方；

易疵点也就这么多了，下面是调试技巧：
【Splay Tree调试技巧】
（1）先用样例调试，保证样例能够通过（注意，样例中必须包含所有题目中给出的操作，如果不是这样，那在调试完样例后还要加一组包含所有题目中给出的操作的小数据）；
（2）然后用mkdt造大数据，一般平衡树操作题的合法数据都不难造，只要注意别越界就行了；
（3）在调试过程中应不断少量增大数据规模，因为在能找出问题的情况下，数据规模越小越好；
（4）如果调试过程中发现死循环或者RE：
[1]首先输出每个操作，找出是在哪个操作处出了问题；
[2]进入该操作内部检查，也就是把该操作的代码读一遍，一般都能找出问题；
[3]如果找不出问题，可以进入该操作内部跟踪检查；
[4]如果跟踪检查仍然没找出问题，那可能是该操作是对的，而其它操作出了问题，此时可以弄一个vst，把整棵树遍历一下，找出真正出问题的操作，转[2]；
（5）排除了死循环或RE后，接下来就是检查输出结果是否正确了：
[1]对于小规模数据可人工计算检查，对于较大规模数据则必须采用对照方法，即弄一个模拟法的代码，保证该代码正确，然后进行对照；
[2]如果发现加入遍历时，结果正确，但去掉遍历后结果不正确，则表明是处理结点标记的时候出了问题（因为在遍历过程中需要下放标记），进入dm或加标记操作中检查即可；
[3]其它情况下，可以在遍历中输出整个序列（或整棵树），进行对照，找出问题所在；
[4]如果数据过大，操作过多，人工分析时间较长，就只能采用读代码的方式检查了；
（6）最后，用mkdt造一个最大规模的数据，检查是否TLE、是否越界（数组是否开小）；
如果以上各点全部通过，就可以宣布AC了。

posted @ 2011-06-23 00:07 Mato_No1 阅读(609) | 评论 (2) | 编辑 收藏

【NOI2005 维护数列(sequence)】Splay Tree处理序列问题

【原题见这里】
本题是Splay Tree处理序列问题（也就是当线段树用）的一个典型例题。

Splay Tree之所以可以当线段树用，是因为它可以支持一个序列，然后用“左端前趋伸展到根，右端后继伸展到根的右子结点，取根的右子结点的左子结点”这种伸展方法，对一个序列中的一整段进行整体操作。由于要防止出现前趋或后继不存在的情况，需要在这个序列的两端加入两个边界结点，要求其值不能影响到结点各种记载信息的维护（多取0、∞或-∞）。这两个边界结点在树中永远存在，不会被删除。

（1）结点的引用：
在当线段树用的Splay Tree中，真正的关键字是下标而不是值，因此，“序列中第i个结点”实际上对应的是“树中第(i+1)小的结点”（因为左边还有一个边界结点），这就说明在对结点引用时需要找第K小的操作。因此，下面的“结点x”指的是“树中第(x+1)小的结点”。
（2）标记：
在线段树中，如果对一个结点所表示的线段整体进行了某种操作，需要在这个结点上打上一个标记，在下一次再找到这个结点时，其标记就会下放到其两个子结点上。在Splay Tree中也可以引入标记。比如要对[2, 6]这一段进行整体操作，就将结点1伸展到根的位置，将结点7伸展到根的右子树的位置，然后结点7的左子树就表示[2, 6]这一段，对这棵子树的根结点打上标记并立即生效（必须是立即生效，而不是等下一次引用再生效），也就是立即改变该结点记录的一些信息的值。如果下次再次引用到这个结点，就要将其标记下放到其两个子结点处；
需要注意的一点是，如果要伸展某个结点x到r的子结点的位置，就必须保证从x原来的位置到r的这个子结点（x伸展后的位置）上的所有结点上均没有标记，否则就会导致标记混乱。因此，必须首先找到这个结点x，在此过程中不断下放标记。
（3）自底向上维护的信息：
标记可以看成一种自顶向下维护的信息。除了标记以外，作为“线段树”，往往还要维护一些自底向上维护的信息。比如在sequence这题中，就有lmax（左段连续最大和）、rmax（右段连续最大和）、midmax（全段连续最大和）以及sum（全段总和）等信息要维护。对于这类东东其实也很好办，因为子树大小（sz域）就是一种自底向上维护的信息，因此对于这些信息只要按照维护sz域的办法维护即可（统一写在upd函数里）。唯一的不同点是打标记时它们的值可能要改变。
（4）对连续插入的结点建树：
本题的插入不是一个一个插入，而是一下子插入一整段，因此需要先将它们建成一棵树。一般建树操作都是递归的，这里也一样。设目前要对A[l..r]建树（A为待插入序列），若l>r则退出，否则找到位于中间的元素mid = l + r >> 1，将A[mid]作根，再对A[l..mid-1]建左子树，对A[mid+1..r]建右子树即可。这样可以保证一开始建的就是一棵平衡树，减小常数因子。
（5）回收空间：
根据本题的数据范围提示，插入的结点总数最多可能达到4000000，但在任何时刻树中最多只有500002个结点（包括两个边界），此时为了节省空间，可以采用循环队列回收空间的方法。即：一开始将所有的可用空间（可用下标，本题为1~500002）存在循环队列Q里，同时设立头尾指针front和rear，每次如果有新结点插入，就取出Q[front]并作为新结点的下标，如果有结点要删除（本题是一次删除整棵子树，因此在删除后需要分别回收它们的空间），则从rear开始，将每个删除的结点的下标放回到Q里。当然，这种方法是要牺牲一定的时间的，因此在空间不是特别吃紧的情况下不要用。

【2012年1月16日更新】
今天重写sequence的时候，秃然发现加入的边界点可能会对lmax、rmax、midmax等的维护造成影响：当序列中所有的值都是负数时，若边界点的值设为0，将使这3个值也为0，所以，边界点的值应设为-INF（不会影响到sum，因为可以单独调出[l, r]的sum，避开边界）。这就说明并非所有这样的题中都可以设置边界点（比如HFTSC2011的那题就不行），如果边界点会对维护的信息造成影响，就不能设置边界点，在各个操作中，分4种情况判断。（代码已经修改）

下面上代码了：
#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
const int MAXN = 500002, NOSM = -2000, INF = ~0U >> 2;
struct node {
    int v, c[2], p, sz, sum, lmax, rmax, midmax, sm;
    bool rev, d;
} T[MAXN + 1];
int root, Q[MAXN + 1], front, rear, a[MAXN], len, res;
int max(int SS0, int SS1)
{
    return SS0 >= SS1 ? SS0 : SS1;
}
int max(int SS0, int SS1, int SS2)
{
    int M0 = SS0 >= SS1 ? SS0 : SS1; return M0 >= SS2 ? M0 : SS2;
}
void newnode(int n, int _v)
{
    T[n].v = T[n].sum = T[n].lmax = T[n].rmax = T[n].midmax = _v; T[n].c[0] = T[n].c[1] = 0; T[n].sz = 1; T[n].sm = NOSM; T[n].rev = 0;
}
void sc(int _p, int _c, bool _d)
{
    T[_p].c[_d] = _c; T[_c].p = _p; T[_c].d = _d;
}
void sm_opr(int x, int SM)
{
    T[x].sum = T[x].sz * SM;
    if (SM > 0) T[x].lmax = T[x].rmax = T[x].midmax = T[x].sum; else T[x].lmax = T[x].rmax = T[x].midmax = SM;
}
void rev_opr(int x)
{
    int c0 = T[x].c[0], c1 = T[x].c[1]; sc(x, c0, 1); sc(x, c1, 0);
    int tmp = T[x].lmax; T[x].lmax = T[x].rmax; T[x].rmax = tmp;
}
void dm(int x)
{
    int SM0 = T[x].sm;
    if (SM0 != NOSM) {
        T[x].v = T[T[x].c[0]].sm = T[T[x].c[1]].sm = SM0; T[x].sm = NOSM;
        sm_opr(T[x].c[0], SM0); sm_opr(T[x].c[1], SM0);
    }
    if (T[x].rev) {
        T[T[x].c[0]].rev = !T[T[x].c[0]].rev; T[T[x].c[1]].rev = !T[T[x].c[1]].rev; T[x].rev = 0;
        rev_opr(T[x].c[0]); rev_opr(T[x].c[1]);
    }
}
void upd(int x)
{
    int c0 = T[x].c[0], c1 = T[x].c[1];
    T[x].sz = T[c0].sz + T[c1].sz + 1;
    T[x].sum = T[c0].sum + T[c1].sum + T[x].v;
    T[x].lmax = max(T[c0].lmax, T[c0].sum + T[x].v + max(T[c1].lmax, 0));
    T[x].rmax = max(T[c1].rmax, max(T[c0].rmax, 0) + T[x].v + T[c1].sum);
    T[x].midmax = max(T[c0].midmax, T[c1].midmax, max(T[c0].rmax, 0) + T[x].v + max(T[c1].lmax, 0));
}
void rot(int x)
{
    int y = T[x].p; bool d = T[x].d;
    if (y == root) {root = x; T[root].p = 0;} else sc(T[y].p, x, T[y].d);
    sc(y, T[x].c[!d], d); sc(x, y, !d); upd(y);
}
void splay(int x, int r)
{
    int p; while ((p = T[x].p) != r) if (T[p].p == r) rot(x); else if (T[x].d == T[p].d) {rot(p); rot(x);} else {rot(x); rot(x);} upd(x);
}
int Find_Kth(int K)
{
    int i = root, S0;
    while (i) {
        dm(i); S0 = T[T[i].c[0]].sz + 1;
        if (K == S0) break; else if (K < S0) i = T[i].c[0]; else {K -= S0; i = T[i].c[1];}
    }
    return i;
}
int mkt(int l, int r)
{
    if (l > r) return 0;
    int n0 = Q[front], mid = l + r >> 1; if (front == MAXN) front = 1; else front++;
    newnode(n0, a[mid]); int l_r = mkt(l, mid - 1), r_r = mkt(mid + 1, r);
    sc(n0, l_r, 0); sc(n0, r_r, 1); upd(n0); return n0;
}
void ins(int pos)
{
    int P0 = Find_Kth(pos); splay(P0, 0); int P1 = Find_Kth(pos + 1); splay(P1, root); sc(P1, mkt(0, len - 1), 0); upd(P1); upd(P0);
}
void era(int x)
{
    if (!x) return;
    if (rear == MAXN) rear = 1; else rear++; Q[rear] = x;
    era(T[x].c[0]); era(T[x].c[1]);
}
void del(int l, int r)
{
    int P0 = Find_Kth(l - 1); splay(P0, 0); int P1 = Find_Kth(r + 1); splay(P1, root); 
    int root0 = T[P1].c[0]; sc(P1, 0, 0); upd(P1); upd(P0); era(root0);
}
void mksame(int l, int r, int x)
{
    int P0 = Find_Kth(l - 1); splay(P0, 0); int P1 = Find_Kth(r + 1); splay(P1, root); 
    int n = T[P1].c[0]; T[n].sm = x; sm_opr(n, x); upd(P1); upd(P0);
}
void reve(int l, int r)
{
    int P0 = Find_Kth(l - 1); splay(P0, 0); int P1 = Find_Kth(r + 1); splay(P1, root); 
    int n = T[P1].c[0]; T[n].rev = !T[n].rev; rev_opr(n); upd(P1); upd(P0);
}
int get_sum(int l, int r)
{
    int P0 = Find_Kth(l - 1); splay(P0, 0); int P1 = Find_Kth(r + 1); splay(P1, root); 
    int n = T[P1].c[0]; return T[n].sum;
}
int max_sum()
{
    return T[root].midmax;
}
void prepare()
{
    T[0].sz = T[0].sum = T[0].lmax = T[0].rmax = T[0].midmax = 0;
    front = 3; rear = MAXN; re1(i, MAXN) Q[i] = i;
    newnode(1, -INF); newnode(2, -INF); sc(1, 2, 1); root = 1; T[root].p = 0;
}
int main()
{
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    prepare();
    int m, l, r, x;
    scanf("%d%d", &len, &m); char ch = getchar(), str[1000];
    re(i, len) scanf("%d", &a[i]); ins(1);
    re(i, m) {
        scanf("%s", str);
        if (!strcmp(str, "INSERT")) {scanf("%d%d", &l, &len); re(i, len) scanf("%d", &a[i]); ins(++l);}
        if (!strcmp(str, "DELETE")) {scanf("%d%d", &l, &r); r += l++; del(l, r);}
        if (!strcmp(str, "MAKE-SAME")) {scanf("%d%d%d", &l, &r, &x); r += l++; mksame(l, r, x);}
        if (!strcmp(str, "REVERSE")) {scanf("%d%d", &l, &r); r += l++; reve(l, r);}
        if (!strcmp(str, "GET-SUM")) {scanf("%d%d", &l, &r); r += l++; printf("%d\n", get_sum(l, r));}
        if (!strcmp(str, "MAX-SUM")) printf("%d\n", max_sum());
        ch = getchar();
    }
    fclose(stdin); fclose(stdout);
    return 0;
}

最后把我的这个代码与BYVoid神犇的本题代码进行测试比较，结果（BYVoid神犇的代码见这里）：

BYVoid神犇的：


本沙茶的：


【相关论文】
运用伸展树解决数列维护问题 by JZP
【感谢】
JZP神犇（提供论文）
BYVoid神犇（提供标程）

posted @ 2011-06-21 16:06 Mato_No1 阅读(2059) | 评论 (0) | 编辑 收藏

Splay Tree 重复次数mul以及一些进阶操作

额……最近两天光顾着刷题忘了总结了……正好现在把总结的东东全部补上吧囧……

【重复次数mul】
在前面第一篇总结Splay Tree的时候就提到了结点的重复次数(mul)域，这个东东至今在网上还米看见有犇用（在本沙茶见过的范围内），但是不可否认的是这个域在某些情况下几乎是“必须使用”的。
所谓重复次数，就是将树中所有值(v)相同的结点全部合并成一个，这些结点的总个数就是合并后的结点的mul值。比如，在一棵空树中插入3个值为5的结点后，在使用mul域的情况下，树中只有一个结点，其v值为5，mul值为3。
在平衡树中，值相同的结点确实非常碍事。按照二叉查找树的定义：“要么是一棵空树，要么是一棵满足以下条件的非空树：根结点左子树中所有结点的值均小于根结点，根结点右子树中所有结点的值均大于根结点，且根的左右子树均为二叉查找树”，在二叉查找树中，是不应该出现值相同的结点的。可是在实际问题中，出现值相同的结点几乎是不可避免的。此时，树的定义就会变得非常模糊，也就是要把二叉查找树定义中的“小于”全部改为“小于等于”，“大于”全部改为“大于等于”。这样定义的树在一般情况下也米有神马问题，但是在找前趋(Pred)和找后继(Succ)操作中，问题就来了。因为根结点的前趋和后继的值可能与根结点相等（比如 HNOI2004 宠物收养所 那一题），这时，根结点的前趋既有可能在左子树里，也有可能在右子树里，根结点的后继也一样。此时，这两个操作就无法进行了。
【mul域的维护】
mul域其实可以看成结点的一个本身属性，和v一样。因此在旋转、伸展操作中任何结点的mul值都是不会改变的。可能改变结点mul值的地方只有两处：一是插入，二是删除。在插入一个值为_v的结点的时候，如果发现值为_v的结点在树中已经存在，则只会将这个结点的mul值加1，而不是真正插入一个新的结点。同样的，在删除一个结点的时候，如果这个结点的mul值大于1，则只会将这个结点的mul值减1，而不是真正删除。
【mul域的作用】
mul域最主要的作用就是解决值相同的结点对于某些操作的影响。另外，mul域的引入可以减少树中结点的总个数（尤其是当插入的结点数很多而结点的值的范围不大的时候），从而降低时间复杂度（准确来说可以降低常数）。
【Splay Tree的进阶操作】
<1>找非根结点的前趋和后继。
Splay Tree由于有伸展操作，可以将要求前趋或后继的点伸展到根再求前趋或后继。如果要不通过伸展操作找一个非根结点的前趋或后继怎么办？
设这个结点为x。如果x有左子结点，则x的前趋就是x的左子结点的右链上的最后一个结点；如果x没有左子结点，则x的前趋就是从x开始往上（往x的祖先）查找，直到找到第一个是其父结点的右子结点的结点为止，则这个结点的父结点就是x的前趋（或者说，就是不断沿着x的父结点往上找，一开始都是往右的，找到第一个往左的就行了）。后继则正好相反。证明可以用中序遍历。
<2>找某个值v0的前趋和后继（值为v0的结点在树中不一定存在）。
所谓v0的前趋和后继，就是指在树中值小于（也有的是不大于）v0的最大的结点的值，和树中值大于（也有的是不小于）v0的最小的结点的值。在有了操作（1）【不通过伸展操作找非根结点的前趋和后继】以后，这个操作变得极为容易：先进行普通的查找操作（查找值为v0的结点），如果能找到，则剩下的步骤就和操作（1）一样了；如果找不到，则必然是找到某个空结点（0）处，假设在这里插入一个值为v0的结点（只是假设，不是真插入），则该结点显然是没有左子结点的，因此就是“从该结点开始往上查找，直到找到第一个是其父结点的右子结点的结点为止，则这个结点的父结点就是该结点的前趋”，也就是v0的前趋；后继类似。
在查找过程中可以进行一个常数优化：设点i为查找过程中“右转”的最后一个结点（即找到该结点后，接下来是该结点的右子结点），每次往右子结点转的时候就更新i，则最后结点i就是值v0的前趋；后继类似。
<3>删除所有值在某区间内的结点（这个区间可以是开区间、闭区间或半开半闭区间）。
以开区间为例：删除树中所有值在(l, r)范围内的结点。先找到l的前趋P和r的后继S（注意这里的前趋和后继是包括“等于”的），然后将P伸展到根，S伸展到P的右子结点处，则S的左子树中就是所有值在(l, r)范围内的结点，直接删掉这棵子树即可（注意删除后要更新S和P）；若改为闭区间，则将前趋和后继中的“等于”去掉（即必须是小于或大于）；半开半闭区间则一半按开区间处理，一半按闭区间处理。问题是，如果点P或点S不存在怎么办。有两种解决办法，一是若P和S之一存在，则将其伸展到根，然后直接删掉其左子树或右子树即可；若P和S都不存在，则树为空，直接将root置为0即可；二是按照sequence的办法，加入两个边界结点，当前趋或后继不存在时就认为是边界结点。
其实不光是删除，在找到了这棵子树后可以对它进行一些整体操作，从而让Splay Tree具有线段树的功能（这个在下面的NOI2005 sequence那一题里面会总结）。
<4>插入一棵树（当然这棵树也是Splay Tree，并且原树中的结点值序列与新树中的结点值序列不相交）。
有时候，题目中会连续出现很多插入操作，中间没有其它操作，此时，与其一个一个插入，还不如将它们先建成一棵树（建树的方法在下一篇里总结），再整体插入。整体插入的方法：设L和R分别是新树里值最小的结点和值最大的结点，在原树中找到L的前趋P和R的后继S，将P伸展到根，S伸展到P的右子结点处，由于原树中的结点值序列与新树中的结点值序列不相交（也就是原树中的结点值要么小于L的值，要么大于R的值），因此S无左子结点，此时将新树作为S的左子树即可。

posted @ 2011-06-21 11:31 Mato_No1 阅读(645) | 评论 (0) | 编辑 收藏

终于摘掉了不会平衡树的帽子

     摘要: 今天真是有纪念意义啊……以前试着捉了N遍的cashier今天竟然AC了，本沙茶终于掌握了平衡树！！！【Splay Tree及其实现】<1>结点记录的信息：一般情况下Splay Tree是用线性存储器（结构数组）来存储的，可以避免在Linux下的指针异常问题。这样对于某个结点，至少要记录以下的域：值（又叫关键字）、左子结点的下标、右子结点的下标、父结点下标、子树大...  阅读全文

posted @ 2011-06-18 21:21 Mato_No1 阅读(1044) | 评论 (0) | 编辑 收藏

次小生成树

给出一个带边权的无向图G，设其最小生成树为T，求出图G的与T不完全相同的边权和最小的生成树（即G的次小生成树）。一个无向图的两棵生成树不完全相同，当且仅当这两棵树中至少有一条边不同。注意，图G可能不连通，可能有平行边，但一定没有自环（其实对于自环也很好处理：直接舍弃。因为生成树中不可能出现自环）。
【具体题目】URAL1416（注意，这一题的边数M的范围没有给出，视为124750）
【分析】
定义生成树T的一个可行变换(-E1, +E2)：将T中的边E1删除后，再加入边E2（满足边E2原来不在T中但在G中），若得到的仍然是图G的一棵生成树，则该变换为可行变换，该可行变换的代价为(E2权值 - E1权值)。这样，很容易证明，G的次小生成树就是由G的最小生成树经过一个代价最小的可行变换得到。进一步可以发现，这个代价最小的可行变换中加入的边E2的两端点如果为V1和V2，那么E1一定是原来最小生成树中从V1到V2的路径上的权值最大的边。

这样，对于本题就有两种算法了：（以下的T全部指G的最小生成树）
（1）Prim：
设立数组F，F[x][y]表示T中从x到y路径上的最大边的权值。F数组可以在用Prim算法求最小生成树的过程中得出。每次将边(i, j)加入后（j是新加入树的边，i=c[j]），枚举树中原有的每个点k（包括i，但不包括j），则F[k][j]=max{F[k][i], (i, j)边权值}，又由于F数组是对称的，可以得到F[j][k]=F[k][j]。然后千万记住将图G中的边(i, j)删除（就是将邻接矩阵中(i, j)边权值改为∞）！因为T中的边是不能被加入的。等T被求出后，所有的F值也求出了，然后，枚举点i、j，若邻接矩阵中边(i, j)权值不是无穷大（这说明i、j间存在不在T中的边），则求出{(i, j)边权值 - F[i][j]}的值，即为加入边(i, j)的代价，求最小的总代价即可。
另外注意三种特殊情况：【1】图G不连通，此时最小生成树和次小生成树均不存在。判定方法：在扩展T的过程中找不到新的可以加入的边；【2】图G本身就是一棵树，此时最小生成树存在（就是G本身）但次小生成树不存在。判定方法：在成功求出T后，发现邻接矩阵中的值全部是无穷大；【3】图G存在平行边。这种情况最麻烦，因为这时代价最小的可行变换(-E1, +E2)中，E1和E2可能是平行边！因此，只有建立两个邻接矩阵，分别存储每两点间权值最小的边和权值次小的边的权值，然后，每当一条新边(i, j)加入时，不是将邻接矩阵中边(i, j)权值改为无穷大，而是改为连接点i、j的权值次小的边的权值。

代码：
#include <iostream>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
const int MAXN = 7000, INF = ~0U >> 2;
int n, s[MAXN][MAXN], s2[MAXN][MAXN], f[MAXN][MAXN], c[MAXN], v[MAXN], res1 = 0, res2 = 0;
bool vst[MAXN];
void init()
{
    freopen("mst.in", "r", stdin);
    scanf("%d", &n);
    re(i, n) re(j, n) s[i][j] = s2[i][j] = INF;
    int m, a, b, len;
    scanf("%d", &m);
    if (!m) {
        if (n > 1) res1 = -INF; res2 = -INF;
        return;
    }
    re(i, m) {
        scanf("%d%d%d", &a, &b, &len); a--; b--;
        if (len < s[a][b]) {s2[a][b] = s2[b][a] = s[a][b]; s[a][b] = s[b][a] = len;} else if (len < s2[a][b]) s2[a][b] = s2[b][a] = len;
    }
    fclose(stdin);
}
void solve()
{
    re(i, n) {f[i][i] = c[i] = vst[i] = 0; v[i] = s[0][i];} vst[0] = 1;
    int l0, l1 = INF, x, y, z;
    re2(i, 1, n) {
        l0 = INF; re(j, n) if (!vst[j] && v[j] < l0) {l0 = v[j]; x = j; y = c[j];}
        if (l0 == INF) {res1 = res2 = -INF; return;}
        vst[x] = 1; res1 += l0; s[x][y] = s[y][x] = INF; if (s2[x][y] < INF && s2[x][y] - l0 < l1) l1 = s2[x][y] - l0;
        re(j, n) if (!vst[j] && s[x][j] < v[j]) {v[j] = s[x][j]; c[j] = x;}
        re(j, n) if (vst[j] && j != x) f[j][x] = f[x][j] = max(f[j][y], l0);
    }
    re(i, n-1) re2(j, i+1, n) if (s[i][j] < INF) {
        z = s[i][j] - f[i][j];
        if (z < l1) l1 = z;
    }
    if (l1 == INF) res2 = -INF; else res2 = res1 + l1;
}
void pri()
{
    freopen("mst.out", "w", stdout);
    printf("Cost: %d\nCost: %d\n", res1 == -INF ? -1 : res1, res2 == -INF ? -1 : res2);
    fclose(stdout);
}
int main()
{
    init();
    if (!res2) solve();
    pri();
    return 0;
}
效率分析：Prim算法求次小生成树的时空复杂度均为O(N2)。

（2）Kruskal：
Kruskal算法也可以用来求次小生成树。在准备加入一条新边(a, b)（该边加入后不会出现环）时，选择原来a所在连通块（设为S1）与b所在连通块（设为S2）中，点的个数少的那个（如果随便选一个，最坏情况下可能每次都碰到点数多的那个，时间复杂度可能增至O(NM)），找到该连通块中的每个点i，并遍历所有与i相关联的边，若发现某条边的另一端点j在未选择的那个连通块中（也就是该边(i, j)跨越了S1和S2）时，就说明最终在T中"删除边(a, b)并加入该边"一定是一个可行变换，且由于加边是按照权值递增顺序的，(a, b)也一定是T中从i到j路径上权值最大的边，故这个可行变换可能成为代价最小的可行变换，计算其代价为[(i, j)边权值 - (a, b)边权值]，取最小代价即可。注意，在遍历时需要排除一条边，就是(a, b)本身（具体实现时由于用DL边表，可以将边(a, b)的编号代入）。另外还有一个难搞的地方：如何快速找出某连通块内的所有点？方法：由于使用并查集，连通块是用树的方式存储的，可以直接建一棵树（准确来说是一个森林），用“最左子结点+相邻结点”表示，则找出树根后遍历这棵树就行了，另外注意在合并连通块时也要同时合并树。
对于三种特殊情况：【1】图G不连通。判定方法：遍历完所有的边后，实际加入T的边数小于(N-1)；【2】图G本身就是一棵树。判定方法：找不到这样的边(i, j)；【3】图G存在平行边。这个对于Kruskal来说完全可以无视，因为Kruskal中两条边只要编号不同就视为不同的边。
其实Kruskal算法求次小生成树还有一个优化：每次找到边(i, j)后，一处理完这条边就把它从图中删掉，因为当S1和S2合并后，(i, j)就永远不可能再是可行变换中的E2了。

代码：
#include <iostream>
#include <stdlib.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
const int MAXN = 7000, MAXM = 130000, INF = ~0U >> 2;
struct edge {
    int a, b, len, pre, next;
} ed[MAXM + MAXM];
struct edge2 {
    int a, b, len, No;
} ed2[MAXM];
int n, m = 0, m2, u[MAXN], ch[MAXN], nx[MAXN], q[MAXN], res1 = 0, res2 = INF;
void init_d()
{
    re(i, n) ed[i].a = ed[i].pre = ed[i].next = i;
    if (n % 2) m = n + 1; else m = n;
}
void add_edge(int a, int b, int l)
{
    ed[m].a = a; ed[m].b = b; ed[m].len = l; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
    ed[m].a = b; ed[m].b = a; ed[m].len = l; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
}
void del_edge(int No)
{
    ed[ed[No].pre].next = ed[No].next; ed[ed[No].next].pre = ed[No].pre;
    ed[ed[No ^ 1].pre].next = ed[No ^ 1].next; ed[ed[No ^ 1].next].pre = ed[No ^ 1].pre;
}
void init()
{
    freopen("mst.in", "r", stdin);
    scanf("%d%d", &n, &m2);
    if (!m2) {
        if (n > 1) res1 = -INF;
        res2 = -INF; return;
    }
    init_d();
    int a, b, len;
    re(i, m2) {
        scanf("%d%d%d", &a, &b, &len);
        ed2[i].No = m; add_edge(--a, --b, len);
        ed2[i].a = a; ed2[i].b = b; ed2[i].len = len;
    }
    fclose(stdin);
}
int cmp(const void *s1, const void *s2)
{
    return ((edge2 *)s1)->len - ((edge2 *)s2)->len;
}
void prepare()
{
    re(i, n) u[i] = ch[i] = nx[i] = -1;
    qsort(ed2, m2, 16, cmp);
}
int find(int x)
{
    int r = x, r0 = x, tmp;
    while (u[r] >= 0) r = u[r];
    while (u[r0] >= 0) {tmp = u[r0]; u[r0] = r; r0 = tmp;}
    return r;
}
void uni(int r1, int r2, int No, int l0)
{
    q[0] = r1;
    int j, k, l1, front, rear;
    for (front=0, rear=0; front<=rear; front++) {
        j = ch[q[front]];
        while (j != -1) {
            q[++rear] = j;
            j = nx[j];
        }
    }
    re3(i, 0, rear) {
        j = q[i];
        for (int p=ed[j].next; p != j; p=ed[p].next) {
            k = ed[p].b;
            if (p != No && find(k) == r2) {
                l1 = ed[p].len - l0;
                if (l1 < res2) res2 = l1;
                del_edge(p);
            }
        }
    }
    u[r2] += u[r1]; u[r1] = r2; nx[r1] = ch[r2]; ch[r2] = r1;
}
void solve()
{
    int r1, r2, l0, num = 0;
    re(i, m2) {
        r1 = find(ed2[i].a); r2 = find(ed2[i].b);
        if (r1 != r2) {
            l0 = ed2[i].len; res1 += l0; num++;
            if (u[r1] >= u[r2]) uni(r1, r2, ed2[i].No, l0); else uni(r2, r1, ed2[i].No ^ 1, l0);
        }
    }
    if (num < n - 1) {res1 = res2 = -INF; return;}
    if (res2 == INF) res2 = -INF; else res2 += res1;
}
void pri()
{
    freopen("mst.out", "w", stdout);
    printf("Cost: %d\nCost: %d\n", res1 == -INF ? -1 : res1, res2 == -INF ? -1 : res2);
    fclose(stdout);
}
int main()
{
    init();
    if (!res1 && res2 == INF) {
        prepare();
        solve();
    }
    pri();
    return 0;
}
效率分析：可以证明，如果每次都选取点少的连通块，Kruskal算法求次小生成树的时间复杂度为O(M*(logN+logM))，空间复杂度为O(M)。
总结：显然Prim适用于稠密图，而Kruskal适用于稀疏图。

下面是对于一些数据的测试结果（数据说明：第1~9个点和第15个点为稠密图或一般图，第10~14个点为稀疏图）

Prim：


Kruskal（加入删边优化）：


Kruskal（未加删边优化）：

posted @ 2011-05-29 16:03 Mato_No1 阅读(6677) | 评论 (5) | 编辑 收藏

最小度限制生成树

给出一个带边权连通无向图，当中指定一个点V0，要求这个图的一个生成树，使得树中V0点的度数（和V0点关联的边数）刚好为一个指定值P，求满足此条件的边权和最小的生成树。

【算法】（某神犇的论文里有详细证明，这里省略了囧……）
设l[i]为连接图中点V0与点i之间的边的长度（若有多条边取权值最小的，若没有边则为无穷大）。
（1）在图中删除点V0，新的图不一定是连通图，设其有B个连通块；
（2）若P<B则无解，否则转下一步；
（3）对这B个连通块分别求最小生成树，得到一个生成森林。然后在图中重新加入点V0，对每个连通块，找出该连通块内l值最小的点V'，添加边(V0, V')，这样就得到了一棵初始的生成树，或者说，这是V0点度数为B的最小的生成树；
（4）然后就是不断往里面加入与V0相关联的边。从V0点开始，对整棵生成树BFS遍历，对每个点i，找到目前的生成树中从V0到i的路径上权值最大的边，设E_len[i]为这条边的权值，E_No[i]为这条边的编号（由于本沙茶使用的是DL边表，故记录编号），这个东东的求法很容易，省略；
（5）最后，枚举除V0点外的每个点，找到(E_len[i]-l[i])值最大的点i，然后在图中删除边E_No[i]，加入边(V0, i)，这样得到的仍然是原图的生成树，且V0的度数增加1；
（6）重复以上过程(P-B)次即得结果。

【实现注意】
为了编程实现更加方便，注意以下几点：
（1）一开始不加入V0，而不是加入了再删去（但各点l值要在输入时求出）；
（2）一开始不用先求出B的值，而是先求出最小生成森林（用Kruskal，不断加边，直到加到不能再加为止）和初始生成树，再遍历初始生成树得到B值；
（3）由于涉及删边，一定要用DL边表。

【代码】（PKU1639，注意这题是求V0度数不超过给定值P的最小生成树，简单改装即可）：
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
const int MAXN = 30, MAXM = 5000, MAXLEN = 20, INF = ~0U >> 2;
struct edge {
    int a, b, len, pre, next;
} ed[MAXM + MAXM];
struct edge0 {
    int a, b, len;
} ed0[MAXM];
int n, m, m0 = 0, P, B = 0, l[MAXN], u[MAXN], B_No[MAXN], q[MAXN], E_No[MAXN], E_len[MAXN], res = 0;
string NAMELIST[MAXN];
bool vst[MAXN];
void add_edge0(int a, int b, int len)
{
    ed0[m0].a = a; ed0[m0].b = b; ed0[m0++].len = len;
}
void init_d()
{
    re(i, n) ed[i].a = ed[i].pre = ed[i].next = i;
    if (n % 2) m = n + 1; else m = n;
}
void add_edge(int a, int b, int len)
{
    ed[m].a = a; ed[m].b = b; ed[m].len = len; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
    ed[m].a = b; ed[m].b = a; ed[m].len = len; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
}
void del_edge(int No)
{
    ed[ed[No].pre].next = ed[No].next; ed[ed[No].next].pre = ed[No].pre;
    ed[ed[No ^ 1].pre].next = ed[No ^ 1].next; ed[ed[No ^ 1].next].pre = ed[No ^ 1].pre;
}
void init()
{
    n = 1; NAMELIST[0] = "Park"; int m_;
    scanf("%d", &m_); char ch = getchar(), s01[MAXLEN], s02[MAXLEN]; int No1, No2, l0, tmp;
    re(i, MAXN) l[i] = INF;
    re(i, m_) {
        scanf("%s %s %d", s01, s02, &l0); ch = getchar();
        No1 = -1; re(j, n) if (NAMELIST[j] == s01) {No1 = j; break;} if (No1 == -1) NAMELIST[No1 = n++] = s01;
        No2 = -1; re(j, n) if (NAMELIST[j] == s02) {No2 = j; break;} if (No2 == -1) NAMELIST[No2 = n++] = s02;
        if (No1 > No2) {tmp = No1; No1 = No2; No2 = tmp;}
        if (No1) add_edge0(No1, No2, l0); else if (l0 < l[No2]) l[No2] = l0;
    }
    scanf("%d", &P);
}
int cmp(const void *s1, const void *s2)
{
    return ((edge0 *)s1)->len - ((edge0 *)s2)->len;
}
int find_root(int x)
{
    int r = x, r0 = x, tmp;
    while (u[r] >= 0) r = u[r];
    while (u[r0] >= 0) {tmp = u[r0]; u[r0] = r; r0 = tmp;}
    return r;
}
void uni(int r1, int r2)
{
    int sum = u[r1] + u[r2];
    if (u[r1] >= u[r2]) {u[r1] = r2; u[r2] = sum;} else {u[r2] = r1; u[r1] = sum;}
}
void prepare()
{
    qsort(ed0, m0, 12, cmp);
    re2(i, 1, n) u[i] = -1; init_d();
    int x1, x2, l0, r1, r2;
    re(i, m0) {
        x1 = ed0[i].a; x2 = ed0[i].b; l0 = ed0[i].len; r1 = find_root(x1); r2 = find_root(x2);
        if (r1 != r2) {uni(r1, r2); add_edge(x1, x2, l0); res += l0;}
    }
    re2(i, 1, n) B_No[i] = -1;
    int Best, Best_No;
    re2(i, 1, n) if (B_No[i] == -1) {
        B_No[i] = B; Best = l[i]; Best_No = q[0] = i;
        int j, k;
        for (int front=0, rear=0; front<=rear; front++) {
            j = q[front];
            for (int p=ed[j].next; p != j; p=ed[p].next) {
                k = ed[p].b;
                if (B_No[k] == -1) {
                    B_No[k] = B; q[++rear] = k; if (l[k] < Best) {Best = l[k]; Best_No = k;}
                }
            }
        }
        add_edge(0, Best_No, Best); res += Best; B++;
    }
}
void solve()
{
    vst[0] = 1;
    re2(P0, B, P) {
        re2(i, 1, n) {E_len[i] = INF; vst[i] = 0;} q[0] = 0;
        int i, j, l0;
        for (int front=0, rear=0; front<=rear; front++) {
            i = q[front];
            for (int p=ed[i].next; p != i; p=ed[p].next) {
                j = ed[p].b; l0 = ed[p].len;
                if (!vst[j]) {
                    vst[j] = 1; q[++rear] = j;
                    if (E_len[i] > l0) {E_len[j] = E_len[i]; E_No[j] = E_No[i];} else {E_len[j] = l0; E_No[j] = p;}
                }
            }
        }
        int Best = 0, Best_No, Best_v;
        re2(i, 1, n) {
            l0 = E_len[i] - l[i];
            if (l0 > Best) {Best = l0; Best_No = E_No[i]; Best_v = i;};
        }
        if (Best) {del_edge(Best_No); add_edge(0, Best_v, l[Best_v]); res -= Best;} else break;
    }
}
void pri()
{
    printf("Total miles driven: %d\n", res);
}
int main()
{
    init();
    prepare();
    solve();
    pri();
    return 0;
}

posted @ 2011-05-23 21:05 Mato_No1 阅读(567) | 评论 (0) | 编辑 收藏

最近捉的一些图论题

     摘要: 【1】PKU1094思考难度不大，就是不断在有向图中加边，求加了几条边以后，图中出现一条连接N个点的简单路径（就是一条长度为(N-1)的链），或者图中出现环。判定连接N个点的简单路径的算法：拓扑排序，若每次队列中有且只有一个入度为0的点，则这样的路径存在，所排出的顺序就是结果。注意两点：（1）如果在前面的若干条边加入后，已经找到了解，那么就输出解，结束（不管后面的边了，即使后面的边加入后形成环也无...  阅读全文

posted @ 2011-05-22 11:09 Mato_No1 阅读(403) | 评论 (0) | 编辑 收藏

Topcoder注册成功

经GYZ、CLJ神牛指点，在N次Error后终于注册成功了……

Topcoder与NOI的规则区别：
【1】Topcoder的代码不是一个完整的代码（连main()都米有），而只是一个类，类里面只有一个方法（相当于main()）。不用输入、输出，系统会将输入数据直接传递到这个方法的参数里，在方法执行完后将返回值直接传递到输出里。类名、方法名、输入参数类型、输出结果类型是在原题中规定的（但参数名、输出结果名可以自定义）。代码中可以（也必须）使用C++ STL。
【2】捉题的时候，题目描述下面的编码区里可以直接编代码，编好后点下面的Compile编译，再点Test测试（可以测试样例和自己的数据），测试完毕后，点Submit提交。所以，不必向其它OJ一样在IDE里编好再Ctrl+ACV提交。
其它的可以参照网上其他人写的东东。

本沙茶先在里面捉了几题（全是水题，神犇不要鄙视），代码：

SRM 506 DIV1 250：
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <iomanip>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define debug(x) cout << #x << " = " << x << endl;
#define pb push_back
#define re_t(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
#define SORT(x) sort(all(x))
#define MP make_pair
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vi::iterator vit;
typedef set<int> si;
typedef si::iterator sit;
typedef map<int,int> mii;
typedef mii::iterator mit;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef istringstream ISS;
typedef ostringstream OSS;
const int MAXN = 175000, INF = ~0U >> 2;
class MathContest {
    public:
    int countBlack(string s0, int p)
    {
        string s = "";
        bool a[MAXN];
        re(i, p) s += s0;
        int n = s.length(), res = 0;
        re(i, n) a[i] = s[i] == 'B';
        int i = 0, j = s.length() - 1;
        bool reversed = 0, turned = 0, v;
        while (i <= j) {
            if (reversed) {
                v = a[j--];
                if (turned) v = !v;
            } else {
                v = a[i++];
                if (turned) v = !v;
            }
            if (v) {res++; turned = !turned;} else reversed = !reversed;
        }
        return res;            
    }
};
SRM 506 DIV2 250：
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <iomanip>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define debug(x) cout << #x << " = " << x << endl;
#define pb push_back
#define re_t(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
#define SORT(x) sort(all(x))
#define MP make_pair
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vi::iterator vit;
typedef set<int> si;
typedef si::iterator sit;
typedef map<int,int> mii;
typedef mii::iterator mit;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef istringstream ISS;
typedef ostringstream OSS;
const int MAXN = 10000, INF = ~0U >> 2;
class SlimeXSlimeRancher2 {
    public:
    int train(vector <int> a)
    {
        int n = a.size(), m = -INF, res = 0;
        re(i, n) m = max(m, a[i]);
        re(i, n) res += m - a[i];
        return res;
    }
};
SRM 506 DIV2 500：
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <iomanip>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define debug(x) cout << #x << " = " << x << endl;
#define pb push_back
#define re_t(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
#define SORT(x) sort(all(x))
#define MP make_pair
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vi::iterator vit;
typedef set<int> si;
typedef si::iterator sit;
typedef map<int,int> mii;
typedef mii::iterator mit;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef istringstream ISS;
typedef ostringstream OSS;
const int MAXN = 10000, INF = ~0U >> 2;
class SlimeXSlimesCity {
    public:
    int merge(vector <int> a)
    {
        int n = a.size();
        SORT(a);
        ll s = 0, s1;
        int res = 0;
        bool ff;
        re(i, n) {
            s += a[i]; s1 = s; ff = 1;
            re2(j, i + 1, n) {
                if (s1 < a[j]) {ff = 0; break;}
                s1 += a[j];
            }
            res += ff;
        }
        return res;    
    }
};

posted @ 2011-05-15 12:20 Mato_No1 阅读(1330) | 评论 (6) | 编辑 收藏

仅列出标题
共12页: First 4 5 6 7 8 9 10 11 12