NC7609B 牛半仙的妹子图

zrzring 2020-11-18 PM 13℃ 0条

按边权排序后并查集维护在一个连通块的点,bitset维护出现的颜色集合,对于询问求一个前缀和来回答询问就行了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <bitset>

#define int long long

using namespace std;

const int N = 1e6 + 10, M = 2e6 + 10, inf = 0x3f3f3f3f;

const long long Linf = 0x3f3f3f3f3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct EDGE {
    int u, v, t;
} e[N];

int n, m, q, s, P, opt, fa[N], ans[N], t[N], c[N], cnt, pre[N];

bitset<700> S[N];

bool cmp(EDGE a, EDGE b) {return a.t < b.t;}

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

signed main() {
    n = read(); m = read(); q = read(); s = read(); opt = read(); if (opt) P = read();
    for (int i = 1; i <= n; i++) S[i][read()] = 1, fa[i] = i;
    for (int i = 1; i <= m; i++) {
        e[i].u = read(), e[i].v = read(), e[i].t = read() + 1;
    }
    sort(e + 1, e + m + 1, cmp); int cnt = 0; ans[0] = 1; t[0] = 0;
    for (int i = 1; i <= m; i++) {
        int fx = find(e[i].u), fy = find(e[i].v);
        if (fx != fy) {
            if (fy == s) fa[fx] = fy, S[fy] |= S[fx]; else fa[fy] = fx, S[fx] |= S[fy];
        }
        ans[i] = S[s].count(); t[i] = e[i].t;
    }
    for (int i = 1; i <= m; i++) {
        pre[i] = pre[i - 1] + ans[i - 1] * (t[i] - t[i - 1] - 1) + ans[i];
    }
    int last = 0;
    for (int i = 1; i <= q; i++) {
        int l = read(), r = read();
        if (opt) l = (l ^ last) % P + 1, r = (r ^ last) % P + 1; if (l > r) swap(l, r); r++;
        int pl = upper_bound(t + 1, t + m + 1, l) - t - 1;
        int pr = upper_bound(t + 1, t + m + 1, r) - t - 1;
        int res = pre[pr] + (r - t[pr]) * ans[pr] - pre[pl] - (l - t[pl]) * ans[pl];
        printf("%lld\n", last = res);
    }
    return 0;
}

评论


您还没有登录呦


登录 注册
Title - Artist
0:00