题解：P12461 [Ynoi Easy Round 2018] 星野爱

· · 题解

Solution

纯套路题。

看到数据范围联想到分块。而这种东西想暴力做一个区间复杂度是 O(\sum \deg)，所以考虑按照 \deg 带权分块，这样可以暴力做一个散块。

注意我们要删掉所有零度点。不然直接这么做复杂度会爆掉（也可以按照 \deg + 1 分块这样就没问题了）。

我们把问题按照询问是否是散块、查询是否是散块分成 4 种情况。

  1. 散块修改，散块查询。全部暴力就行。
  2. 散块修改，整块查询。对于每一块，计算修改一个点对整个块产生的贡献（很可以直接记下来空间会爆，所以只能对每个块做一遍）。
  3. 整块修改，散块查询。计算修改一个块对一个点产生的贡献（很容易发现和上面那个本质相同，可以节省一些运算量）。
  4. 整块修改，整块查询。在计算出一个块对一个点的贡献之后对每个块做一遍前缀和即可。

复杂度为 O(m \sqrt m)，足以通过本题。

这种带权分块要注意，普通分块题目会把左右两端都当成散块（哪怕他们实际上是一个整块，并不影响复杂度）。而带权分块必须把他们当成整块，不然会被某个点极大的情况卡掉。

#include<bits/stdc++.h>
#define ull unsigned long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10,B=1500;
int n,m,k,q,tot,op[MAXN],l[MAXN],r[MAXN],rnk[MAXN];
int ex[MAXN],ey[MAXN];
vector<int> g[MAXN],G[MAXN];
int L[MAXN],R[MAXN],bel[MAXN];

ull val[MAXN],ad[MAXN],EF[MAXN],ef[MAXN],pre[MAXN];

int sp[MAXN],to[MAXN*2],deg[MAXN];
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    ffor(i,1,m) {int u,v;cin>>u>>v,ex[i]=u,ey[i]=v,g[u].push_back(v),g[v].push_back(u);}
    ffor(i,1,n) if(!g[i].empty()) rnk[i]=++tot;
    else rnk[i]=rnk[i-1];

    ffor(i,1,m) {
        int u=rnk[ex[i]],v=rnk[ey[i]];
        G[u].push_back(v),G[v].push_back(u);    
    }

    int mt=0;
    ffor(i,1,n) {sp[i]=mt+1;for(auto v:G[i]) deg[i]++,to[++mt]=v;}

    ffor(i,1,q) {
        cin>>op[i]>>l[i]>>r[i];
        if(op[i]==1) cin>>val[i];
        l[i]=rnk[l[i]-1]+1;
        r[i]=rnk[r[i]];
    }
    int lst=1,tmp=0;
    n=tot;
    ffor(i,1,n+1) {
        tmp+=deg[i];
        if(tmp>=B||i==n+1) {
            if(lst<=i-1) ++k,L[k]=lst,R[k]=i-1;
            lst=i,tmp=deg[i];
        }
    }
    ffor(i,1,k) ffor(j,L[i],R[i]) bel[j]=i;
    ffor(i,1,q) if(l[i]<=r[i]) {
        if(op[i]==1) {
            if(bel[l[i]]==bel[r[i]]&&(l[i]!=L[bel[l[i]]]||r[i]!=R[bel[r[i]]])) ffor(u,l[i],r[i]) for(int e=sp[u],v=to[e];e<=sp[u]+deg[u]-1;e++,v=to[e]) ad[v]+=val[i];
            else {
                if(l[i]!=L[bel[l[i]]]) ffor(u,l[i],R[bel[l[i]]]) for(int e=sp[u],v=to[e];e<=sp[u]+deg[u]-1;e++,v=to[e]) ad[v]+=val[i];
                if(r[i]!=R[bel[r[i]]]) ffor(u,L[bel[r[i]]],r[i]) for(int e=sp[u],v=to[e];e<=sp[u]+deg[u]-1;e++,v=to[e]) ad[v]+=val[i];
            }
        }
        else {
            if(bel[l[i]]==bel[r[i]]&&(l[i]!=L[bel[l[i]]]||r[i]!=R[bel[r[i]]])) ffor(u,l[i],r[i]) for(int e=sp[u],v=to[e];e<=sp[u]+deg[u]-1;e++,v=to[e]) val[i]+=ad[v];
            if(bel[l[i]]!=bel[r[i]]) {
                if(l[i]!=L[bel[l[i]]]) ffor(u,l[i],R[bel[l[i]]]) for(int e=sp[u],v=to[e];e<=sp[u]+deg[u]-1;e++,v=to[e]) val[i]+=ad[v];
                if(r[i]!=R[bel[r[i]]]) ffor(u,L[bel[r[i]]],r[i]) for(int e=sp[u],v=to[e];e<=sp[u]+deg[u]-1;e++,v=to[e]) val[i]+=ad[v];
            }
        }
    }
    ffor(id,1,k) {
        memset(EF,0,sizeof(EF)),memset(ef,0,sizeof(ef));
        ffor(u,L[id],R[id]) for(int e=sp[u],v=to[e];e<=sp[u]+deg[u]-1;e++,v=to[e]) EF[v]++;
        ffor(u,1,n) for(int e=sp[u],v=to[e];e<=sp[u]+deg[u]-1;e++,v=to[e]) ef[u]+=EF[v];
        ffor(i,1,n) pre[i]=pre[i-1]+ef[i]; 
        ull zad=0,sad=0;
        ffor(i,1,q) if(l[i]<=r[i]) {
            if(op[i]==1) {              
                sad+=(pre[r[i]]-pre[l[i]-1])*val[i];
                if(l[i]<=L[id]&&R[id]<=r[i]) zad+=val[i];
            }
            else {
                if(l[i]<=L[id]&&R[id]<=r[i]) val[i]+=sad;
                if(bel[l[i]]==bel[r[i]]&&(l[i]!=L[bel[l[i]]]||r[i]!=R[bel[r[i]]])) val[i]+=zad*(pre[r[i]]-pre[l[i]-1]);
                if(bel[l[i]]!=bel[r[i]]) {
                    if(l[i]!=L[bel[l[i]]]) val[i]+=zad*(pre[R[bel[l[i]]]]-pre[l[i]-1]);
                    if(r[i]!=R[bel[r[i]]]) val[i]+=zad*(pre[r[i]]-pre[L[bel[r[i]]]-1]);
                }
            }
        }
    }

    ffor(i,1,q) if(op[i]==2) cout<<val[i]<<'\n';
    return 0;
}