题解：CF348C Subset Sums

· · 题解

题目传送门

题意

给出一个长度为 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;
}