kangkang0201 @ 2023-08-21 00:02:51
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define ll long long
unsigned ll a[MAXN];
struct node
{
int l,r;
ll lazy;
ll sum;
}tr[MAXN<<2|4];
//整合
inline void pushup(int u)
{
tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}
void buildtree(int u , int l , int r)
{
tr[u].l = l;
tr[u].r = r;
if(l == r)
{
tr[u].sum = a[l];
return;
}
int mid = (l + r) >> 1;
buildtree(u<<1,l,mid);
buildtree(u<<1|1,mid+1,r);
pushup(u);
}
//如果查询的节点在之前放置的懒标记之下
inline void pushdown(int u)
{
if(tr[u].lazy)
{
tr[u<<1].lazy = tr[u].lazy;
tr[u<<1].sum += (tr[u<<1].r - tr[u<<1].l + 1)*tr[u].lazy;
tr[u<<1|1].lazy = tr[u].lazy;
tr[u<<1|1].sum += (tr[u<<1|1].r -tr[u<<1|1].l + 1)*tr[u].lazy;
tr[u].lazy = 0;
}
}
inline void modify(int u ,int l ,int r, ll k)
{
if(l<= tr[u].l && r >= tr[u].r)
{
tr[u].lazy += k;
tr[u].sum +=(tr[u].r - tr[u].l + 1) * k;
return;
}
//先把懒标记更新下去
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid)
{
modify(u<<1,l,mid,k);
}
if(r > mid)
{
modify(u<<1|1,mid+1,r,k);
}
pushup(u);
}
ll query(int u ,int l ,int r)
{
if(l <= tr[u].l && r>=tr[u].r)
{
return tr[u].sum;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >>1;
ll res = 0;
if(l <= mid) res+= query(u<<1 , l, r);
if(r > mid) res+= query(u<<1|1, l, r);
return res;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
for(int i = 1 ; i <= n ; i++)
{
cin>>a[i];
}
buildtree(1,1,n);
for(int i = 0 ; i < m ;i++)
{
int stra;
cin>>stra;
if(stra == 1)
{
int l, r;
ll k;
cin>>l>>r>>k;
modify(1,l,r,k);
}
else
{
int l,r;
cin>>l>>r;
ll answer = query(1,l,r);
printf("%lld\n",answer);
}
}
return 0;
}
by DGME @ 2023-08-21 02:12:26