Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int maxN = 1e5;
- int n;
- struct SegmentTree {
- vector<long long> t = vector<long long> (maxN * 4);
- vector<long long> lazy = vector<long long> (maxN * 4);
- void push(int x) {
- lazy[2 * x] += lazy[x];
- lazy[2 * x + 1] += lazy[x];
- t[2 * x] += lazy[x];
- t[2 * x + 1] += lazy[x];
- lazy[x] = 0;
- }
- void upd(int x, int lx, int rx, int l, int r, long long val) {
- push(x);
- if(lx >= l && rx <= r) {
- t[x] += val * (rx - lx + 1);
- lazy[x] += val;
- return;
- }
- if(lx > r || rx < l) {return;}
- push(x);
- int m = (lx + rx) / 2;
- upd(2 * x, lx, m, l, r, val);
- upd(2 * x + 1, m + 1, rx, l, r, val);
- t[x] = t[2 * x] + t[2 * x + 1];
- }
- void upd(int l, int r, long long val) {
- upd(1, 0, n - 1, l, r, val);
- }
- long long query(int x, int lx, int rx, int l, int r) {
- push(x);
- if(lx >= l && rx <= r) {
- return t[x];
- }
- if(lx > r || rx < l) {return 0;}
- int m = (lx + rx) / 2;
- long long f = query(2 * x, lx, m, l, r) , s = query(2 * x + 1, m + 1, rx, l, r);
- t[x] = t[2 * x + 1] + t[2 * x];
- return f + s;
- }
- long long query(int l, int r) {
- return query(1, 0, n - 1, l, r);
- }
- };
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- int m;
- cin >> n >> m;
- SegmentTree st;
- for (int i = 0; i<m; i++) {
- int type;
- cin >> type;
- if(type == 1) {
- long long l,r,v;
- cin >> l >> r >> v;
- r--;
- st.upd(l, r, v);
- continue;
- }
- int l, r;
- cin >> l >> r;
- r--;
- cout << st.query(l, r) << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement