nkoj4400 子集求和

萌新刚学根号分治系列

根号分治，即把一个问题分成两类，一类是规模小于 $\sqrt{n}$ 的，一类是规模大于 $\sqrt{n}$ 的。当然这个阈值有时候可能为了常数乃至复杂度需要调整。

这题可以拿来分的就只有集合的大小了。我们把元素个数小于 $\sqrt{n}$ 的叫做小集合，否则叫做大集合。显然，大集合的个数不超过 $\sqrt{n}$

预处理 $unionset[i]$ 表示所有与 $i$ 相交的大集合（不预处理临时暴力枚举也可以的）。$cnt[i][j]$ 表示 $i$ 集合与第 $j$ 个大集合的交集大小，这部分是 $O(n\sqrt{n})$ 的。

还有个 $Lazy[i]$ 表示第 $i$ 个大集合的懒标记（里面的数需要加上多少），$sum[i]$ 表示只考虑小集合的修改时第 $i$ 个大集合当前答案。

处理操作：

• 查询第 $i$ 个小集合对应序列元素之和。
• 这种情况直接暴逆就好了，没什么好说的，复杂度显然 $O(\sqrt{n})$。
• 查询第 $i$ 个大集合对应序列元素之和。
• 答案为 $sum[i]+\sum cnt[i][j]\times Lazy[i]$，$j$ 是大集合。即临时累加大集合的修改对该次询问的影响。
• 将第 $i$ 个小集合所有元素加上 $x$。
• 将第 $i$ 个小集合的元素暴力修改，再枚举所有大集合 $j$，处理对大集合的影响（$sum[j]+=cnt[i][j]\times x$）。
• 将第 $i$ 个大集合所有元素加上 $x$。
• 直接加 $Lazy$ 即可。

#include <cstdio>
#include <vector>
#include <cmath>
#define int long long
#define set wtcl//防撞关键字（雾

int a[100005], cnt[100005][350], id[100005];
int sum[100005], Lazy[100005], S, tot;
std::vector<int> set[100005], num[100005], unionset[100005];//num[i]即所有包含第i个数的大集合的编号，预处理cnt和unionset要用到
bool mark[100005][350];

signed main() {
	int n, m, q;
	scanf("%lld%lld%lld", &n, &m, &q);
	S = sqrt(n);
	for (int i = 1; i <= n; ++ i) scanf("%lld", a + i);
	for (int i = 1; i <= m; ++ i) {
		int k, x;
		scanf("%lld", &k);
		if (k > S) id[i] = ++ tot;
		while (k --) {
			scanf("%lld", &x);
			set[i].push_back(x);
			if (id[i]) num[x].push_back(i), sum[id[i]] += a[x];
		}
	}
	for (int i = 1; i <= m; ++ i)
		for (int j : set[i])
			for (int k : num[j]) {
				if (!mark[i][id[k]]) {//如果i的unionset还没有加入第k个集合（k集合是大集合）
					mark[i][id[k]] = true;
					unionset[i].push_back(id[k]);
				}
				++ cnt[i][id[k]];
			}
	while (q --) {
		char opt;
		int k, x;
		scanf(" %c", &opt);
		if (opt == '?') {
			scanf("%lld", &k);
			int ans = 0;
			if (set[k].size() <= S) {
				for (int i : set[k]) ans += a[i];
				for (int i : unionset[k]) ans += cnt[k][i] * Lazy[i];
			}
			else {
				ans = sum[id[k]];
				for (int i = 1; i <= tot; ++ i)
					ans += cnt[k][i] * Lazy[i];
			}
			printf("%lld\n", ans);
		} else {
			scanf("%lld%lld", &k, &x);
			if (set[k].size() <= S) {
				for (int i : set[k]) a[i] += x;
				for (int i : unionset[k])
					sum[i] += cnt[k][i] * x;
			} else Lazy[id[k]] += x;
		}
	}
	return 0;
}