BZOJ 2959 - 长跑 | Sengxian's Blog

BZOJ 2959 - 长跑

#并查集 #LCT #边-双连通

Published on 2016-06-29

题目地址

描述

某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”，同学们纷纷离开寝室，离开教室，离开实验室，到操场参加 3000 米长跑运动。一时间操场上熙熙攘攘，摩肩接踵，盛况空前。

为了让同学们更好地监督自己，学校推行了刷卡机制。

学校中有 $n(n\le 150000)$ 个地点，用 $1$ 到 $n$ 的整数表示，每个地点设有若干个刷卡机。

有以下三类事件：　　

修建了一条连接 $A$ 地点和 $B$ 地点的跑道。
$A$ 点的刷卡机台数变为了 $B$ 。
进行了一次长跑。问一个同学从 $A$ 出发，最后到达 $B$ 最多可以刷卡多少次。具体的要求如下：

当同学到达一个地点时，他可以在这里的每一台刷卡机上都刷卡。但每台刷卡机只能刷卡一次，即使多次到达同一地点也不能多次刷卡。
为了安全起见，每条跑道都需要设定一个方向，这条跑道只能按照这个方向单向通行。最多的刷卡次数即为在任意设定跑道方向，按照任意路径从 $A$ 地点到 $B$ 地点能刷卡的最多次数。

分析

考虑询问操作，对于一个环，我们可以将环中的边顺序定向，这样就保证能将环中的点全部走过，而且能够进环以及出环。

事实上，只要在一个边-双联通分量里面，我们就可进入边-双连通分量，走过所有的点，再出来。简单证明一下，假设 $u$ 进 $v$ 出，我们先从 $u$ 走到 $v$ ，再从 $v$ 走到 $u$ ，再走第一次的路径从 $u$ 到 $v$ 出去。根据双联通分量的定义，一定存在两条不相交的路径，所以我们可以把边全部定向，使得可以走过所有的点然后出去。

环是一个边-双联通分量，将环缩成点，形成一棵树，如果又加边形成了环，那么又可以将环缩成点。
那么询问 $u\rightarrow v$ 的路径，就是询问 $u$ 缩成的点与 $v$ 缩成的点在新的树里面的点权和，我们考虑用 LCT 维护缩点后的森林。

考虑添加一条边 $(u, v)$ ，如果 $u, v$ 本身为一个点（缩点后的点），不管。如果 $(u, v)$ 不联通，直接在 LCT 里面加边即可。

如果 $(u, v)$ 已经联通，那么要考虑缩环，需要删掉很多点，需要把连接这些点的边连接到缩成的点上。怎么快速缩呢？首先将 $u$ 改为树根，然后 access(v), splay(v)，这样 $u\rightarrow v$ 路径上的点都在一起了，那么我们遍历一下这个 Splay，清空非根节点，将其余的点再并查集里面与根节点合并，并且权值加在根节点的 Splay 节点上面。这样就缩成了一个点，只有指向被删除的点的虚边还是不对的，但是不能够直接修改，怎么办呢？考虑访问虚边的时候再来改，我们在 access 的时候，找 fa 的时候再并查集里面更新一次它的 fa 就可以获得缩点得到的 fa 了，由于修改主链的操作只在 access 里面有，所以只需修改 access，其余的函数不用动，这样是正确的。

剩下的都是 LCT 的基本操作了，我就不多说了。还有别的更快的方法，但是我也不会啊QAQ。

代码

//  Created by Sengxian on 6/29/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2959 LCT + 缩环
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 150000 + 3;

