Codeforces348C - Subset Sums

本文主要是介绍Codeforces348C - Subset Sums，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Portal

Description

给出长度为\(n(n\leq10^5)\)的序列\(\{a_n\}\)以及\(m(m\leq10^5)\)个下标集合\(\{S_m\}(\sum|S_i|\leq10^5)\)，进行\(q(q\leq10^5)\)次操作：

询问下标属于集合\(S_k\)的所有数之和。
将下标属于集合\(S_k\)的所有数加\(x\)。

Solution

记\(N_0=\sqrt{\sum|S_i|}\)。
我们把集合划分成轻集合与重集合，大小超过\(N_0\)的集合就是重集合。容易知道重集合的个数不超过\(N_0\)。对于每个重集合，记录sum表示该集合的和，add表示该集合总体被加了的值，cnt[i]表示该集合与集合\(i\)的交集大小。
询问时，如果是重集合则输出sum；否则暴力求\(\{a\}\)上的和，再加上每个重集合对该轻集合的贡献add*cnt[k]。
修改时，如果是重集合则add+=x；否则暴力修改\(\{a\}\)。然后更新每个重集合的sum，也就是加上x*cnt[k]。

时间复杂度\(O(q\sqrt{\sum|S_i|})\)。

Code

//Subset Sums
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long lint;
inline int read()
{int x=0,f=1; char ch=getchar();while(ch<'0'||'9'<ch) {if(ch=='-') f=-1; ch=getchar();}while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
int const N=1e5+1e3;
int const N0=400;
int n,m,q,n0; lint a[N];
int ori[N];
struct _set{int siz,id; vector<int> x;} s[N];
bool cmpSiz(_set x,_set y) {return x.siz>y.siz;}
bool tmp[N]; int cnt[N0][N]; lint add[N0],sum[N0];
int main()
{n=read(),m=read(),q=read();for(int i=1;i<=n;i++) a[i]=read();int sumK=0;for(int i=1;i<=m;i++){s[i].siz=read(),s[i].id=i,s[i].x.push_back(0); sumK+=s[i].siz;for(int p=1;p<=s[i].siz;p++) s[i].x.push_back(read());}sort(s+1,s+m+1,cmpSiz);for(int i=1;i<=m;i++) ori[s[i].id]=i;n0=sqrt(sumK); int cnt1=0;for(int i=1;s[i].siz>=n0;i++) cnt1=i;for(int i=1;i<=cnt1;i++){memset(tmp,false,sizeof tmp);for(int p=1;p<=s[i].siz;p++) sum[i]+=a[s[i].x[p]],tmp[s[i].x[p]]=true;for(int j=1;j<=m;j++)for(int p=1;p<=s[j].siz;p++) if(tmp[s[j].x[p]]) cnt[i][j]++;}for(int owo=1;owo<=q;owo++){char opt; scanf("%c",&opt);if(opt=='?'){int k=ori[read()];if(k<=cnt1) printf("%lld\n",sum[k]);else{lint res=0;for(int p=1;p<=s[k].siz;p++) res+=a[s[k].x[p]];for(int i=1;i<=cnt1;i++) res+=add[i]*cnt[i][k];printf("%lld\n",res);}}if(opt=='+'){int k=ori[read()]; lint v=read();if(k<=cnt1) add[k]+=v;else for(int p=1;p<=s[k].siz;p++) a[s[k].x[p]]+=v;for(int i=1;i<=cnt1;i++) sum[i]+=v*cnt[i][k];}}return 0;
}