Luogu8360 Editorial

· · 题解

不是很优秀的 \Theta(n\sqrt n\log n) 做法，但是可以通过本题。

使用线段树之类的数据结构维护需要记录每个区间的所有颜色的变化信息，下传上传复杂度都很大，不划算。

那么用分块来做，每个块维护每种颜色的出现位置以及在 2 操作中被加的权值总和。

此时对于 “散块重构” 的问题可以使用每种颜色的出现位置还原块内元素的真实 a,c 值，进行完 c_i 修改 或者 a_i 增加以及求和操作之后再重新进行统计即可

对于 1 操作，可以使用启发式合并来实现对位置信息的维护，由于交换 std::vector 的复杂度是 \Theta(1) 所以也可以简单实现。

注意这里因为大小关系交换两个颜色的位置之后对应的加法标记也要交换，而从一个颜色被扔到另一个颜色的 vector 中时需要先加自己的标记再减去目标颜色的标记来保证后续调用 a_i+tag_{c_i} 得到的信息正确。

直接使用 __gnu_pbds::gp_hash_table 来维护块内颜色的在线做法只能得到 55 分，但是这题可以离线。

所以对于每个块处理它对于每个询问的贡献即可，想找当前在块里面的出现颜色可以另维护一个 set ，不想这里的 \log 可以使用 vector，不要求元素不重复，扫描的时候不重复扫描就行了。

const int N=2.5e5+10;
int n,Q,C,c[N],a[N];
int block;
int ql[N],qr[N],qx[N],qy[N],ans[N],opt[N];
int tag[N];
vector<int> pos[N];
bool vis[N];
signed main(){
    n=read(); Q=read(); C=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=n;++i) c[i]=read();
    block=sqrt(n);
    for(int i=1;i<=Q;++i){
        opt[i]=read(); ql[i]=read(); qr[i]=read();
        if(opt[i]!=3) qx[i]=read(),qy[i]=read();
    }
    for(int l=1,r;l<=n;l=r+1){
        r=min(l+block-1,n);
        for(int i=1;i<=C;++i){
            tag[i]=0;
            pos[i].clear();
        }
        int sum=0;
        vector<int> cols;
        for(int i=l;i<=r;++i){
            pos[c[i]].emplace_back(i);
            if(!vis[c[i]]){
                cols.emplace_back(c[i]);
                vis[c[i]]=1;
            }
            sum+=a[i];
        }
        for(int i=l;i<=r;++i) vis[c[i]]=0;
        for(int id=1;id<=Q;++id){
            if(qr[id]<l||ql[id]>r) continue;
            int x=qx[id],y=qy[id];
            if(ql[id]<=l&&qr[id]>=r){
                if(opt[id]==1){
                    if(pos[x].empty()) continue;
                    cols.emplace_back(y);
                    if(pos[x].size()>pos[y].size()){
                        swap(pos[x],pos[y]);
                        swap(tag[x],tag[y]);
                    }
                    while(pos[x].size()){
                        int t=pos[x].back(); pos[x].pop_back();
                        a[t]+=tag[x];
                        a[t]-=tag[y];
                        pos[y].emplace_back(t);
                    }
                    tag[x]=0;
                }else if(opt[id]==2){
                    if(pos[x].size()){
                        tag[x]+=y;
                        sum+=pos[x].size()*y;
                    }
                }else ans[id]+=sum;
            }else{
                for(auto col:cols) if(!vis[col]){
                    for(auto i:pos[col]) a[i]+=tag[c[i]=col];
                    tag[col]=0;
                    vis[col]=1;
                    pos[col].clear();
                }
                for(auto col:cols) vis[col]=0;
                cols.clear();
                int L=max(l,ql[id]),R=min(r,qr[id]);
                for(int i=L;i<=R;++i){
                    if(opt[id]==1){
                        if(c[i]==x) c[i]=y;
                    }else if(opt[id]==2){
                        if(c[i]==x) a[i]+=y;
                    }else if(opt[id]==3){
                        ans[id]+=a[i];
                    }
                }
                sum=0;
                for(int i=l;i<=r;++i){
                    sum+=a[i];
                    pos[c[i]].emplace_back(i);
                    if(!vis[c[i]]){
                        cols.emplace_back(c[i]);
                        vis[c[i]]=1;
                    }
                }
                for(int i=l;i<=r;++i) vis[c[i]]=0;
            }
        }
    }
    for(int i=1;i<=Q;++i) if(opt[i]==3) print(ans[i]);
    return 0;
}