样例一:
IN:
```
8 10
640 591 141 307 942 58 775 133
2 1 5
2 3 8
2 3 6
2 5 8
2 4 8
1 4 8 60
2 1 6
2 5 8
1 3 7 15
1 2 6 86
```
OUT:
```
2621
2356
1448
1908
2215
2859
2148
```
MYOUT
```
2621
2356
1448
1908
1908
2799
2148
```
by lijunxi1 @ 2023-10-04 21:03:12
```
#include<bits/stdc++.h>
using namespace std;
int n,m,zl,x,y,k;
long long xds[400005],a[400005],lb[400005];
long long js(int l,int r,int w)
{
if(l==r)return xds[w]=a[l];
int mid=(l+r)/2;
return xds[w]=js(l,mid,w*2)+js(mid+1,r,w*2+1);
}
long long cz(int l,int r,int ml,int mr,int w)
{
//cout<<l<<" "<<r<<" "<<ml<<" "<<mr<<"\n";
if(l==r)
{
if(l>=ml&&r<=mr)
{
xds[w]+=lb[w];
lb[w]=0;
return xds[w];
}
else return xds[w];
}
int mid=(l+r)/2;
long long ans=0;
lb[w*2]+=lb[w];
lb[w*2+1]+=lb[w];
xds[w]+=lb[w]*(r-l+1);
lb[w]=0;
if(l>=ml&&r<=mr)return xds[w];
if((mid>=ml&&mid<=mr)||(l>=ml&&l<=mr))ans+=cz(l,mid,ml,mr,w*2);
if((mid+1>=ml&&mid+1<=mr)||(r>=ml&&r<=mr))ans+=cz(mid+1,r,ml,mr,w*2+1);
return ans;
}
void zj(int l,int r,int ml,int mr,int w,int k)
{
if(l==r)
{
if(l>=ml&&l<=mr)
{
lb[w]+=k;
}
return;
}
int mid=(l+r)/2;
long long ans=0;
lb[w*2]+=lb[w];
lb[w*2+1]+=lb[w];
xds[w]+=lb[w]*(r-l+1);
if(l<=ml&&r>=mr)xds[w]+=k*(mr-ml+1);
else if(l<=ml&&r<=mr)xds[w]+=min(0,r-ml+1)*k;
else if(l>=ml&&r>=mr)xds[w]+=min(0,mr-l+1)*k;
else xds[w]+=(r-l+1)*k;
lb[w]=0;
if(l>=ml&&r<=mr)
{
lb[w]=k;
return;
}
if((mid>=ml&&mid<=mr)||(l>=ml&&l<=mr))zj(l,mid,ml,mr,w*2,k);
if((mid+1>=ml&&mid+1<=mr)||(r>=ml&&r<=mr))zj(mid+1,r,ml,mr,w*2+1,k);
return;
}
int main ()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
js(1,n,1);
while(m--)
{
cin>>zl>>x>>y;
if(zl==1)
{
cin>>k;
zj(1,n,x,y,1,k);
}
else cout<<cz(1,n,x,y,1)<<"\n";
}
}
```
又改了一点点
by lijunxi1 @ 2023-10-04 21:20:26
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,zl,x,y,k;
long long xds[400005],a[400005],lb[400005];
long long js(int l,int r,int w)
{
if(l==r)return xds[w]=a[l];
int mid=(l+r)/2;
return xds[w]=js(l,mid,w*2)+js(mid+1,r,w*2+1);
}
long long cz(int l,int r,int ml,int mr,int w)
{
if(l==r)
{
xds[w]+=lb[w];
lb[w]=0;
return xds[w];
}
int mid=(l+r)/2;
long long ans=0;
lb[w*2]+=lb[w];
lb[w*2+1]+=lb[w];
xds[w]+=lb[w]*(r-l+1);
lb[w]=0;
if(l>=ml&&r<=mr)return xds[w];
if((mid>=ml&&mid<=mr)||(l>=ml&&l<=mr))ans+=cz(l,mid,ml,mr,w*2);
if((mid+1>=ml&&mid+1<=mr)||(r>=ml&&r<=mr))ans+=cz(mid+1,r,ml,mr,w*2+1);
return ans;
}
void zj(int l,int r,int ml,int mr,int w,int k)
{
if(l==r)
{
if(l>=ml&&l<=mr)
{
lb[w]+=k;
}
return;
}
int mid=(l+r)/2;
long long ans=0;
lb[w*2]+=lb[w];
lb[w*2+1]+=lb[w];
xds[w]+=lb[w]*(r-l+1);
lb[w]=0;
if(l<=ml&&r>=mr)xds[w]+=k*(mr-ml+1);
else if(l<=ml&&r<=mr)xds[w]+=max(0,r-ml+1)*k;
else if(l>=ml&&r>=mr)xds[w]+=max(0,mr-l+1)*k;
else xds[w]+=(r-l+1)*k;
if(l>=ml&&r<=mr)
{
lb[w]=k;
return;
}
if((mid>=ml&&mid<=mr)||(l>=ml&&l<=mr))zj(l,mid,ml,mr,w*2,k);
if((mid+1>=ml&&mid+1<=mr)||(r>=ml&&r<=mr))zj(mid+1,r,ml,mr,w*2+1,k);
return;
}
int main ()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
js(1,n,1);
while(m--)
{
cin>>zl>>x>>y;
if(zl==1)
{
cin>>k;
zj(1,n,x,y,1,k);
}
else cout<<cz(1,n,x,y,1)<<"\n";
}
}
```
by lijunxi1 @ 2023-10-04 21:46:44
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,zl,x,y,k;
long long xds[400005],a[400005],lb[400005];
long long js(int l,int r,int w)
{
if(l==r)return xds[w]=a[l];
int mid=(l+r)/2;
return xds[w]=js(l,mid,w*2)+js(mid+1,r,w*2+1);
}
long long cz(int l,int r,int ml,int mr,int w)
{
if(l==r)
{
xds[w]+=lb[w];
lb[w]=0;
return xds[w];
}
int mid=(l+r)/2;
long long ans=0;
lb[w*2]+=lb[w];
lb[w*2+1]+=lb[w];
xds[w]+=lb[w]*(r-l+1);
lb[w]=0;
if(l>=ml&&r<=mr)return xds[w];
if((mid>=ml&&mid<=mr)||(l>=ml&&l<=mr))ans+=cz(l,mid,ml,mr,w*2);
if((mid+1>=ml&&mid+1<=mr)||(r>=ml&&r<=mr))ans+=cz(mid+1,r,ml,mr,w*2+1);
return ans;
}
void zj(int l,int r,int ml,int mr,int w,int k)
{
if(l==r)
{
if(l>=ml&&l<=mr)
{
lb[w]+=k;
}
return;
}
int mid=(l+r)/2;
long long ans=0;
lb[w*2]+=lb[w];
lb[w*2+1]+=lb[w];
xds[w]+=lb[w]*(r-l+1);
lb[w]=0;
if(l<=ml&&r>=mr)xds[w]+=k*(mr-ml+1);
else if(l<=ml&&r<=mr)xds[w]+=max(0,r-ml+1)*k;
else if(l>=ml&&r>=mr)xds[w]+=max(0,mr-l+1)*k;
else
{
lb[w]=k;
return;
}
if((mid>=ml&&mid<=mr)||(l>=ml&&l<=mr))zj(l,mid,ml,mr,w*2,k);
if((mid+1>=ml&&mid+1<=mr)||(r>=ml&&r<=mr))zj(mid+1,r,ml,mr,w*2+1,k);
return;
}
int main ()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
js(1,n,1);
while(m--)
{
cin>>zl>>x>>y;
if(zl==1)
{
cin>>k;
zj(1,n,x,y,1,k);
}
else cout<<cz(1,n,x,y,1)<<"\n";
}
}
```
60了哎!
by lijunxi1 @ 2023-10-04 21:52:23