Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define fi first
- #define se second
- const int N = 1e5 + 10;
- ll sum[4 * N];
- ll add[4 * N];
- void push(int v, int l, int r) {
- int m = (l + r) / 2;
- add[v * 2 + 1] += add[v];
- sum[v * 2 + 1] += (m - l + 1) * add[v];
- add[v * 2 + 2] += add[v];
- sum[v * 2 + 2] += (r - (m + 1) + 1) * add[v];
- add[v] = 0;
- }
- void upd(int l, int r, int tl, int tr, int v, int x) {
- if (l > tr || r < tl) {
- return;
- }
- if (l <= tl && r >= tr) {
- sum[v] += (tr - tl + 1) * x;
- add[v] += x;
- } else {
- push(v, tl, tr);
- int tm = (tl + tr) >> 1;
- upd(l, r, tl, tm, v * 2 + 1, x);
- upd(l, r, tm + 1, tr, v * 2 + 2, x);
- sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
- }
- }
- ll get(int l, int r, int tl, int tr, int v) {
- if (l > tr || r < tl) {
- return 0;
- }
- if (l <= tl && r >= tr) {
- return sum[v];
- } else {
- push(v, tl, tr);
- int tm = (tl + tr) >> 1;
- return get(l, r, tl, tm, v * 2 + 1) + get(l, r, tm + 1, tr, v * 2 + 2);
- }
- }
- int main() {
- #ifdef LOCAL
- freopen("input.txt", "rt", stdin);
- freopen("output.txt", "wt", stdout);
- #endif
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int n;
- cin >> n;
- for (int i = 0; i < n; ++i) {
- int a;
- cin >> a;
- upd(i, i, 0, n - 1, 0, a);
- }
- int q;
- cin >> q;
- while (q--) {
- int t;
- cin >> t;
- if (t == 1) {
- int l, r;
- cin >> l >> r;
- l--;
- r--;
- cout << get(l, r, 0, n - 1, 0) << '\n';
- } else {
- int l, r;
- ll x;
- cin >> l >> r >> x;
- l--;
- r--;
- upd(l, r, 0, n - 1, 0, x);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement