over 2 years ago

前言

开始集训了,我就又开始更新博客了。。
今天zzj讲了一点树上莫队。。。我就拿出来讲讲吧。。。可能和别人的不一样咯。。
这玩意而主要是处理链的询问,其实跟莫队差不多的思想。
这玩意儿比选关键点的方法好写多了。。。

分块方法

参见bzoj1086(貌似也是sgu的原题),就是选一个阈值然后按照那道题里的方法分块,这个分块的好处在于块内与相邻块之间的移动都是的。

移动方法

我们将询问按照所在块编号为第一关键字,所在块编号(或序编号)为第二关键字排序,将一条路径暴力转移到下一条路径即可,转移过程中涉及到路径取反的问题,有一些细节,我贴一个自认为还算好的代码:

//inner[x] 代表x是否在路径内
//dep[x] 代表x的深度
//cross 代表旧路径与新路径的交界点

//inverse x
void inv(int x) {
    if(inner[x]) {
        inner[x] = false;
        delete(x);
    }
    else {
        inner[x] = true;
        insert(x);
    }
}

//move x up
void move_up(int &x) {
    if(!cross) {
        if(inner[x] && !inner[fa[x]]) cross = x;
        else if(inner[fa[x]] && !inner[x]) cross = fa[x];
    }
    inv(x), x = fa[x];
}

//move a to b
void move(int a, int b) {
    if(a == b) return ;
    cross = 0;
    if(inner[b]) cross = b;
    while(dep[a] > dep[b]) move_up(a);
    while(dep[b] > dep[a]) move_up(b);
    while(a != b) move_up(a), move_up(b);
    inv(a), inv(cross);
}

时间复杂度

由于这样的分块方法在块内移动,块之间移动都是的,可以证明时间复杂度是,分别是第一个点和第二个点的时间复杂度。

spoj COT2

一道很经典的题目了,做法有很多,今天用树上莫队写了一发,加了输入输出优化成功卡到了rank1
思路就是我们按照常规的将询问排序后,直接暴力修改即可。。。说到底就是优化了的暴力。。。取即可。
spoj COT2(树上莫队).cpp

WC2013 糖果公园

带修改的也不要怂,一样可以树上莫队干起来!
我们把询问按照所在块编号分别为关键字排序,然后对于两个块之间的所有操作,按时间排序(包括修改),暴力做,因为在同一个块之间移动时间是的,在块之间移动的时间复杂度是,修改的时间复杂度是,因此总时间复杂度就是,我们取,由于同阶,因此最终时间复杂度就是,赤裸裸的暴力。。。
park(树上莫队).cpp

这玩意儿真的太好写了!!!

← sgu313:Circular Railway bzoj2125:最短路 →
 
comments powered by Disqus