BZOJ 3995 - [SDOI2015]道路修建

#数据结构 #线段树

Published on 2017-04-07

描述

某国有 $2\times n(n\le 60000)$ 个城市，这 $2\times n$ 个城市构成了一个 $2$ 行 $n$ 列的方格网。现在该国政府有一个旅游发展计划，这个计划需要选定 $l, r(l\le r)$ 两列，修建若干条专用道路，使得这两列之间（包括这两列）的所有 $2(r-l+1)$ 个城市中每个城市可以只通过专用道路就可以到达这 $2(r - l + 1)$ 个城市中的任何一个城市。这种专用道路只能在同一行相邻两列的城市或者同一列的两个城市之间修建，且修建需要花费一定的费用。由于该国政府决定尽量缩减开支，因此政府决定，选定 $l, r$ 后，只修建 $2(r-l+1)-1$ 条专用道路，使得这些专用道路构成一个树结构。

现在你需要帮助该国政府写一个程序，完成这个任务。具体地，该任务包含 $m(m\le 60000)$ 个操作，每个操作的格式如下：

C x0 y0 x1 y1 w：由于重新对第 $x_0$ 行第 $y_0$ 列的城市和第 $x_1$ 行第 $y_1$ 列的城市之间的情况进行了考察，它们之间修建一条专用道路的花费变成了 $w$ ；
Q l r：若政府选定的两列分别为 $l, r$ ，询问政府的最小开支。

分析

本题与 BZOJ 1018 十分类似，由于都只有 2 列，所以可以考虑用线段树来维护一下联通情况。

本题需要维护最小生成树，经过分析发现，对于一个区间 $[l, r]$ ，只需要维护第 $l$ 列的两个点和第 $r$ 列的两个点共四个点的联通情况，以及达到这种情况的最小代价。注意中间的点需要保证与这四个点联通。联通情况一共有十种，分情况讨论不难得出。

合并两个区间时，枚举两个区间的联通情况，再枚举两个区间中间两条边的选取情况，计算出新的联通情况，并更新答案。我这里采用了一个技巧，先预处理出 $\mathrm{trans}(i, j, s)$ 表示第 $i$ 种联通情况与第 $j$ 种联通情况合并，中间两条边选择的情况为 $s$ 转移到的新的联通情况编号，如果不合法则为 $-1$ 。这样转移的时候只需要查表，就能得到新的联通情况。

我看见有人是手动分类讨论来转移的，这样可以做到比较精简，但是很容易讨论出错，我个人认为这种预处理转移表的方法还是比较值得推崇的，毕竟不需要过多的思考。

复杂度显然是： $O(n\log n)$ ，由于合并的时候枚举了所有的情况，常数比较大。

总结：本题思考难度不大，但是细节颇为繁琐。考试的时候碰到这种题，不妨花一点时间思考，用什么方法实现才能写得又快又好。

代码

//  Created by Sengxian on 2017/04/07.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 3995 线段树
#include <bits/stdc++.h>
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 * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 60000 + 3;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
int n, m, a[MAX_N], b[MAX_N], c[MAX_N];

struct Data {
    ll cost[10];

    Data() {}

    Data(int v) {
        memset(cost, 0x3f, sizeof cost);
        cost[2] = 0, cost[9] = v;
    }

    inline ll &operator [] (const int &pos) {
        return *(cost + pos);
    }

    inline ll operator [] (const int &pos) const {
        return *(cost + pos);
    }
} null;

int trans[10][10][4] = {
<!--0-->,
<!--1-->,
<!--2-->,
<!--3-->,
<!--4-->,
<!--5-->,
<!--6-->,
<!--7-->,
<!--8-->,
<!--9--> 
};

inline void relax(ll &a, const ll &b) {
    if (b < a) a = b;
}

inline Data merge(const Data &lhs, const Data &rhs, int pos) {
    if (lhs[0] == -INF) return rhs;
    if (rhs[0] == -INF) return lhs;
    Data res;
    memset(res.cost, 0x3f, sizeof res.cost);
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j)
            for (int s = 1; s <= 3; ++s) if (trans[i][j][s] != -1) {
                relax(res[trans[i][j][s]], lhs[i] + rhs[j] + (s & 1) * a[pos] + ((s >> 1) & 1) * b[pos]);
            }
    return res;
}

namespace SegmentTree {
    const int MAX_NODE = (1 << 16) * 2;

    #define ls (((o) << 1) + 1)
    #define rs (((o) << 1) + 2)
    #define mid (((l) + (r)) >> 1)

    Data datas[MAX_NODE];
    int n;

    void build(int o, int l, int r) {
        if (r - l == 1) {
            datas[o] = Data(c[l]);
        } else {
            build(ls, l, mid), build(rs, mid, r);
            datas[o] = merge(datas[ls], datas[rs], mid - 1);
        }
    }

    void init(int _n) {
        n = _n;
        null[0] = -INF;
        build(0, 0, n);
    }

    Data query(int o, int l, int r, int a, int b) {
        if (r <= a || l >= b) return null;
        if (l >= a && r <= b) return datas[o];
        return merge(query(ls, l, mid, a, b), query(rs, mid, r, a, b), mid - 1);
    }

    void update(int o, int l, int r, int pos) {
        if (r - l == 1) datas[o] = Data(c[l]);
        else {
            if (pos < mid) update(ls, l, mid, pos);
            else update(rs, mid, r, pos);
            datas[o] = merge(datas[ls], datas[rs], mid - 1);
        }
    }

    inline Data query(int l, int r) {
        return query(0, 0, n, l, r);
    }

    inline void update(int pos) {
        update(0, 0, n, pos);
    }

    #undef ls
    #undef rs
    #undef mid
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    n = readInt(), m = readInt();
    for (int i = 0; i < n - 1; ++i) a[i] = readInt();
    for (int i = 0; i < n - 1; ++i) b[i] = readInt();
    for (int i = 0; i < n; ++i) c[i] = readInt();

    SegmentTree::init(n);

    for (int i = 0; i < m; ++i) {
        static char op[2];
        scanf("%s", op);
        if (op[0] == 'C') {
            int x1 = readInt() - 1, y1 = readInt() - 1, x2 = readInt() - 1, y2 = readInt() - 1, w = readInt();
            if (y1 > y2) swap(x1, x2), swap(y1, y2);
            if (x1 > x2) swap(x1, x2), swap(y1, y2);
            if (y1 == y2) {
                c[y1] = w;
            } else {
                if (x1 == 0) a[y1] = w;
                else b[y1] = w;
            }
            SegmentTree::update(y1);
        } else if (op[0] == 'Q') {
            int l = readInt() - 1, r = readInt();
            printf("%lld\n", SegmentTree::query(l, r)[9]);
        }
    }

    return 0;
}

附赠打表的代码：

//  Created by Sengxian on 2017/04/07.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
#include <bits/stdc++.h>
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 * 10 + ch - '0', ch = getchar();
    return n;
}

struct DisjointSet {
    int fa[8];

    DisjointSet() {
        for (int i = 0; i < 8; ++i) fa[i] = i;
    }

    inline 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;
    }

    inline bool same(int x, int y) {
        return find(x) == find(y);
    }
};

const int ALL = 10;
int trans[ALL][ALL][4];

const int sets[][4] = {
    {0, 1, 0, 2},
    {0, 1, 2, 1},
    {0, 1, 0, 1},
    {0, 1, 2, 0},
    {0, 1, 1, 2},
    {0, 0, 1, 0},
    {0, 1, 0, 0},
    {0, 0, 0, 1},
    {0, 1, 1, 1},
    {0, 0, 0, 0}
};

void addEdge(DisjointSet &ds, int start, const int set[]) {
    int fa[4] = {-1, -1, -1, -1};
    for (int i = 0; i < 4; ++i) {
        if (fa[set[i]] == -1) fa[set[i]] = i;
        else ds.unite(i + start, fa[set[i]] + start);
    }
}

inline int getID(DisjointSet &ds, int a, int b, int c, int d) {
    int groupID[8] = {-1, -1, -1, -1, -1, -1, -1, -1}, root[4] = {ds.find(a), ds.find(b), ds.find(c), ds.find(d)};
    int cnt = 0, set[4];
    for (int i = 0; i < 4; ++i) {
        if (groupID[root[i]] == -1) groupID[root[i]] = cnt++;
        set[i] = groupID[root[i]];
    }

    for (int i = 0; i < 8; ++i) if (groupID[ds.find(i)] == -1) return -1;

    for (int i = 0; i < ALL; ++i) {
        bool flag = true;
        for (int j = 0; j < 4; ++j)
            if (sets[i][j] != set[j]) {
                flag = false;
                break;
            }
        if (flag) return i;
    }

    return -1;
}

int main() {
    freopen("table.out", "w", stdout);
    for (int i = 0; i < ALL; ++i)
        for (int j = 0; j < ALL; ++j)
            for (int s = 1; s <= 3; ++s) {
                DisjointSet ds;
                addEdge(ds, 0, sets[i]);
                addEdge(ds, 4, sets[j]);
                if (s & 1) ds.unite(2, 4);
                if (s & 2) ds.unite(3, 5);
                trans[i][j][s] = getID(ds, 0, 1, 6, 7);
            }

    printf("int trans[%d][%d][4] = {\n", ALL, ALL);
    for (int i = 0; i < ALL; ++i) {
        printf("{");
        for (int j = 0; j < ALL; ++j) {
            putchar('{');
            for (int k = 0; k < 4; ++k) {
                printf("%d", trans[i][j][k]);
                if (k + 1 != 4) printf(", ");
            }
            putchar('}');
            if (j + 1 != ALL) printf(", ");
        }
        printf("}%c\n", i + 1 == ALL ? ' ' : ',');
    }
    puts("};");
    return 0;
}

BZOJ 4013 - [HNOI2015]实验比较 BZOJ 3817 - Sum

Sengxian's Blog

BZOJ 3995 - [SDOI2015]道路修建

描述

分析

代码