待补:根号分治做法
发现要支持区间加和连通块求和、合并,容易想到分块(虽然我一开始看错题了)。
完全不需要根号分治,直接分块即可。
考虑稍微暴力的分块。区间加的话,散块部分可以直接加到全局的 \(sum\) 数组中,毕竟不是区间求和,然后整块部分直接打标记,记录块内每个连通块的大小即可。然后合并就是对于每一个块分别合并就行。但这样空间是 \(\mathcal{O}(n\sqrt{n})\) 的,考虑优化。
占内存的是要维护每一块的 \(siz\) 数组,发现 \(siz\) 数组会占用很多无用的内存,因为一个块最多只有 \(\mathcal{O}(\sqrt{n})\) 个块,使用 vector 动态扩容即可。即维护每个连通块出现的块的编号和它在该块内的元素数量。这样就做到了空间线性。
时间复杂度:\(\mathcal{O}(n\sqrt{n})\)。空间线性。
代码:
const int N = 2e5 + 10, B = 450 + 10;
int n, m, len, b;
int fa[N], sz[N], L[B], R[B], pos[N];
ll tg[B], sum[N], tmp[B];
vector<pair<int, ll> > v[N];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int main() {
ios
cin >> n >> m;
for (int i = 1; i <= n; i++) {
fa[i] = i;
sz[i] = 1;
}
len = sqrt(n), b = n / len + (n % len != 0);
for (int i = 1; i <= b; i++) {
L[i] = (i - 1) * len + 1, R[i] = min(i * len, n);
for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
}
for (int i = 1; i <= n; i++) v[i].pb(make_pair(pos[i], 1));
for (int t = 1, opt, x, y, z; t <= m; t++) {
cin >> opt >> x;
if (opt == 1) {
cin >> y;
x = find(x), y = find(y);
if (x == y) continue;
memset(tmp, 0, sizeof(tmp));
if (sz[x] > sz[y]) swap(x, y);
fa[x] = y, sz[y] += sz[x], sum[y] += sum[x];
for (int i = 0; i < v[x].size(); i++) tmp[v[x][i].first] += v[x][i].second;
for (int i = 0; i < v[y].size(); i++) tmp[v[y][i].first] += v[y][i].second;
v[x].clear(); v[y].clear();
for (int i = 1; i <= b; i++)
if (tmp[i])
v[y].pb(make_pair(i, tmp[i]));
} else if (opt == 2) {
cin >> y >> z;
int p = pos[x], q = pos[y];
if (p == q) {
for (int i = x; i <= y; i++) sum[find(i)] += z;
continue;
}
for (int i = x; i <= R[p]; i++) sum[find(i)] += z;
for (int i = L[q]; i <= y; i++) sum[find(i)] += z;
for (int i = p + 1; i < q; i++) tg[i] += z;
} else {
x = find(x);
ll res = sum[x];
for (int i = 0; i < v[x].size(); i++)
res += tg[v[x][i].first] * v[x][i].second;
cout << res << "\n";
}
}
return 0;
}