Siyuan

「UOJ 274」温暖会指引我们前行
「UOJ 274」温暖会指引我们前行
扫描右侧二维码阅读全文
06
2019/03

「UOJ 274」温暖会指引我们前行

题目链接:UOJ 274

虽然小 R 住的宿舍楼早已来了暖气,但是由于某些原因,宿舍楼中的某些窗户仍然开着(例如厕所的窗户),这就使得宿舍楼中有一些路上的温度还是很低。

小 R 的宿舍楼中有 $n$ 个地点和一些路,一条路连接了两个地点,小 R 可以通过这条路从其中任意一个地点到达另外一个地点。但在刚开始,小 R 还不熟悉宿舍楼中的任何一条路,所以他会慢慢地发现这些路,他在发现一条路时还会知道这条路的温度和长度。每条路的温度都是互不相同的。

小 R 需要在宿舍楼中活动,每次他都需要从一个地点到达另一个地点。小 R 希望每次活动时经过一条最温暖的路径,最温暖的路径的定义为,将路径上各条路的温度从小到大排序后字典序最大。即温度最低的路温度尽量高,在满足该条件的情况下,温度第二低的路温度尽量高,以此类推。小 R 不经过重复的路。由于每条路的温度互不相同,因此只存在一条最温暖的路径。

对于小 R 的每次活动,你需要求出小 R 需要走过的路径总长度。如果小 R 通过当前发现的路不能完成这次活动,则输出 $-1$。

注意本题中的字典序与传统意义上的字典序定义有所不同,对于两个序列 $a,b(a\ne b)$,若 $a$ 是 $b$ 的前缀则 $a$ 的字典序较大,同时可以推出空串的字典序最大。

一共有 $m$ 个事件,事件分为三类。

  1. find id u v t l:表示小 R 发现了一条连接 $u$ 和 $v$ 之间的路,编号为 $id$。相同 $id$ 的边只会出现一次。
  2. move u v:表示小 R 要从 $u$ 到达 $v$,你需要计算出最温暖的路径的长度 ,若不能从 $u$ 到达 $v$,则输出 $-1$。
  3. change id l:表示从 $u$ 到 $v$ 这条边的长度变为了 $l$(保证在当前时间点这条边存在)。

数据范围:$1\le n\le 10^5$,$1\le m\le 3\times 10^5$,$0\le t\le 10^9$,$0\le l\le 10^4$。


Solution

我们用 $\text{LCT}$ 维护子树内最小温度的边,每次加边时如果没有连通则直接加入;否则和目前链 $(u,v)$ 上的最小温度比较,如果 $t$ 大于最小温度则断开最小温度的边,加入 $(u,v)$。查询时直接查链的长度即可。

注意:本题 $\text{hack}$ 数据卡常,因此不要使用 $\text{findroot}$ 查询连通性;而使用并查集

时间复杂度:$\mathcal O(m\log n)$。


Code

#include <cstdio>
#include <algorithm>

const int N = 4e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m, fr[N], to[N], tem[N], len[N], f[N];

struct Node;
Node *null;

struct Node {
    Node *ch[2], *fa;
    int sum, mn, idx;
    bool rev;
    Node(int _idx = 0) {
        ch[0] = ch[1] = fa = null;
        sum = mn = rev = 0, idx = _idx;
    }
    bool get() {
        return fa->ch[1] == this;
    }
    bool isroot() {
        return fa->ch[0] != this && fa->ch[1] != this;
    }
    void reverse() {
        rev ^= 1, std::swap(ch[0], ch[1]);
    }
    void pushup() {
        mn = idx;
        if (ch[0] != null && tem[ch[0]->mn] < tem[mn]) mn = ch[0]->mn;
        if (ch[1] != null && tem[ch[1]->mn] < tem[mn]) mn = ch[1]->mn;
        sum = ch[0]->sum + ch[1]->sum + len[idx];
    }
    void pushdown() {
        if (rev) {
            ch[0]->reverse();
            ch[1]->reverse();
            rev = 0;
        }
    }
} *a[N];

struct LCT {
    LCT(int n) {
        null = new Node();
        null->ch[0] = null->ch[1] = null->fa = null;
        for (int i = 1; i <= n; i++) {
            a[i] = new Node(i);
        }
    }
    void pushtag(Node *x) {
        if(!x->isroot()) pushtag(x->fa);
        x->pushdown();
    }
    void rotate(Node *x) {
        Node *y = x->fa, *z = y->fa;
        int k = x->get();
        !y->isroot() && (z->ch[y->get()] = x), x->fa = z;
        y->ch[k] = x->ch[!k], x->ch[!k]->fa = y;
        x->ch[!k] = y, y->fa = x;
        y->pushup();
    }
    void splay(Node *x) {
        pushtag(x);
        while (!x->isroot()) {
            Node *y = x->fa;
            if (!y->isroot()) {
                rotate(x->get() == y->get() ? y : x);
            }
            rotate(x);
        }
        x->pushup();
    }
    void access(Node *x) {
        for (Node *y = null; x != null; x = (y = x)->fa) {
            splay(x), x->ch[1] = y, x->pushup();
        }
    }
    void makeroot(Node *x) {
        access(x), splay(x), x->reverse();
    }
    Node *findroot(Node *x) {
        access(x), splay(x);
        x->pushdown();
        while (x->ch[0] != null) {
            (x = x->ch[0])->pushdown();
        }
        return x;
    }
    void split(Node *x, Node *y) {
        makeroot(x), access(y), splay(y);
    }
    void link(Node *x, Node *y) {
        makeroot(x);
        if (findroot(y) != x) x->fa = y;
    }
    void cut(Node *x, Node *y) {
        makeroot(x);
        if (findroot(y) == x && x->fa == y && x->ch[1] == null) {
            x->fa = y->ch[0] = null, y->pushup();
        }
    }
};
int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}
int main() {
    scanf("%d%d", &n, &m);
    LCT lct(n + m);
    for (int i = 1; i <= n; i++) {
        tem[i] = INF, f[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        char s[10];
        scanf("%s", s + 1);
        if (s[1] == 'f') {
            int id, u, v, t, l;
            scanf("%d%d%d%d%d", &id, &u, &v, &t, &l), id += n + 1;
            fr[id] = ++u, to[id] = ++v, tem[id] = t, len[id] = l;
            if (find(u) == find(v)) {
                lct.split(a[u], a[v]);
                if (tem[a[v]->mn] < t) {
                    int k = a[v]->mn;
                    lct.cut(a[fr[k]], a[k]), lct.cut(a[to[k]], a[k]);
                    lct.link(a[u], a[id]), lct.link(a[v], a[id]);
                }
            } else {
                lct.link(a[u], a[id]), lct.link(a[v], a[id]);
                f[find(u)] = find(v);
            }
        } else if (s[1] == 'm') {
            int u, v;
            scanf("%d%d", &u, &v), u++, v++;
            if (find(u) != find(v)) puts("-1");
            else lct.split(a[u], a[v]), printf("%d\n", a[v]->sum);
        } else {
            int id, l;
            scanf("%d%d", &id, &l), id += n + 1;
            lct.splay(a[id]), len[id]=l, a[id]->pushup();
        }
    }
    return 0;
}

发表评论