2020CCPC长春 K

题意：初始有 (n) 个节点 (1) 到 (n)，权值分别为 (a_1...a_n)。
有三种操作，(1.)新建标号为 (x) 的节点，权值为 (y)。(2.) 合并标号为 (x) 和 (y) 所在的树(集合)。(3.) 将标号为 (x) 的节点权值修改成 (y)。每次操作后询问 (gcd(a_i, a_j) = a_i oplus a_j) 的对数，并且要求 (i,j) 在同一树中。

对于 (a_i) 来说，不同的 (gcd) 取值等于约数个数，考虑枚举 (a_i) 的约数并判断这个约数有没有贡献。具体的，
对于 (a_i) 的约数 (x)，我们想找到一个值 (y) 使得 (gcd(a_i,x) = x = a_i oplus y)，即 (y=a_i oplus x)，之后判断 (gcd(a_i,y)) 和 (x) 是否相等，进而得到 (a_i) 的一组解。

然后 (mathcal{O}(nlog^2 n)) 的预处理贡献和 (mathcal{O}(nlog n)) 的启发式合并就可以ac了，合并的时候大概有一个几十的常数。

#include <bits/stdc++.h>
using namespace std;
              
#define fi first
#define se second 
#define mp make_pair
#define pb push_back
#define debug(x) cerr << #x << " is " << x << '
';
 
typedef long long LL;
typedef pair<int, int> pii;
typedef unsigned long long ull;
           
const int N = 5e5 + 5, M = 2e5, P = 1e9 + 7, INF = 0X3F3F3F3F;
const ull D = 743, mo1 = 966335533, mo2 = 966331133;

int n, q, u, v, a[N];
int fa[N], sz[N];
LL ans;
std::vector<int> g[N];
unordered_map<int, LL> dsu[N];

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  for (int i = 1, y; i <= M; i++) {
    for (int j = i + i; j <= M; j += i) {
      y = (j ^ i);
      if (i == __gcd(j, y)) {
        g[j].pb(y);
      }
    }
  }
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    dsu[i][a[i]]++;
  }
  for (int i = 1; i <= n + q; i++) {
    fa[i] = i;
    sz[i] = 1;
  }
  for (int i = 1, op, x, y; i <= q; i++) {
    cin >> op >> x >> y;
    if (op == 1) {
      a[x] = y;
      dsu[x][y]++;
      cout << ans << '
';
    } else if (op == 2) {
      u = find(x), v = find(y);
      if (u != v) {
        if (sz[u] > sz[v]) swap(u, v);
        for (auto &it : dsu[u]) {
          for (auto &it1 : g[it.fi]) {
            if (dsu[v].count(it1)) ans += it.se * dsu[v][it1];
          }
        }
        for (auto &it : dsu[u]) dsu[v][it.fi] += it.se;
        dsu[u].clear();
        fa[u] = v, sz[v] += sz[u];
      }
      cout << ans << '
';
    } else {
      u = find(x);
      for (auto &it :g[a[x]]) {
        if (dsu[u].count(it)) ans -= dsu[u][it];
      }
      dsu[u][a[x]]--;
      a[x] = y;
      for (auto &it :g[a[x]]) {
        if (dsu[u].count(it)) ans += dsu[u][it];
      }
      dsu[u][a[x]]++;
      cout << ans << '
';
    }
  }
  return 0;  
}