思路好题

首先，将集合大小大于等于sqrt(n)的集合称为重集合，其余称为轻集合，则重集合个数小于等于sqrt(n)。

令f[i][j]表示第i个集合和第j个集合的同样元素个数，这能够在O(n*sqrt(n))内预处理。

再令sum[i]表示第i个重集合的元素和，add[i]表示第i个重集合全部元素的增量标记。

改动操作。重集合直接改动sum[i]和add[i]。轻集合暴力改动，同一时候用f[i][j]改动重集合。

询问操作。重集合直接输出sum[i]，轻集合暴力计算。

总复杂度O(n*sqrt(n))。

注意集合的存储方式。邻接矩阵会超内存。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define F(i,j,n) for(int i=j;i<=n;i++)#define D(i,j,n) for(int i=j;i>=n;i--)#define ll long long#define maxn 100005using namespace std;int n,m,q,cnt,tot,block,head[maxn],id[maxn],f[maxn][400];ll a[maxn],sum[400],add[400];bool g[400][maxn];struct edge_type{int next,to;}e[maxn];inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline void add_edge(int x,int y){ e[++cnt]=(edge_type){head[x],y}; head[x]=cnt;}int main(){ n=read();m=read();q=read(); block=ceil(sqrt(100000)); F(i,1,n) a[i]=read(); F(i,1,m) { int sz=read(); if (sz>=block) id[i]=++tot; while (sz--) { int x=read(); if (id[i]) g[tot][x]=true; add_edge(i,x); } } F(i,1,m) F(j,1,tot) for(int k=head[i];k;k=e[k].next) if (g[j][e[k].to]) f[i][j]++; F(i,1,m) if (id[i]) for(int j=head[i];j;j=e[j].next) sum[id[i]]+=a[e[j].to]; while (q--) { char ch=getchar();while (ch!='?'&&ch!='+') ch=getchar(); if (ch=='?') { int x=read(); if (id[x]) printf("%I64d\n",sum[id[x]]); else { ll ans=0; for(int i=head[x];i;i=e[i].next) ans+=a[e[i].to]; F(i,1,tot) ans+=add[i]*f[x][i]; printf("%I64d\n",ans); } } else { int x=read(),y=read(); F(i,1,tot) sum[i]+=(ll)y*f[x][i]; if (id[x]) add[id[x]]+=y; else for(int i=head[x];i;i=e[i].next) a[e[i].to]+=y; } }}