```cpp
#include<cstdio>
#define isdigit(c) (c>='0'&&c<='9')
#define lc(x) e[x].lch
#define rc(x) e[x].rch
using namespace std;
typedef long long ll;
const ll MAXN=1e5+50;
void read(ll &x){
x=0;char c=getchar();int f=1;
while(!isdigit(c)){
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
x*=f;
}
struct Treap{
ll val,size,key,lch,rch,add,sum;
}e[MAXN];
ll cnt=0,root=0,seed=233;
ll get_key(){
return seed=seed*19260817%998244353;
}
ll newnode(ll val){
e[++cnt].val=val;
e[cnt].size=1;
e[cnt].key=get_key();
e[cnt].sum=val;
lc(cnt)=rc(cnt)=e[cnt].add=0;
return cnt;
}
void update(ll x){
e[x].size=e[lc(x)].size+e[rc(x)].size+1;
e[x].sum=e[lc(x)].sum+e[rc(x)].sum+e[x].val;
}
void part_add(ll now,ll val){
e[now].val+=val;
e[now].add+=val;
update(now);
e[now].sum+=(e[now].size)*val;
}
void pushdown(ll now){
if(!e[now].add) return;
if(lc(now)) part_add(lc(now),e[now].add);
if(rc(now)) part_add(rc(now),e[now].add);
e[now].add=0;
}
void split(ll now,ll &a,ll &b,ll size){
if(now==0){
a=b=0;
return;
}
pushdown(now);
if(e[lc(now)].size>=size){
split(lc(now),a,b,size);
lc(now)=b;
update(now);
b=now;
}else{
split(rc(now),a,b,size-(e[lc(now)].size+1));
rc(now)=a;
update(now);
a=now;
}
}
void merge(ll &now,ll a,ll b){
if(a==0||b==0){
now=a+b;
return;
}
if(e[a].key<e[b].key){
pushdown(a);
now=a;
merge(rc(now),rc(a),b);
}else{
pushdown(b);
now=b;
merge(lc(now),a,lc(b));
}
update(now);
}
void add(ll l,ll r,ll val){
ll x,y,z;
split(root,x,y,l-1);
split(y,y,z,r-l+1);
part_add(y,val);
merge(y,y,z);
merge(root,x,y);
}
void insert(ll val){
ll x=newnode(val);
merge(root,root,x);
update(root);
}
ll get_sum(ll l,ll r){
ll x,y,z;
split(root,x,y,l-1);
split(y,y,z,r-l+1);
ll ans=e[y].sum;
merge(y,y,z);
merge(root,x,y);
return ans;
}
int main(){
ll n,m;
read(n),read(m);
ll opt,x,y,k;
for(ll i=1;i<=n;++i){
read(x);
insert(x);
}
for(ll i=1;i<=m;++i){
read(opt);
if(opt==1){
read(x),read(y),read(k);
add(x,y,k);
}else{
read(x),read(y);
printf("%lld\n",get_sum(x,y));
}
}
return 0;
}
```
by enor2017 @ 2019-01-23 08:03:04