【题解】LC：倍增 / 区间并查集（Range Parallel Unionfind）

做过类似的题原来有模板。【记录】「SCOI2016」三道模拟赛/26.7.12-CSDN博客这里面的第三道。#includebits/stdc.h using namespace std; typedef long long LL; const LL P 998244353; const int N 5e5 10; LL a[N], ans; int fa[21][N]; // fa[i][j] 其实并不代表着 [j, j (1 i) - 1] 区间的都属于 j 的并查集 // 不然初始化的时候不就直接把区间合并了嘛 // 其实这不能单独来看换句话说只有两个不同的 j // 在 fa[i] 里都属于一个并查集才能代表 [j, j (1 i) - 1] 和 [j, j (1 i) - 1] 同属 // 这类似于懒标记但不是向下传递 // 如果这一层两个不同的点并查集相同那就没有接着往下的必要了 int findfa(int c, int x) { if (fa[c][x] x) { return fa[c][x]; } return fa[c][x] findfa(c, fa[c][x]); } void merge(int C, int x, int y) { int tx findfa(C, x), ty findfa(C, y); if (tx ! ty) { fa[C][tx] ty; // 合并第 C 层的并查集 if (C ! 0) { merge(C - 1, x, y); merge(C - 1, x (1 (C - 1)), y (1 (C - 1))); } else { ans (ans a[tx] * a[ty] % P) % P; a[ty] (a[ty] a[tx]) % P; // 只有到最底层才合并 a 数组因为 a 数组管的是单个 } } } int main () { ios::sync_with_stdio(false); cin.tie(0); int n, Q; cin n Q; for (int i 0; i n; i ) { cin a[i]; } for (int i 0; i 20; i ) { for (int j 0; j n; j ) { fa[i][j] j; } } ans 0; while (Q --) { int len, x, y; cin len x y; if (len 0) { cout ans \n; continue; } int lg log2(len); // 1(log2(n)) n // len 0 时 lg 会等于负数所以要特判 merge(lg, x, y); merge(lg, x len - (1 lg), y len - (1 lg)); cout ans \n; } return 0; }