BZOJ 2959 - 长跑

Published on 2016-06-29

题目地址

描述

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

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

学校中有 n(n150000)n(n\le 150000) 个地点,用 11nn 的整数表示,每个地点设有若干个刷卡机。

有以下三类事件:   

  1. 修建了一条连接 AA 地点和 BB 地点的跑道。
  2. AA 点的刷卡机台数变为了BB
  3. 进行了一次长跑。问一个同学从 AA 出发,最后到达 BB 最多可以刷卡多少次。具体的要求如下:   

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

分析

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

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

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

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

如果 (u,v)(u, v) 已经联通,那么要考虑缩环,需要删掉很多点,需要把连接这些点的边连接到缩成的点上。怎么快速缩呢?首先将 uu 改为树根,然后 access(v), splay(v),这样 uvu\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;
}