Codeforces 348C Subset Sums 分块思想

题意思路：https://www.cnblogs.com/jianrenfang/p/6502858.html

第一次见这种思路，对于集合大小分为两种类型，一种是重集合，一种是轻集合，对于重集合，我们维护这个集合加上的和，已经集合的和。对于轻集合，我们直接暴力在序列上加上和，以及把这种加和对重集合的影响加上。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 100010;
int cnt[maxn][350];
LL sum[maxn], add[maxn], a[maxn];
int mp[350], tot;
vector<int> s[maxn];
bool is_big[maxn];
int main() {
	int n, m, x, y, T;
	scanf("%d%d%d", &n, &m, &T);
	int block = sqrt(n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	} 
	for (int i = 1; i <= m; i++) {
		scanf("%d", &x);
		while(x--) {
			scanf("%d", &y);
			s[i].push_back(y);
		}
		sort(s[i].begin(), s[i].end());
		if(s[i].size() >= block) {
			mp[++tot] = i;
			is_big[i] = 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= tot; j++) {
			int now = mp[j], l = 0, r = 0;
			for (; l < s[i].size(); l++) {
				while(r < s[now].size() && s[now][r] < s[i][l]) r++;
				if(s[now][r] == s[i][l]) cnt[i][j]++;
			}
		}
	}
	for (int i = 1; i <= tot; i++)
		for (int j = 0; j < s[mp[i]].size(); j++) {
			sum[mp[i]] += a[s[mp[i]][j]];
		}
	char str[3];
	while(T--) {
		scanf("%s", str + 1);
		if(str[1] == '+') {
			scanf("%d %d", &x, &y);
			if(is_big[x]) add[x] += y;
			else {
				for (int i = 0; i < s[x].size(); i++)
					a[s[x][i]] += y;
				for (int i = 1; i <= tot; i++)
					sum[mp[i]] += (LL)cnt[x][i] * y;	
			}
		} else {
			LL ans = 0;
			scanf("%d", &x);
			if(is_big[x]) {
				ans += sum[x];
				for (int i = 1; i <= tot; i++) {
					ans += add[mp[i]] * (LL)cnt[x][i];
				}
				printf("%lld
", ans);
			} else {
				for (int i = 0; i < s[x].size(); i++) {
					ans += a[s[x][i]];
				}
				for (int i = 1; i <= tot; i++)
					ans += add[mp[i]] * (LL)cnt[x][i];
				printf("%lld
", ans);
			}
		}
	}
}