RT,想不懂标记永久化里面的sum如何在区间乘法中维护(这是标记永久化的代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
ll n,m;
ll sum[400010],add[400010],a[100010];
void build(ll k,ll l,ll r) {
if(l == r) {
sum[k] = a[l];
return;
}
ll mid = (l+r)/2;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
sum[k] += sum[k*2] + sum[k*2+1];
}
void Add(ll k,ll l,ll r,ll x,ll y,ll num) {
if(l > y || r < x) return;
if(l >= x && r <= y) {
add[k] += num;
return;
}
sum[k] += (min(r,y) - max(l,x) + 1) * num;
ll mid = (l+r)/2;
Add(k*2,l,mid,x,y,num);
Add(k*2+1,mid+1,r,x,y,num);
}
ll query(ll k,ll l,ll r,ll x,ll y) {
if(l > y || r < x) return 0;
if(l >= x && r <= y) return sum[k] + add[k] * (r-l+1);
long long res = 0;
res += add[k] * (min(r,y) - max(x,l) + 1);
ll mid = (l+r)/2;
res += query(k*2,l,mid,x,y);
res += query(k*2+1,mid+1,r,x,y);
return res;
}
int main() {
cin >> n >> m;
for(ll i = 1;i <= n;i++) {
cin >> a[i];
}
build(1,1,n);
for(ll i = 1;i <= m;i++) {
ll judge,x,y,k;
cin >> judge;
if(judge == 1) {
cin >> x >> y >> k;
Add(1,1,n,x,y,k);
}
else {
cin >> x >> y;
cout << query(1,1,n,x,y) << endl;
}
}
return 0;
}