CF348C

Feyn · 2022-11-23 17:15:49 · 题解

link & my blog

一道还算不错的根号分治题目。

为啥是根号分治呢，看它比较简洁的要求，看它 10^5 的数据范围和 3 秒的时限，再加上它每个组分得毫无规律，多半是根号分治。然后套路地把所有集合划分成大集合和小集合，然后套路地让别人去更新大集合，然后小集合去更新别人。接下来是展开来说具体做法。

首先是大集合。大集合的答案显然来自于两个个方面：原来数列中的数以及后来更新的数。前者不多说，后者可以看成是这样的：假设 add_x 代表这个集合已经加上的数的和，当前集合是 y，那么第二部分的答案应该是 \sum\limits_{x}add_x\times|x\cap y|。于是要维护的东西就比较显然了，只需要维护每个集合和每个大集合的交集大小，在更新的时候遍历所有大集合，更新当前加的值乘上交集大小即可。该部分显然是 O(\sqrt N) 的。

然后是小集合。由于大集合不会去更新小集合的答案（不然复杂度爆炸），小集合的答案来自于三个方面：原来的数、小集合更新的数、大集合更新的数。第一个不说，第二个，由于小集合元素少，可以每次更新小集合的时候都遍历集合元素并把变化量累加到每个位置上，查询的时候也是遍历元素查询即可。至于第三个，可以用相似的方法，遍历这个集合和所有大集合的交集，算上大集合的变化量即可。

细节不是很多，放一下代码：

#include<bits/stdc++.h>
//#define feyn
#define int long long
#define ptt pair<int,int>
#define mp make_pair
using namespace std;
const int N=100010;
const int P=1000;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}

int m,n,q,a[N],addTag[N],sum[N];

vector<int>s[N],pl[N];
vector<ptt>f[N];

int iNum,ins[N],insId[N];
bitset<N>vis[P];

signed main(){

    #ifdef feyn
    freopen("in.txt","r",stdin);
    #endif

    read(m);read(n);read(q);
    for(int i=1;i<=m;i++)read(a[i]);
    for(int i=1;i<=n;i++){
        int nowNum,nowData;read(nowNum);
        while(nowNum--)read(nowData),s[i].push_back(nowData);
        if(s[i].size()>P){
            ins[++iNum]=i;insId[i]=iNum;
            for(int Data:s[i]){
                pl[Data].push_back(i);
                vis[iNum].set(Data);
                sum[i]+=a[Data];
            }
        }
    }
    for(int x=1;x<=n;x++){
        if(s[x].size()<=P)continue;
        int xx=insId[x];
        for(int y=1;y<=n;y++){
            int nowNum=0;
            if(s[y].size()<=P)for(int Data:s[y])nowNum+=vis[xx][Data];
            else nowNum=(vis[xx]&vis[insId[y]]).count();
            f[y].push_back(mp(x,nowNum));
        }
    }
    while(q--){
        char op;int x,y;cin>>op;read(x);
        if(op=='?'){
            if(s[x].size()<=P){
                int nowAn=0;
                for(int Data:s[x])nowAn+=a[Data];
                for(ptt Data:f[x])nowAn+=addTag[Data.first]*Data.second;
                printf("%I64d\n",nowAn);continue;
            }
            printf("%I64d\n",sum[x]);continue;
        }
        read(y);addTag[x]+=y;
        if(s[x].size()<=P)for(int nowPl:s[x])a[nowPl]+=y;
        for(ptt Data:f[x])sum[Data.first]+=Data.second*y;
    }

    return 0;
}