可以说是数据结构学傻了的典型案例了
昨天跳到这题上
然后思考了一下
噫！好！线段树裸题
然后打完板子，发现\( n \le 10^9 \)
显然线段树直接做不太行
然后这题又只有普及的难度
然后我就打了神奇的动态开点线段树水过
qwq
之后看题解发现正解是\( O(m^2) \)的暴力
因为常数小跑的更快啊qwq
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int cnt=,tr[<<],tag[<<],lx[<<],rx[<<],n,m,root=;
void pushup(int o){
tr[o]=tr[lx[o]]+tr[rx[o]];
}
void pushdown(int o,int ln,int rn){
if(!lx[o])
lx[o]=++cnt;
if(!rx[o])
rx[o]=++cnt;
if(tag[o]){
tag[lx[o]]+=tag[o];
tag[rx[o]]+=tag[o];
tr[lx[o]]+=tag[o]*ln;
tr[rx[o]]+=tag[o]*rn;
tag[o]=;
}
}
void update(int L,int R,int l,int r,int& o,int c){
if(!o)
o=++cnt;
if(L<=l&&r<=R){
tr[o]+=c*(r-l+);
tag[o]+=c;
return;
}
int mid=(l+r)>>;
pushdown(o,mid-l+,r-mid);
if(L<=mid){
update(L,R,l,mid,lx[o],c);
}
if(R>mid){
update(L,R,mid+,r,rx[o],c);
}
pushup(o);
}
int query(int L,int R,int l,int r,int &o){
if(!o)
o=++cnt;
if(L<=l&&r<=R){
return tr[o];
}
int ans=,mid=(l+r)>>;
pushdown(o,mid-l+,r-mid);
if(L<=mid){
ans+=query(L,R,l,mid,lx[o]);
}
if(R>mid)
ans+=query(L,R,mid+,r,rx[o]);
return ans;
}
void debug(int l,int r,int o){
if(!o)
return;
printf("o=%d l=%d r=%d tag=%d num=%d lx=%d rx=%d\n",o,l,r,tag[o],tr[o],lx[o],rx[o]);
if(l==r)
return;
int mid=(l+r)>>;
debug(l,mid,lx[o]);
debug(mid+,r,rx[o]);
}
signed main(){
scanf("%lld %lld",&n,&m);
for(int i=;i<=m;i++){
int opt;
scanf("%lld",&opt);
if(opt==){
int l,r,k;
scanf("%lld %lld %lld",&l,&r,&k);
update(l,r,,n,root,k);
// debug(1,n,root);
}
else{
int l,r;
scanf("%lld %lld",&l,&r);
printf("%lld\n",query(l,r,,n,root) );
}
}
return ;
}