120 lines
3.2 KiB
C++
120 lines
3.2 KiB
C++
#include<bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
|
|
void solve() {
|
|
int64_t n, m;
|
|
cin >> n >> m;
|
|
vector<int64_t> a(n + 1);
|
|
for (int64_t i = 1; i <= n; i++)cin >> a[i];
|
|
vector<int64_t> tree(4 * n);
|
|
vector<int64_t> lazy(4 * n);
|
|
auto lz = [&](int64_t p, int64_t s, int64_t t, int64_t x) {
|
|
// cerr << "Lazy " << p << " " << s << " " << t << " " << x << "\n";
|
|
tree[p] += (t - s + 1) * x;
|
|
lazy[p] += x;
|
|
};
|
|
auto build = [&](auto &&self, int64_t s, int64_t t, int64_t p) {
|
|
if (s == t) {
|
|
tree[p] = a[s];
|
|
return;
|
|
}
|
|
int64_t m = (s+t)/2;
|
|
self(self, s, m, p * 2);
|
|
self(self, m + 1, t, p * 2 + 1);
|
|
tree[p] = tree[p * 2] + tree[p * 2 + 1];
|
|
};
|
|
build(build, 1, n, 1);
|
|
auto query = [&](auto &&self, int64_t l, int64_t r, int64_t s, int64_t t, int64_t p) -> int64_t {
|
|
// cerr << "query in " << l << " " << r << " " << s << " " << t << "\n";
|
|
int64_t sum = 0;
|
|
if (l <= s && t <= r) return tree[p];
|
|
int64_t m = (s+t)/2;
|
|
if (lazy[p]) {
|
|
// cerr << "Lazy p " << " " << s << " " << t << " " << p << " " << lazy[p] << "\n";
|
|
lz(p * 2, s, m, lazy[p]);
|
|
lz(p * 2 + 1, m + 1, t, lazy[p]);
|
|
lazy[p] = 0;
|
|
}
|
|
if (l <= m) {
|
|
sum += self(self, l, r, s, m, p * 2);
|
|
}
|
|
if (r >= m + 1) {
|
|
sum += self(self, l, r, m + 1, t, p * 2 + 1);
|
|
}
|
|
return sum;
|
|
};
|
|
auto modify = [&](auto &&self, int64_t l, int64_t r, int64_t s, int64_t t, int64_t p, int64_t x) -> void {
|
|
// cerr << "Modify in " << l << " " << r << " " << s << " " << t << " " << p << " " << x << "\n";
|
|
if (l <= s && t <= r) {
|
|
lz(p, s, t, x);
|
|
return;
|
|
}
|
|
int64_t m = s + ((t - s) >> 1);
|
|
if (lazy[p] && s != t) {
|
|
// cerr << "Lazy p " << " " << s << " " << t << " " << p << " " << lazy[p] << "\n";
|
|
lz(p * 2, s, m, lazy[p]);
|
|
lz(p * 2 + 1, m + 1, t, lazy[p]);
|
|
lazy[p] = 0;
|
|
}
|
|
if (l <= m) {
|
|
self(self, l, r, s, m, p * 2, x);
|
|
}
|
|
if (r >= m + 1) {
|
|
self(self, l, r, m + 1, t, p * 2 + 1, x);
|
|
}
|
|
tree[p]=tree[p*2]+tree[p*2+1];
|
|
};
|
|
for (int64_t i = 1; i <= m; i++) {
|
|
int64_t x;
|
|
cin >> x;
|
|
if (x == 1) {
|
|
int64_t l, r, x;
|
|
cin >> l >> r >> x;
|
|
modify(modify, l, r, 1, n, 1, x);
|
|
} else {
|
|
int64_t l, r;
|
|
cin >> l >> r;
|
|
cout << query(query, l, r, 1, n, 1) << "\n";
|
|
}
|
|
}
|
|
}
|
|
|
|
int fact(int x);
|
|
|
|
int fact(int x)
|
|
{
|
|
if(x==0)return 1;
|
|
return fact(x-1)*x;
|
|
}
|
|
|
|
int main() {
|
|
int64_t t;
|
|
// cin>>t;
|
|
t = 1;
|
|
while (t--) {
|
|
solve();
|
|
}
|
|
|
|
// struct F
|
|
// {
|
|
// int operator()(int x)const{
|
|
// if(x==0)return 1;
|
|
// return (*this)(x-1)*x;
|
|
// }
|
|
// };
|
|
// F f;
|
|
|
|
// auto f=[](auto &&self,int x){
|
|
// if(x==0)return 1;
|
|
// return self(self,x-1)*x;
|
|
// };
|
|
auto f=[](auto &&self,int x){
|
|
if(x==0)return 1;
|
|
return self(self,x-1)*x;
|
|
};
|
|
// f=[](int x){return x+1;};
|
|
f(f,1);
|
|
|
|
}
|