题目传送门
题意
给出一个长度为 \(n\) 的序列 \(a\)，有 \(m\) 个集合，每个集合包含原序列中的 \(s_i\) 个元素，元素所对应的在原序列中的下标分别是 \(p_{i,1},p_{i,2},...,p_{i,s_i}\)。有 \(q\) 次操作，操作一是选定一个集合，给集合中的元素加上一个数 \(x\)，注意这个操作既改变了这个集合也会改变其他包含这个数的集合，操作二是选定一个集合，求集合中所有元素的和。
分析
考虑根号分治，我们定义所有集合大小大于等于 \(\sqrt n\) 的集合为大集合，小于 \(\sqrt n\) 的集合为小集合。核心思路是，对于大集合我们预处理和记录 tag，对于小集合我们暴力维护。
首先考虑如何预处理，对于所有的大集合，我们定义 \(num_{i,j}\) 为第 \(j\) 号大集合和第 \(i\) 号集合的交集的大小，这里算大小时我用了二分，其实可以直接桶排序，做到 \(O(1)\) 算大小。用二分预处理复杂度为 \(O(n\sqrt n\log n)\)。
对于操作一，如果这一次修改的是小集合，那么直接暴力修改，同时要修改与这个小集合有交集的大集合的 sum。如果这次修改是大集合，那么我们只需要修改 tag。
对于操作二，如果这次查询的是小集合，那么我们直接暴力求和，但是不要忘记加上大集合对这个小集合的贡献，直接用大集合的 tag 乘上交集大小即可。如果这次查询是大集合，那么我们要统计其他大集合对这个大集合的贡献，也是 tag 乘交集大小。
最终复杂度为 \(O(n\sqrt n\log n+q\sqrt n)\)。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=101010;
ll n,m,q,a[N],s[N],sum[N],vis[N],tot,tag[N],pos[N],cnt,pre[N];
int num[N][110];
vector<ll>g[N],t;
ll same(ll x,ll y){ll res=0;for(auto i:g[x]){res+=upper_bound(g[y].begin(),g[y].end(),i)-lower_bound(g[y].begin(),g[y].end(),i);}return res;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m>>q;tot=1000;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){cin>>s[i];if(s[i]>tot)vis[i]=1,t.push_back(++cnt),pos[cnt]=i,pre[i]=cnt;for(int j=1;j<=s[i];j++){ll x;cin>>x;sum[i]+=a[x];g[i].push_back(x);}}for(auto i:t)sort(g[pos[i]].begin(),g[pos[i]].end());for(int i=1;i<=m;i++){for(auto j:t){if(i==pos[j])continue;num[i][j]=same(i,pos[j]);}}while(q--){char op;ll x,y;cin>>op;if(op=='+'){cin>>x>>y;if(!vis[x]){for(auto i:g[x])a[i]+=y;for(auto i:t)sum[pos[i]]=sum[pos[i]]+num[x][i]*y;}else tag[x]=tag[x]+y,sum[x]+=y*s[x];}else{cin>>x;if(vis[x]){ll res=0;for(auto i:t)res=res+num[x][i]*tag[pos[i]];cout<<sum[x]+res<<"\n";}else{ll res=0;for(auto i:g[x])res+=a[i];for(auto i:t)res=res+num[x][i]*tag[pos[i]];cout<<res<<"\n";}}}return 0;
}