isaster(Comet OJ - Contest #11D题+kruskal重构树+线段树+倍增)

目录
  • 题目链接
  • 思路
  • 代码

题目链接

传送门

思路

\(kruskal\)重构树\(+\)线段树\(+\)倍增

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define fi first
#define se second
#define lson (rt<<1)
#define rson (rt<<1|1)
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["< '9') f |= (ch == '-'), ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x = f ? -x : x;
}

pii edge[maxn*2];
vector vec[maxn];
int n, m, q, op, x, y, dfn;
int Fa[maxn], mul[maxn<<2], fa[maxn][22], w[maxn], ls[maxn], rs[maxn], dd[maxn];

int fi(int x) {
    return Fa[x] == x ? x : Fa[x] = fi(Fa[x]);
}

void dfs(int u, int p) {
    fa[u][0] = p, ls[u] = ++dfn, dd[dfn] = u;
    for(int i = 1; i <= 20; ++i) fa[u][i] = fa[fa[u][i-1]][i-1];
    for(int i = 0; i < (int)vec[u].size(); ++i) {
        int v = vec[u][i];
        dfs(v, u);
    }
    rs[u] = dfn;
}

void push_up(int rt) {
    mul[rt] = 1LL * mul[lson] * mul[rson] % mod;
}

void build(int rt, int l, int r) {
    if(l == r) {
        mul[rt] = w[dd[l]];
        return;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid), build(rson, mid + 1, r);
    push_up(rt);
}

void update(int rt, int l, int r, int pos, int val) {
    if(l == r) {
        mul[rt] = val % mod;
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(lson, l, mid, pos, val);
    else update(rson, mid + 1, r, pos, val);
    push_up(rt);
}

int query(int rt, int l, int r, int L, int R) {
    if(l == L && R == r) return mul[rt];
    int mid = (l + r) >> 1;
    if(R <= mid) return query(lson, l, mid, L, R);
    else if(L > mid) return query(rson, mid + 1, r, L, R);
    else return 1LL * query(lson, l, mid, L, mid) * query(rson, mid + 1, r, mid + 1, R) % mod;
}

void solve(int x, int y) {
    if(x > y) {
        printf("0\n");
        return;
    }
    for(int i = 20; i >= 0; --i) {
        if(fa[x][i] != 0 && fa[x][i] <= y) x = fa[x][i];
    }
    printf("%d\n", query(1, 1, n, ls[x], rs[x]));
}

int main() {
#ifndef ONLINE_JUDGE
FIN;
#endif // ONLINE_JUDGE
    n = read(), m = read(), q = read();
    for(int i = 1; i <= n; ++i) w[i] = read(), w[i] %= mod, Fa[i] = i;
    int x, y;
    for(int i = 1; i <= m; ++i) {
        x = read(), y = read();
        if(x < y) swap(x, y);
        edge[i] = {x, y};
    }
    sort(edge + 1, edge + m + 1);
    for(int i = 1; i <= m; ++i) {
        x = edge[i].fi, y = edge[i].se;
        x = fi(x), y = fi(y);
        if(x == y) continue;
        if(x > y) Fa[y] = x, vec[x].push_back(y);
        else Fa[x] = y, vec[y].push_back(x);
    }
    dfs(n, 0);
    build(1, 1, n);
    while(q--) {
        op = read(), x = read(), y = read();
        if(op == 1) {
            solve(x, y);
        } else {
            update(1, 1, n, ls[x], y);
        }
    }
    return 0;
}
迷之线段树迷之最小生成树

相关

标签