#include #define int long long #define mod (int)(1e9+7) #define inf (int)(3e18) #define rep(i,n) for(int i=0;i #define PiP pair> #define PP pair #define all(v) v.begin(),v.end() #define mkp make_pair #define mkt make_tuple #define prique(T) priority_queue,greater> #define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end()) using namespace std; template inline void chmax(T& a, T b) { a = max(a, b); } template inline void chmin(T& a, T b) { a = min(a, b); } bool prime(int x) { for (int i = 2; i * i <= x; i++) { if (x % i == 0)return false; } return x != 1; } int gcd(int x, int y) { if (y == 0)return x; return gcd(y, x % y); } int lcm(int x, int y) { return x / gcd(x, y) * y; } int kai(int x, int y) { int res = 1; for (int i = x - y + 1; i <= x; i++) { res *= i; res %= mod; } return res; } int mod_pow(int x, int y, int m) { int res = 1; while (y > 0) { if (y & 1) { res = res * x % m; } x = x * x % m; y >>= 1; } return res; } int comb(int x, int y) { if (y > x)return 0; return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod; } int get_rand(int MIN, int MAX) { random_device rnd; mt19937_64 mt64(rnd()); uniform_int_distributionengine(MIN, MAX); return engine(mt64); } /*--------Library Zone!--------*/ struct RangeSumQuery { int size = 1; vectordat, lazy, ki, gu; vectordivide; void init(int k = 0, int l = 0, int r = -1) { if (r == -1)r = size; gu[k] = r - l; if (r - l == 1)return; init(k * 2 + 1, l, (l + r) / 2); init(k * 2 + 2, (l + r) / 2, r); } void eval(int k, int l, int r) { if (divide[k]) { dat[k] = ki[k]; divide[k] = 0; if (r - l > 1) { divide[k * 2 + 1] = 1; divide[k * 2 + 2] = 1; } } if (lazy[k] % 2) { swap(ki[k], gu[k]); } dat[k] += lazy[k] * (r - l); if (r - l > 1) { lazy[k * 2 + 1] += lazy[k]; lazy[k * 2 + 2] += lazy[k]; } lazy[k] = 0; } void update_1(int a, int b, int k = 0, int l = 0, int r = -1) { if (r == -1)r = size; eval(k, l, r); if (r <= a || b <= l)return; if (a <= l && r <= b) { divide[k] = 1; eval(k, l, r); return; } update_1(a, b, k * 2 + 1, l, (l + r) / 2); update_1(a, b, k * 2 + 2, (l + r) / 2, r); dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2]; ki[k] = ki[k * 2 + 1] + ki[k * 2 + 2]; gu[k] = gu[k * 2 + 1] + gu[k * 2 + 2]; } void update_2(int a, int b, int x, int k = 0, int l = 0, int r = -1) { if (r == -1)r = size; eval(k, l, r); if (r <= a || b <= l)return; if (a <= l && r <= b) { lazy[k] += x; eval(k, l, r); return; } update_2(a, b, x, k * 2 + 1, l, (l + r) / 2); update_2(a, b, x, k * 2 + 2, (l + r) / 2, r); dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2]; ki[k] = ki[k * 2 + 1] + ki[k * 2 + 2]; gu[k] = gu[k * 2 + 1] + gu[k * 2 + 2]; } int query(int a, int b, int k = 0, int l = 0, int r = -1) { if (r == -1)r = size; eval(k, l, r); if (r <= a || b <= l)return 0; if (a <= l && r <= b) { return dat[k]; } int lval = query(a, b, k * 2 + 1, l, (l + r) / 2); int rval = query(a, b, k * 2 + 2, (l + r) / 2, r); return lval + rval; } RangeSumQuery(int x) { while (size < x)size *= 2; dat.resize(size * 2 - 1, 0); lazy.resize(size * 2 - 1, 0); ki.resize(size * 2 - 1, 0); gu.resize(size * 2 - 1); divide.resize(size * 2 - 1, 0); init(); } }; int n, q; signed main() { cin >> n >> q; RangeSumQuery RSQ(n); rep(i, n) { int a; cin >> a; RSQ.update_2(i, i + 1, a); } rep(i, q) { int type; cin >> type; if (type == 1) { int l, r; cin >> l >> r; l--; r--; RSQ.update_1(l, r + 1); } else if (type == 2) { int l, r, x; cin >> l >> r >> x; l--; r--; RSQ.update_2(l, r + 1, x); } else { int l, r; cin >> l >> r; l--; r--; cout << RSQ.query(l, r + 1) << endl; } } }