【GDOI 2017第2ラウンドシミュレーションday 1】道路建設(クルーズ最小生成樹+線分樹+集計)

テーマ：

n点,m辺を与える.qグループクエリは,クエリ番号が[l..r]の範囲のすべてのエッジでクルーズカール最小生成ツリーの代価を行うたびにクエリを行う.
1<=n<=100,1<=m<=100000,1<=q<=15000

問題:

n小さいですね.
線分樹でもいいですか.
合併すればいいでしょう.
莫隊+lctはできませんか.
時間複雑度:O(αmn+α q log m n)
Code:

#include
#include
#define fo(i, x, y) for(int i = x; i <= y; i ++)
using namespace std;

const int N = 1e5 + 5;

int n, m, q;
struct edge {
    int u, v, c;
} e[N];
int f[N];

int find(int x) {return f[x] == x ? x : (f[x] = find(f[x]));}

struct tree {
    int s, d[100];
} t[N * 4];

void He(tree &t, tree a, tree b) {
    t.s = t.d[0] = 0;
    fo(i, 1, n) f[i] = i;
    int l = 1, r = 1;
    while(l <= a.d[0] && r <= b.d[0]) {
        if(e[a.d[l]].c < e[b.d[r]].c) {
            if(find(e[a.d[l]].u) != find(e[a.d[l]].v)) {
                t.s += e[a.d[l]].c;
                t.d[++ t.d[0]] = a.d[l];
                f[f[e[a.d[l]].u]] = f[e[a.d[l]].v];
            } 
            l ++;
        } else {
            if(find(e[b.d[r]].u) != find(e[b.d[r]].v)) {
                t.s += e[b.d[r]].c;
                t.d[++ t.d[0]] = b.d[r];
                f[f[e[b.d[r]].u]] = f[e[b.d[r]].v];
            } 
            r ++;
        }
    }
    for(; l <= a.d[0]; l ++) {
        if(find(e[a.d[l]].u) != find(e[a.d[l]].v)) {
            t.s += e[a.d[l]].c;
            t.d[++ t.d[0]] = a.d[l];
            f[f[e[a.d[l]].u]] = f[e[a.d[l]].v];
        } 
    }
    for(; r <= b.d[0]; r ++) {
        if(find(e[b.d[r]].u) != find(e[b.d[r]].v)) {
            t.s += e[b.d[r]].c;
            t.d[++ t.d[0]] = b.d[r];
            f[f[e[b.d[r]].u]] = f[e[b.d[r]].v];
        } 
    }
}

void Build(int i, int x, int y) {
    if(x == y) {
        if(e[x].u != e[x].v) {
            t[i].d[0] = 1; t[i].d[1] = x;
            t[i].s = e[x].c;
        }
        return;
    }
    int m = x + y >> 1;
    Build(i + i, x, m); Build(i + i + 1, m + 1, y);
    He(t[i], t[i + i], t[i + i + 1]);
}

tree p;

tree find(int i, int x, int y, int l, int r) {
    if(x == l && y == r) return t[i];
    int m = x + y >> 1;
    if(r <= m) return find(i + i, x, m, l, r);
    if(l > m) return find(i + i + 1, m + 1, y, l, r);
    He(p, find(i + i, x, m, l, m), find(i + i + 1, m + 1, y, m + 1, r));
    return p;
}

int x, y;

int main() {
    freopen("highway.in", "r", stdin);
    freopen("highway.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &q);
    fo(i, 1, m) scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].c);
    Build(1, 1, m);
    for(; q; q --) {
        scanf("%d %d", &x, &y);
        p = find(1, 1, m, x, y);
        printf("%d
", p.s);
    }
}