自动搬运

查看原文

来自洛谷，原作者为

	H17 *　*

搬运于2025-08-24 23:15:43，当前版本为作者最后更新于2025-05-11 10:16:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

第二道学会了的 Ynoi 题（注意不是场切）。

题目分析

首先由于操作是对 $i\in[l,r] \operatorname{R}(i)$ 进行的，所以不妨考虑直接拍到一个序列里，记为 $\{a_{2m}\}$。

同时假设 $\operatorname R(i)$ 在序列中的位置是 $L_i\sim R_i$。

题目就可以转化为：

1. 对于 $i\in[L_l,R_r]$，$w_{a_i}\gets w_{a_i}+v$；
2. 求 $\sum\limits_{i=L_l}^{R_r} w_{a_i}$。

（我只能自己想到这里，我太菜了。）

我们考虑对 $a_{l\sim r}$ 的贡献。

第一种：包含 $[l,r]$ 的操作 $1$，直接贡献到 $w_{a_i}$；第二种：对于 $a_i=a_j(i\in[l,r],j\notin[l,r])$ 时，操作会对 $w_{a_j}$ 贡献。（对于第一种我们称为直接贡献，第二种我们称为附加贡献）

我们考虑对 $a$ 进行分块，对上面内容用在整块和零散块中间，先考虑零散块部分：显然它对零散块可以直接暴力求附加贡献。（见代码“（0）”部分）

剩下考虑零散块修改对整块询问的贡献：修改时显然零散块对整块只有附加贡献。设它和一个整块的交的大小是 $x$，那这次操作对 $a_{l\sim r}$ 的附加贡献和是 $x\times v$，用 $tag_1$ 记录，之后询问遇到这个块的时候直接贡献加上 $tag_1$。（见代码“（1）”部分）

考虑整块修改对询问的贡献：修改时，整个块打上标记 $tag_2$（这里是直接贡献）。询问时，求两者的交的大小 $x$，询问时贡献 $tag_2\times x$ 同上。这里不用区分询问的是直接、附加贡献、零散块、整块，几者都被包含。（见代码“（2）”部分）

时间复杂度 $O(m\sqrt{m}+q\sqrt{m})$，空间复杂度 $O(n+m+q)$。

代码实现

#include<bits/stdc++.h>
#define int unsigned int
#define ull unsigned long long 
using namespace std;
constexpr int N=2e5+1,blen=666;
int n,m,q,a[N<<1],len,bl[N<<1],btot,appear[N],inter[N<<1];
ull w[N];
vector<int>e[N];
pair<int,int>pos[N];
struct Block{
    int l,r;
    ull tag1,tag2;
    Block(int l=0,int r=0):l(l),r(r),tag1(0),tag2(0){}
}block[blen];
struct Query{
    int op,l,r,val;
    ull ans;
    Query():ans(0){}
    Query(int op,int l,int r):op(op),l(l),r(r),val(0),ans(0){}
    Query(int op,int l,int r,int val):op(op),l(l),r(r),val(val),ans(0){}
}query[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m>>q;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        e[u].push_back(v),e[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        pos[i].first=len+1;
        for(auto p:e[i])
            a[++len]=p;
        pos[i].second=len;
    }
    for(int i=1;i<=len;i++)
        bl[i]=(i-1)/blen+1;
    btot=bl[len];
    for(int i=1;i<=btot;i++)
        block[i]=Block(block[i-1].r+1,min(block[i-1].r+blen,len));
    for(int i=1,op,l,r,v;i<=q;i++){
        cin>>op>>l>>r;
        if(op==1){
            cin>>v;
            query[i]=Query(op,pos[l].first,pos[r].second,v);
        }
        else
            query[i]=Query(op,pos[l].first,pos[r].second);
    }
    for(int i=1;i<=q;i++){
    	if(query[i].l>query[i].r)
    		continue;
        if(query[i].op==1){
            if(bl[query[i].l]==bl[query[i].r]){
                for(int j=query[i].l;j<=query[i].r;j++)
                    w[a[j]]+=query[i].val;
            }
            else{
                for(int j=query[i].l;j<=block[bl[query[i].l]].r;j++)
                    w[a[j]]+=query[i].val;
                for(int j=block[bl[query[i].r]].l;j<=query[i].r;j++)
                    w[a[j]]+=query[i].val;
            }
        }//暴力零散块修改（0）
        else{
            if(bl[query[i].l]==bl[query[i].r]){
                for(int j=query[i].l;j<=query[i].r;j++)
                    query[i].ans+=w[a[j]];
            }
            else{
                for(int j=query[i].l;j<=block[bl[query[i].l]].r;j++)
                    query[i].ans+=w[a[j]];
                for(int j=block[bl[query[i].r]].l;j<=query[i].r;j++)
                    query[i].ans+=w[a[j]];
            }
        }//暴力零散块查询（0）
    }
    for(int i=1;i<=btot;i++){
        for(int j=block[i].l;j<=block[i].r;j++)
            appear[a[j]]++;
        for(int j=1;j<=len;j++)
            inter[j]=inter[j-1]+appear[a[j]];//前缀和求交
        for(int j=1;j<=q;j++){
			if(query[j].l>query[j].r)
				continue;
            if(query[j].op==1){
                if(bl[query[j].l]==bl[query[j].r])
                    block[i].tag1+=1ull*query[j].val*(inter[query[j].r]-inter[query[j].l-1]);//零散块修改（1）
                else{
                    block[i].tag1+=1ull*query[j].val*(inter[block[bl[query[j].l]].r]-inter[query[j].l-1]),
                    block[i].tag1+=1ull*query[j].val*(inter[query[j].r]-inter[block[bl[query[j].r]].l-1]);//零散块修改（1）
                    if(query[j].l<block[i].l&&block[i].r<query[j].r)
                        block[i].tag2+=query[j].val;//整块修改（2）
                }
            }
            else{
            	query[j].ans+=block[i].tag2*(inter[query[j].r]-inter[query[j].l-1]);//询问贡献（2）
                if(query[j].l<block[i].l&&block[i].r<query[j].r)
                    query[j].ans+=block[i].tag1;//询问整块的贡献（1）
            }
        }
        for(int j=block[i].l;j<=block[i].r;j++)
            appear[a[j]]--;
    }
    for(int i=1;i<=q;i++)
        if(query[i].op==2)
            cout<<query[i].ans<<'\n';
    return 0;
}