1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
| #include <algorithm> #include <bitset> #include <cstdio>
typedef long long ll; const int N = 5e5 + 5, K = 6e2 + 5, BIT = 21; int n, m, q, x, opt, M, tot, f[N << 1], fa[BIT][N << 1], val[N << 1]; std::bitset<K> bit[N << 1]; ll ans, sum[BIT][N << 1], trash; int e_cnt, heads[N << 1];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
struct Edge { int nxt, v, w; Edge() {} Edge(int u, int v, int w) : nxt(u), v(v), w(w) {} inline bool operator<(const Edge &rhs) const { return w < rhs.w; } } e[N], g[N << 1];
inline void add(int u, int v) { g[++e_cnt].v = v, g[e_cnt].nxt = heads[u], heads[u] = e_cnt; }
inline void jump(int &u, int v, ll &res) { for (int i = BIT - 1; ~i; --i) { if (val[fa[i][u]] <= v) { res += sum[i][u]; u = fa[i][u]; } } }
void solve(int u) { for (int i = heads[u], v; i; i = g[i].nxt) { solve(v = g[i].v); sum[0][v] = bit[v].count() * (val[u] - val[v]); } }
int main() { #ifndef ONLINE_JUDGE #ifdef LOCAL freopen("testdata.in", "r", stdin); freopen("testdata.out", "w", stdout); #else freopen("T2.in", "r", stdin); freopen("T2.out", "w", stdout); #endif #endif
scanf("%d%d%d%d%d", &n, &m, &q, &x, &opt); tot = n; if (opt) { scanf("%d", &M); } for (int i = 1, c; i <= n; ++i) { scanf("%d", &c); bit[i].set(c); } for (int i = 1, u, v, w; i <= m; ++i) { scanf("%d%d%d", &u, &v, &w); e[i] = Edge(u, v, w); } for (register int i = 1, end = n << 1; i <= end; ++i) f[i] = i; std::sort(e + 1, e + m + 1); for (int i = 1, u, v; i <= m; ++i) { if ((u = find(e[i].nxt)) != (v = find(e[i].v))) { bit[++tot] |= bit[u]; bit[tot] |= bit[v]; val[tot] = e[i].w; add(tot, u), add(tot, v); fa[0][u] = tot, fa[0][v] = tot; fa[0][tot] = tot; f[u] = f[v] = tot; } }
solve(tot);
for (int i = 1, end = n << 1; i < BIT; ++i) for (int j = 1; j <= end; ++j) { sum[i][j] = sum[i - 1][j] + sum[i - 1][fa[i - 1][j]]; fa[i][j] = fa[i - 1][fa[i - 1][j]]; }
for (int i = 1, l, r; i <= q; ++i) { scanf("%d%d", &l, &r); if (opt) { l = (l ^ ans) % M + 1; r = (r ^ ans) % M + 1; if (l > r) std::swap(l, r); } ans = 0; int cur = x; jump(cur, l, trash); if (r < val[fa[0][cur]]) { ans += (r - l + 1) * bit[cur].count(); } else { ans += (val[fa[0][cur]] - l) * bit[cur].count(); jump(cur, val[fa[0][cur]], trash); jump(cur, r, ans); ans += (r - val[cur] + 1) * bit[cur].count(); } printf("%lld\n", ans); } return 0; }
|