题解：P12461 [Ynoi Easy Round 2018] 星野爱
鲤鱼江
·
·
题解
把图拍扁成一个长为 2m 的序列 a_{1\dots 2m}，一个节点 i 管辖的区间是 [L_i,R_i]，问题即可转化为：
操作一：\forall i\in[L_l,R_r],w_{a_i}\gets w_{a_i}+v。
操作二：求 \sum\limits_{i=L_l}^{R_r} w_{a_i}。
套路地，我们对度数考虑根号处理，本题采用带权分块，将节点编号按照 deg 分块使得每一块都度数和都 \le B，deg_x>B 的 x 单独分一块，注意去掉零度点否则复杂度会爆炸，不过你按 deg+1 分块就没这个烦恼了。
然后和常规分块还有一个差别就是如果一个块被完全包含就直接将其看作整块，不像普通分块默认把边角块当作散的。
思考修改对询问的贡献：
- 散块对散块，直接暴力。
- 整块对区间，存 f_{i,j} 表示第 i 个块修改对前 j 个点的贡献。
- 散块对整块：跟整块对散块本质相同。
```cpp
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
#include<bits/stdc++.h>
using namespace std;
namespace Fread {
const int SIZE=1<<21;char buf[SIZE],*S,*T;
inline char getchar() {if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return '\n';}return *S++;}
}
namespace Fwrite {
const int SIZE=1<<21;
char buf[SIZE],*S=buf,*T=buf+SIZE;
inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}
inline void putchar(char c){*S++=c;if(S==T)flush();}
struct POPOSSIBLE{~POPOSSIBLE(){flush();}}ztr;
}
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
namespace Fastio{
struct Reader{
template<typename T>
Reader& operator >> (T& x) {
char c=getchar();T f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}x=0;
while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}x*=f;
return *this;
}
Reader(){}
}cin;
struct Writer{
template<typename T>
Writer& operator << (T x) {
if(x==0){putchar('0');return *this;}
if(x<0){putchar('-');x=-x;}
static int sta[45];int top=0;
while(x){sta[++top]=x%10;x/=10;}
while(top){putchar(sta[top]+'0');--top;}
return *this;
}
Writer& operator << (char c) {putchar(c);return *this;}
Writer(){}
}cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
const int N=4e5+10;
struct Query{
int op,l,r,v,zl,zr;
Query(int op=0,int l=0,int r=0,int v=0):
op(op),l(l),r(r),v(v){;}
}q[N];
int n,m,Q,lenth,pos[N],lpos[N],rpos[N],tot,ct[N],a[N],L[N],R[N],cnt;
vector < int > v[N];ll ans[N],val[N],f[N],w,now,VAL;
inline void add(int x,int y){v[x].emplace_back(y);v[y].emplace_back(x);}
inline void SetBlock(int l,int r){
// cout << tot+1 << ' ' << l << ' ' << r << "--\n";
++tot;for(int i=l;i<=r;++i) pos[i]=tot;
lpos[tot]=l;rpos[tot]=r;
}
inline void Corner(int id){//处理散块
int op=q[id].op,l=q[id].l,r=q[id].r,vl=q[id].v;
int st=pos[l],ed=pos[r];
// cout << st << ' ' << ed << ' ' << l << ' ' << r << "\n";
q[id].zl=st+(l!=lpos[st]);
q[id].zr=ed-(r!=rpos[ed]);
// cout<<"GCX,are you ok? "<<id<<' '<<q[id].zl<<' '<<q[id].zr<<'\n';
if(l==lpos[st]&&r==rpos[ed]) return ;
if(op==1){
if(st==ed){
for(int i=l;i<=r;++i) for(int j:v[i]) val[j]+=vl;
}else {
if(l!=lpos[st]) for(int i=l;i<=rpos[st];++i) for(int j:v[i]) val[j]+=vl;
if(r!=rpos[ed]) for(int i=lpos[ed];i<=r;++i) for(int j:v[i]) val[j]+=vl;
}
}else {
if(st==ed){
for(int i=l;i<=r;++i) for(int j:v[i]) ans[id]+=val[j];
}else {
if(l!=lpos[st]) for(int i=l;i<=rpos[st];++i) for(int j:v[i]) ans[id]+=val[j];
if(r!=rpos[ed]) for(int i=lpos[ed];i<=r;++i) for(int j:v[i]) ans[id]+=val[j];
}
// cout << ans[id] << "---\n";
}
}
inline void init(int id){
for(int j=L[lpos[id]];j<=R[rpos[id]];++j) ++ct[a[j]];
for(int i=1;i<=n;++i){
for(int j=L[i];j<=R[i];++j) f[i]+=ct[a[j]];
f[i]+=f[i-1];
}
}
inline void clear(){VAL=w=0;for(int i=1;i<=n;++i) ct[i]=f[i]=val[i]=0;}
inline void Solve1(int p){//整块对区间
int op=q[p].op,l=q[p].l,r=q[p].r,v=q[p].v;
if(op==1)(l<=lpos[now]&&rpos[now]<=r)&&(w+=v);
else ans[p]+=(f[r]-f[l-1])*w;
}
inline void Solve2(int p){//散块对整块
int op=q[p].op,l=q[p].l,r=q[p].r,v=q[p].v;
if(op==1){
if(q[p].zl<=q[p].zr){
int sl=l,sr=rpos[q[p].zl-1];VAL+=(f[sr]-f[sl-1])*v;
sl=lpos[q[p].zr+1];sr=r;VAL+=(f[sr]-f[sl-1])*v;
}else VAL+=(f[r]-f[l-1])*v;
}else (l<=lpos[now]&&rpos[now]<=r)&&(ans[p]+=VAL);
}
inline void Deal(int id){for(int i=1;i<=Q;++i){Solve1(i);Solve2(i);}}
signed main(){
cin>>n>>m>>Q;for(int i=1,x,y;i<=m;++i){cin>>x>>y;add(x,y);}
for(int i=1;i<=Q;++i){
cin>>q[i].op>>q[i].l>>q[i].r;
if(q[i].op==1) cin>>q[i].v;
}
for(int i=1;i<=n;++i){
L[i]=cnt+1;
for(int j:v[i]) a[++cnt]=j;
R[i]=cnt;
}
lenth=sqrt(3*m)*1.5;int s=0,las=1;
for(int i=1;i<=n;++i){//带权分块
int sz=v[i].size()+1;
if(s+sz>lenth){
s=0;
if(las==i) SetBlock(i,i),las=i+1;
else {SetBlock(las,i-1);las=i;--i;continue;}
}else s+=sz;
}
if(las<=n) SetBlock(las,n);
lpos[tot+1]=n+1;for(int i=1;i<=Q;++i) Corner(i);
for(int i=1;i<=tot;++i){now=i;init(i);Deal(i);clear();}
for(int i=1;i<=Q;++i) if(q[i].op==2) cout<<ans[i]<<'\n';
return 0;
}
```