C 牛牛的无向图

题目地址：

https://ac.nowcoder.com/acm/contest/7079/C

基本思路：

我们考虑离线每次查询的,
在最小生成树的过程中,我们每次是从小往大加边的,
同样将也按从小到大排序,
每次加到一个比当前要大的边的时候,
之前的那些已经连上的边一定是都比小的,
所以在这些联通块中的点，两两之间的一定是比小的,也就是符合条件的,
那么这时符合条件的点对的数量就是(为每个联通块的大小),
每次并查集合并时维护这个结果就行了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

unsigned int SA, SB, SC; int n, m, q, LIM;
unsigned int rng61() {
  SA ^= SA << 16;
  SA ^= SA >> 5;
  SA ^= SA << 1;
  unsigned int t = SA;
  SA = SB;
  SB = SC;
  SC ^= t ^ SA;
  return SC;
}
const int maxn = 1e6 + 10;
ll u[maxn],v[maxn],w[maxn],L[maxn];
void gen() {
  scanf("%d%d%d%u%u%u%d", &n, &m, &q, &SA, &SB, &SC, &LIM);
  for (int i = 1; i <= m; i++) {
    u[i] = rng61() % n + 1;
    v[i] = rng61() % n + 1;
    w[i] = rng61() % LIM;
  }
  for (int i = 1; i <= q; i++) {
    L[i] = rng61() % LIM;
  }
}
ll par[maxn],sz[maxn];
ll find(ll x){ return par[x] == x ? x : par[x] = find(par[x]); }
bool same(ll x,ll y){ return find(x) == find(y); }
struct Edge{
    ll u,v,w;
    bool operator < (const Edge &no) const {
      return w < no.w;
    }
};
vector<Edge> edge;
signed main() {
  gen();
  for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
  rep(i, 1, m) edge.push_back({u[i], v[i], w[i]});
  sort(L + 1, L + 1 + q);
  ll pos = 1,ans = 0,res = 0;
  sort(all(edge));
  for (auto it : edge) {
    if (!same(it.u, it.v)) {
      while (it.w > L[pos] && pos <= q) { ans ^= res; pos++; }
      ll x = find(it.u),y = find(it.v);
      res -= sz[x] * (sz[x] - 1ll) / 2ll + sz[y] * (sz[y] - 1ll) / 2ll; // 消除要联通的这两个联通块的贡献;
      par[x] = y; sz[y] += sz[x];
      res += sz[y] * (sz[y] - 1ll) / 2ll;// 加上新生成的这个联通块的贡献;
    }
  }
  rep(i,pos,q) ans ^= res;
  cout << ans << '\n';
  return 0;
}