按边权排序后并查集维护在一个连通块的点,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; }