Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int64_t inf = 1000 * 1000 * 1000;
- int64_t inf64 = inf * inf;
- int64_t nll = 0;
- #define ll long long
- #define se second
- #define fi first
- #define endl '\n'
- vector <int64_t> a;
- struct fruct
- {
- int32_t l, r;
- int64_t delta, val;
- fruct *left, *right;
- fruct(int32_t l, int32_t r, int64_t delta, int64_t val):
- l(l), r(r), delta(delta),
- val(val), left(0), right(0){};
- };
- void build(fruct *cur, int32_t l, int32_t r)
- {
- if (l == r) cur->val = a[l];
- else
- {
- if (!cur->left) cur->left = new fruct(0, 0, 0, 0);
- if (!cur->right) cur->right = new fruct(0, 0, 0, 0);
- int32_t m = (l + r) / 2;
- build(cur->left, l, m);
- build(cur->right, m + 1, r);
- cur->val = cur->left->val + cur->right->val;
- }
- cur->l = l;
- cur->r = r;
- cur->delta = 0;
- }
- int64_t get_val(fruct *cur)
- {
- return cur->val + cur->delta * (cur->r - cur->l + 1);
- }
- void pull(fruct *cur)
- {
- cur->val = get_val(cur->left) + get_val(cur->right);
- }
- void push(fruct *cur)
- {
- cur->left->delta += cur->delta;
- cur->right->delta += cur->delta;
- cur->delta = 0;
- }
- void update(fruct *cur, int32_t l, int32_t r, int64_t d)
- {
- if (cur->l > r || cur->r < l) return;
- else if(cur->l >= l && cur->r <= r)
- {
- cur->delta += d;
- return;
- }
- push(cur);
- update(cur->left, l, r, d);
- update(cur->right, l, r, d);
- pull(cur);
- }
- int64_t get_sum(fruct *cur, int32_t l, int32_t r)
- {
- if (cur->l > r || cur->r < l) return 0;
- else if (cur->l >= l && cur->r <= r) return get_val(cur);
- push(cur);
- int64_t res = get_sum(cur->left, l, r) + get_sum(cur->right, l, r);
- pull(cur);
- return res;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- int64_t n, q;
- cin >> n >> q;
- a.resize(n, 0);
- fruct root(0, 0, 0, 0);
- build(&root, 0, n - 1);
- for (int32_t i = 0; i < q; ++i)
- {
- int64_t tp, l, r, x;
- cin >> tp;
- if (tp == 1)
- {
- cin >> l >> r >> x;
- update(&root, l, r - 1, x);
- }
- else
- {
- cin >> l >> r;
- cout << get_sum(&root, l, r - 1) << endl;
- }
- }
- }
- /*
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement