Codeforces SegTree - part 2 - step 4 - B

#include <bits/stdc++.h>
#define int unsigned long long int

using namespace std;

/*
So make things easier you can firstly consider 3 lazy values instead of the two that I used(later we will combine two of them into a single one):
l1 - sum of values a
l2 - sum of values d
l3 - sum of values d * l.
The update for a node which has ends of interval [L, R] will be:
node += (R - L + 1) * l1 + (R * (R + 1) - L * (L - 1)) / 2 * l2 - (R - L + 1) * l3,
so the first term of the sum is obvious because (R - L + 1) is the length of the segment(I use 1 - indexing) and for each element of the segment you have to add a, so for the whole segment you add len_seg(R - L + 1) * a(l1 in our case because there may be more update operations added in l1)
The third one is easy too. If we were to rewrite the statement update operation we would get: xi += a + d * i - d * l, so this is the same case as for a. You just have to subtract
len_seg(R - L + 1) * l3. Also, we observe that l1 and l3 have the same coefficient so we can
combine them in only one lazy value(in my code this value is lazy[x].first)
Finally, the second one is easy again:). We have the sum of d in l2. If we want
to update the segment [L, R] will need to add L * l2 + (L + 1) * l2 + ... + R * l2 =
= l2 * (L + (L + 1) + ... + R) = l2 * ((1 + 2 + ... + R) - (1 + 2 + ... + (L - 1)) =
= l2 * (R * (R + 1) - L * (L - 1)) / 2 (using Gauss's formula). In my code l2 is lazy[x].second.
*/

struct SegTree {
    int Size;
    vector < int > Tree;
    vector < pair < int , int > > lazy;

    void init(int N) {
        Size = 1;
        while(Size < N)
            Size <<= 1;
        Tree.assign((Size << 1) + 1, 0);
        lazy.assign((Size << 1) + 1, make_pair(0, 0));
    }

    void propagate(int x, int lx, int rx) {
        if(lx == rx)
            return;
        int mid = (lx + rx) >> 1;
        int len1 = mid - lx + 1;
        int len2 = rx - mid;
        Tree[x << 1] += len1 * lazy[x].first + (mid * (mid + 1) - lx * (lx - 1)) / 2 * lazy[x].second;
        Tree[(x << 1) + 1] += len2 * lazy[x].first + (rx * (rx + 1) - mid * (mid + 1)) / 2 * lazy[x].second;
        lazy[x << 1].first += lazy[x].first;
        lazy[x << 1].second += lazy[x].second;
        lazy[(x << 1) + 1].first += lazy[x].first;
        lazy[(x << 1) + 1].second += lazy[x].second;
        lazy[x] = make_pair(0, 0);
    }

    void update(int x, int lx, int rx, int st, int dr, int a, int d) {
        propagate(x, lx, rx);
        if(st <= lx && rx <= dr) {
            int len = rx - lx + 1;
            Tree[x] += len * (a - d * st) + ((rx * (rx + 1) - lx * (lx - 1)) / 2 * d);
            lazy[x].first += (a - d * st);
            lazy[x].second += d;
            return;
        }
        int mid = (lx + rx) >> 1;
        if(st <= mid)
            update(x << 1, lx, mid, st, dr, a, d);
        if(mid < dr)
            update((x << 1) + 1, mid + 1, rx, st, dr, a, d);
    }

    int query(int x, int lx, int rx, int poz) {
        propagate(x, lx, rx);
        if(lx == rx)
            return Tree[x];
        int mid = (lx + rx) >> 1;
        if(poz <= mid)
            return query(x << 1, lx, mid, poz);
        else
            return query((x << 1) + 1, mid + 1, rx, poz);
    }
};

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    SegTree Tree;
    Tree.init(N);
    while(Q --) {
        int type;
        cin >> type;
        if(type == 1) {
            int st, dr, a, d;
            cin >> st >> dr >> a >> d;
            Tree.update(1, 1, N, st, dr, a, d);
        }
        else {
            int poz;
            cin >> poz;
            cout << Tree.query(1, 1, N, poz) << '\n';
        }
    }
}