struct union_set {
    int fa[maxn];
    inline void init(int n) {
        for (int i = 0; i < n; ++i) fa[i] = i;
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    inline void unite(int x, int y) {
        x = find(x), y = find(y);
        fa[x] = y;
    }
}s1, s2;
//s1 for circle, s2 for connective

namespace link_cut_tree {
    const int maxNode = maxn;
    struct splay *null;
    struct splay {
        splay *fa, *ch[2];
        int val, sum, c;
        bool reversed;
        inline void maintain() {sum = ch[0]->sum + ch[1]->sum + val;}
        inline void reverse() {swap(ch[0], ch[1]), reversed ^= 1, c = c == -1 ? -1 : c ^ 1;}
        inline void push_down() {if (reversed) ch[0]->reverse(), ch[1]->reverse(), reversed = false;}
        inline bool is_root() {return fa == null || (fa->ch[0] != this && fa->ch[1] != this);}
    }pool[maxNode];
    void init() {
        null = new splay();
        null->fa = null, null->ch[0] = null->ch[1] = null;
        null->sum = 0;
    }
    inline void rotate(splay* &o, int d) {
        splay *k = o->ch[d ^ 1];
        k->fa = o->fa, o->fa = k, k->ch[d]->fa = o;
        o->ch[d ^ 1] = k->ch[d], k->ch[d] = o;
        o->maintain(), k->maintain();
        o = k;
    }
    void _splay(splay* &o) {
        o->push_down();
        int d = o->c;
        if (d != -1) {
            splay *p = o->ch[d];
            p->push_down();
            int d2 = p->c;
            if (d2 != -1) {
                _splay(p->ch[d2]);
                if (d == d2) rotate(o, d ^ 1); else rotate(o->ch[d], d);
            }
            rotate(o, d ^ 1);
        }
    }
    inline void Splay(splay *o) {
        o->c = -1;
        while (!o->is_root()) {
            o->fa->c = o->fa->ch[1] == o;
            o = o->fa;
        }
        _splay(o);
    }
    #define toID(i) ((i) - pool)
    #define toNode(i) (pool + (i))
    inline void access(splay *o) {
        splay *k = null;
        while (o != null) {
            Splay(o);
            o->ch[1] = k;
            o->maintain();
            k = o;
            //缩环只会影响虚边,所以在这里更新缩环后的父亲就可以了.
            if (o->fa != null) o->fa = toNode(s1.find(toID(o->fa)));
            o = o->fa;
        }
    }
    inline void make_root(splay *o) {
        access(o), Splay(o);
        o->reverse();
    }
    inline void link(splay *a, splay *b) {
        make_root(a);
        a->fa = b;
    }
    inline void redution(splay* &a, splay *b) {
        if (a == null) return;
        assert(toID(b) == s1.find(toID(b)));
        s1.unite(toID(a), toID(b)); //一定是将 a 集合接在 b 上面,要保证 b 是根!
        b->val += a->val;
        redution(a->ch[0], b), redution(a->ch[1], b);
        a = null;
    }
    inline void circle(splay *a, splay *b) {
        make_root(a), access(b), Splay(b);
        redution(b->ch[0], b); //将 a->b 缩成 b
        assert(b->ch[1] == null);
    }
}

using namespace link_cut_tree;
int n, m, a[maxn];

int main() {
#ifndef ONLINE_JUDGE
    freopen("run0.in", "r", stdin);
#endif
    n = ReadInt(), m = ReadInt();
    s1.init(n), s2.init(n), init();
    for (int i = 0; i < n; ++i) {
        pool[i].fa = null, pool[i].ch[0] = pool[i].ch[1] = null;
        pool[i].val = pool[i].sum = a[i] = ReadInt();
        pool[i].reversed = false;
    }
    while (m--) {
        int p = ReadInt();
        if (p == 1) {
            int u = ReadInt() - 1, v = ReadInt() - 1;
            if (s1.find(u) == s1.find(v)) continue; //缩点后自环
            //注意任何时候都要用对应的点来代表自己!
            if (s2.find(u) != s2.find(v)) { //不在一棵树中
                u = s1.find(u), v = s1.find(v);
                link(toNode(u), toNode(v));
                s2.unite(u, v);
            } else { //缩环
                u = s1.find(u), v = s1.find(v);
                circle(toNode(u), toNode(v));
            }
        } else if (p == 2) {
            int u = ReadInt() - 1, val = ReadInt();
            splay *ne = toNode(s1.find(u));
            Splay(ne);
            ne->val += val - a[u];
            ne->maintain();
            a[u] = val;
        } else if (p == 3) {
            int u = ReadInt() - 1, v = ReadInt() - 1;
            if (s2.find(u) != s2.find(v)) puts("-1");
            else {
                u = s1.find(u), v = s1.find(v);
                if (u == v) {printf("%d\n", toNode(u)->val);continue;}
                make_root(toNode(u)), access(toNode(v)), Splay(toNode(v));
                printf("%d\n", toNode(v)->sum);
            }
        } else assert(false);
    }
    return 0;
}

BZOJ 3881 - [Coci2015]Divljak BZOJ 3754 - Tree之最小方差树