wa10pts求条 动态开点线段树

#include<bits/stdc++.h>
#define int unsigned long long 
using namespace std;
const int N=1e5+5;
int n,m,ls[N*120],rs[N*120],tot,s[N*120],lz[N*120],rt;
void pd(int u,int l,int r,int mid){
	if(!lz[u])return;
	if(!ls[u])ls[u]=++tot;
	if(!rs[u])rs[u]=++tot;
	s[ls[u]]+=(mid-l+1)*lz[u],lz[ls[u]]+=lz[u];
	s[rs[u]]+=(r-mid)*lz[u],lz[rs[u]]+=lz[u];
	lz[u]=0;
}
void mdy(int &u,int l,int r,int k,int lc,int rc){
	if(rc<l||r<lc)return;
	if(!u)u=++tot;
	if(l<=lc&&rc<=r){
		s[u]+=(rc-lc+1)*k,lz[u]+=k;
		return;
	}
	int mid=(lc+rc)>>1;
	pd(u,lc,rc,mid);
	mdy(ls[u],l,r,k,lc,mid);
	mdy(rs[u],l,r,k,mid+1,rc);
	s[u]+=s[ls[u]]+s[rs[u]];
}
int que(int u,int l,int r,int lc,int rc){
	if(rc<l||lc>r)return 0;
	if(l<=lc&&rc<=r)return s[u];
	int mid=(lc+rc)>>1;
	pd(u,lc,rc,mid);
	return que(ls[u],l,r,lc,mid)+que(rs[u],l,r,mid+1,rc);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int opt,l,r,k;m;m--){
		cin>>opt>>l>>r;
		if(opt==1){
			cin>>k;
			mdy(rt,l,r,k,1,n);
		}
		else cout<<(l+r)*(r-l+1)/2+que(rt,l,r,1,n)<<"\n";
	}
	return 0;
}