Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
- const int SIZE = (1 << 17);
- int a[100100];
- int tree[2 * SIZE];
- int tree_add[2 * SIZE];
- int n;
- void push(int v, int L, int R)
- {
- if (L != R - 1)
- {
- tree_add[2 * v + 1] = tree_add[v];
- tree_add[2 * v + 2] = tree_add[v];
- }
- tree[v] += tree_add[v] * (R - L);
- tree_add[v] = 0;
- }
- void build_sum_tree(int v, int L, int R)
- {
- if (L == R - 1)
- {
- if (L < n)
- {
- tree[v] = a[L];
- }
- return;
- }
- int M = (L + R) / 2;
- build_sum_tree(2 * v + 1, L, M);
- build_sum_tree(2 * v + 2, M, R);
- tree[v] = tree[2 * v + 1] + tree[2 * v + 2];
- }
- int64_t get_summary(int v, int L, int R, int l, int r)
- {
- push(v, L, R);
- if (r <= L || R <= l) return 0;
- if (l <= L && R <= r) return tree[v];
- int M = (L + R) / 2;
- int64_t first_child = get_summary(2 * v + 1, L, M, l, r);
- int64_t second_child = get_summary(2 * v + 2, M, R, l, r);
- return first_child + second_child;
- }
- void set_in_sum_tree(int v, int L, int R, int i, int x)
- {
- if (L == R - 1)
- {
- tree[v] = x;
- a[i] = x;
- return;
- }
- int M = (L + R) / 2;
- if (i < M) set_in_sum_tree(2 * v + 1, L, M, i, x);
- else set_in_sum_tree(2 * v + 2, M, R, i, x);
- tree[v] = tree[2 * v + 1] + tree[2 * v + 2];
- }
- void set_range(int v, int L, int R, int l, int r, int x)
- {
- push(v, L, R);
- if (r <= L || R <= l) return;
- if (l <= L && R <= r)
- {
- tree_add[v] += x;
- push(v, L, R);
- return;
- }
- int M = (L + R) / 2;
- set_range(2 * v + 1, L, M, l, r, x);
- set_range(2 * v + 2, M, R, l, r, x);
- tree[v] = tree[2 * v + 1] + tree[2 * v + 2];
- }
- int main()
- {
- int q;
- cin >> n >> q;
- forn (req, q)
- {
- char type;
- cin >> type;
- if (type == '1')
- {
- int l, r, x;
- cin >> l >> r >> x;
- --l;
- set_range(0, 0, SIZE, l, r, x);
- }
- else if (type == '2')
- {
- int l, r;
- cin >> l >> r;
- --l;
- cout << get_summary(0, 0, SIZE, l, r) << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement