把所有集合分成大于sqrt(n)和小于sqrt(n)的集合, 处理出每两个集合有交集是多大之后就可以在sqrt(n)的复杂内完成一次操作。
#include#define LL long long#define LD long double#define ull unsigned long long#define fi first#define se second#define mk make_pair#define PLL pair #define PLI pair #define PII pair #define SZ(x) ((int)x.size())#define ALL(x) (x).begin(), (x).end()#define fio ios::sync_with_stdio(false); cin.tie(0);using namespace std;const int N = 1e5 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 998244353;const double eps = 1e-8;const double PI = acos(-1);template inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}template inline void sub(T& a, S b) {a -= b; if(a < 0) a += mod;}template inline bool chkmax(T& a, S b) { return a < b ? a = b, true : false;}template inline bool chkmin(T& a, S b) { return a > b ? a = b, true : false;}const int B = 350;int n, m, q;LL a[N];int cnt[307][N];int cnt2[307][307];LL sum[N], addval[N];int to[N];int fto[N];vector S[N];vector big, sml;vector vc[N];int main() { scanf("%d%d%d", &n, &m, &q); for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); for(int i = 1; i <= m; i++) { int num; scanf("%d", &num); S[i].resize(num); for(int j = 0; j < num; j++) scanf("%d", &S[i][j]); if(num >= B) to[i]= SZ(big), fto[SZ(big)] = i, big.push_back(i); else to[i] = SZ(sml), fto[SZ(sml)] = i, sml.push_back(i); } for(int i = 0; i < SZ(big); i++) { for(auto& x : S[big[i]]) { vc[x].push_back(i); sum[fto[i]] += a[x]; } } for(int i = 0; i < SZ(sml); i++) { for(auto& x : S[sml[i]]) { for(auto& y : vc[x]) { cnt[y][i]++; } } } for(int i = 0; i < SZ(big); i++) { for(auto& x : S[big[i]]) { for(auto& y : vc[x]) { if(i < y) cnt2[i][y]++, cnt2[y][i]++; } } } while(q--) { char op[3]; scanf("%s", op); if(op[0] == '+') { int k, x; scanf("%d%d", &k, &x); if(SZ(S[k]) >= B) { sum[k] += 1LL * SZ(S[k]) * x; addval[k] += x; for(int i = 0; i < SZ(big); i++) { if(to[k] == i) continue; sum[fto[i]] += 1LL * x * cnt2[to[k]][i]; } } else { for(auto& id : S[k]) a[id] += x; for(int i = 0; i < SZ(big); i++) sum[fto[i]] += 1LL * cnt[i][to[k]] * x; } } else { int k; scanf("%d", &k); if(SZ(S[k]) >= B) { printf("%lld\n", sum[k]); } else { LL ans = 0; for(auto& x : S[k]) ans += a[x]; for(int i = 0; i < SZ(big); i++) ans += addval[fto[i]] * cnt[i][to[k]]; printf("%lld\n", ans); } } } return 0;}/**/