太菜了，咕一会儿。
星野爱给了你一张无向图
每个节点有权值
1,l,r,v，对于， ，令 2,l,r，计算。
输出的值请对
能想到把这张图片放到这道题的背景和写出这道题的人都是神人了。1
带权分块。
更具体地，给出一个动态数组
- 初始，
，枚举点 。 - 若
则 。 - 将
加入到 末尾。
很厉害。
因为有
...
cpp
#define rg for(reg int e=head[u],v=nxt[e];e<head[u]+deg[u];++e,v=nxt[e])
#define N (200010)
#define B 1500
struct OP{int op,l,r;ull val,ans;}r[N];
int n,m,q,rx[N],ry[N],rk[N],in[N],tot,deg[N],head[N],nxt[N<<1],L[N],R[N],k,rev[N];
ull ad[N],sum[N],num[N];
vector<int>e[N];
signed main(){
io.read(n);io.read(m);io.read(q);
// Input graph
rep(i,1,m)io.read(rx[i]),io.read(ry[i]),in[rx[i]]++,in[ry[i]]++;
// Del useless node
rep(i,1,n)if(!in[i])rk[i]=rk[i-1];else rk[i]=++tot;
// Dev graph
rep(i,1,m)e[rk[rx[i]]].pb(rk[ry[i]]),e[rk[ry[i]]].pb(rk[rx[i]]);
// Add all into a line
reg int TMPcnt=0;
rep(i,1,n){
head[i]=TMPcnt+1;
for(auto to:e[i])deg[i]++,nxt[++TMPcnt]=to;
}
// operator
rep(i,1,q){
io.read(r[i].op),io.read(r[i].l),io.read(r[i].r);
if(r[i].op==1)io.read(r[i].val);
r[i].l=rk[r[i].l-1]+1;
r[i].r=rk[r[i].r];
}
// sqrt
n=tot;
reg int last=1,tmp=0;
rep(i,1,n+1)if((tmp+=deg[i])>=B||i>n)++k,L[k]=last,R[k]=i-1,last=i,tmp=deg[i];
rep(id,1,k)rep(i,L[id],R[id])rev[i]=id;
// solve
// --single one--
rep(i,1,q)if(r[i].l<=r[i].r){
if(r[i].op==1){ //change
if(rev[r[i].l]==rev[r[i].r]&&(r[i].l!=L[rev[r[i].l]]||r[i].r!=R[rev[r[i].r]])){
rep(u,r[i].l,r[i].r)rg ad[v]+=r[i].val;
}else{
if(r[i].l!=L[rev[r[i].l]])rep(u,r[i].l,R[rev[r[i].l]])rg ad[v]+=r[i].val;
if(r[i].r!=R[rev[r[i].r]])rep(u,L[rev[r[i].r]],r[i].r)rg ad[v]+=r[i].val;
}
}else{ //query
if(rev[r[i].l]==rev[r[i].r]&&(r[i].l!=L[rev[r[i].l]]||r[i].r!=R[rev[r[i].r]])){
rep(u,r[i].l,r[i].r)rg r[i].ans+=ad[v];
}
if(rev[r[i].l]!=rev[r[i].r]){
if(r[i].l!=L[rev[r[i].l]])rep(u,r[i].l,R[rev[r[i].l]])rg r[i].ans+=ad[v];
if(r[i].r!=R[rev[r[i].r]])rep(u,L[rev[r[i].r]],r[i].r)rg r[i].ans+=ad[v];
}
}
}
// ---full one---
rep(id,1,k){
memset(sum,0,sizeof sum);memset(num,0,sizeof num);
rep(u,L[id],R[id])rg num[v]++;
rep(u,1,n){rg sum[u]+=num[v];sum[u]+=sum[u-1];};
ull sgl=0,ful=0;
rep(i,1,q)if(r[i].l<=r[i].r){
if(r[i].op==1){
ful+=r[i].val*(sum[r[i].r]-sum[r[i].l-1]);
if(r[i].l<=L[id]&&R[id]<=r[i].r)sgl+=r[i].val;
}else{
if(r[i].l<=L[id]&&R[id]<=r[i].r)r[i].ans+=ful; //贡献给整块查询
if(rev[r[i].l]==rev[r[i].r]&&(r[i].l!=L[rev[r[i].l]]||r[i].r!=R[rev[r[i].r]]))
r[i].ans+=sgl*(sum[r[i].r]-sum[r[i].l-1]);
if(rev[r[i].l]!=rev[r[i].r]){
if(r[i].l!=L[rev[r[i].l]])r[i].ans+=sgl*(sum[R[rev[r[i].l]]]-sum[r[i].l-1]);
if(r[i].r!=R[rev[r[i].r]])r[i].ans+=sgl*(sum[r[i].r]-sum[L[rev[r[i].r]]-1]);
}
}
}
}
rep(i,1,q)if(r[i].op==2)io.write(r[i].ans,'\n');
return 0;
}Ynoi Easy Round 2018 星野爱https://blog.acerkaio.top/posts/2025/%E6%98%9F%E9%87%8E%E7%88%B1