[Ynoi Easy Round 2018] 星野爱

_H17_ · 2025-05-11 10:16:04 · 题解

前言

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

题目分析

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

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

题目就可以转化为：

对于 i\in[L_l,R_r]，w_{a_i}\gets w_{a_i}+v；
求 \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;
}