题解：CF348C Subset Sums

· · 题解

一眼根号分治，然后发现各种问题置换根本理不清楚。这也是我在想这道题的时候遭遇的最大的困难。

显然的想法：我们设置输入的集合总大小是 \Sigma，那么我们肯定按照 B=\sqrt \Sigma 根号分治：大小大于等于 B 的集合只有至多 B 个。

为了方便，我们称呼大小小于 B 的集合是小集合，大小大于等于 B 的集合是大集合。

我们抛开代码难度不谈，我们总是可以把贡献划分成四块：

不妨考虑最后一个怎么做，因为最后一个的操作指南比较固定（无论是修改还是询问都不能扫描集合）。为了保证单次复杂度 \mathcal O(B)，可以想到：如果我们能修改的时候 \mathcal O(B) 地扫一遍大集合，并计算修改的集合对每个大集合的贡献就好了。

然后可以发现这是容易的，并且显然可以扩展到任意集合对大集合的贡献。只要我们能算出一张表 c_{i,j}，表示每个大集合 i 和每个大集合 j 的交即可。

算出 c 是简单的。显然我们可以维护每个下标所在的大集合，由于所有集合总共只有 \mathcal O(\Sigma) 个数，每个数产生的贡献是 \mathcal O(B) 的，所以复杂度正确。

剩下只用考虑大集合修改，贡献给小集合怎么做。由于我们已经会小集合修改，贡献给大集合了，所以我们只需转置问题，反过来在询问处扫描大集合加入贡献即可。

确实有点绕。但代码还挺好写。

int n,m,q;
int B;
int t;
int org[N];
int id[N];
int big[N];
pair<int,vector<int>> a[N];
vector <int> in[N];
int cnt[N][320];
ll sum[N];
ll del[N],add[N];
int main(){
#ifdef Shun
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    fr1(i,1,n) cin>>org[i];
    B=sqrt(100000);
    fr1(i,1,m){
        int k;
        cin>>k;
        a[i].se.resize(k);
        fr1(j,0,k-1) cin>>a[i].se[j],sum[i]+=org[a[i].se[j]];
        if(k>=B){
            t++;
            big[t]=i,id[i]=t;
            for(auto j:a[i].se) in[j].pb(t);
        }
    }
    fr1(i,1,m){
        for(auto j:a[i].se){
            for(auto k:in[j]) cnt[i][k]++; 
        }
    }
    while(q--){
        char c;
        int k,x;
        cin>>c>>k;
        if(c=='?'){
            if(a[k].se.size()>=B) cout<<sum[k]<<'\n';
            else{
                ll ans=sum[k];
                for(auto j:a[k].se) ans+=del[j];
                fr1(j,1,t) ans+=1ll*cnt[k][j]*add[j];
                cout<<ans<<'\n';
            }
        }
        else{
            cin>>x;
            if(a[k].se.size()>=B) add[id[k]]+=x;
            else for(auto j:a[k].se) del[j]+=x;
            fr1(j,1,t) sum[big[j]]+=1ll*cnt[k][j]*x;
        }
    }
    ET;
}
//ALL FOR Zhang Junhao.