multiplication range updates using lazy propagation

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Hi, I'm trying to solve a problem I just gave myself using lazy propagation and segment tree. Essentially, we have some queries on an array, where each query consists of two integers $$$L$$$ and $$$R$$$, and we are supposed to update the array by multiplying each element in the range by $$$2$$$, and then adding $$$1$$$ to every element. Every element a[i] within the range becomes 2 * a[i] + 1. For each query, we just print the sum of all elements.

Let N be the number of elements, A be the array.

So, for this test case:

N = 5. A = {1, 2, 3, 4, 5}. 1 Query: [L, R] = [1, 2]

The answer should be 20, but my code prints 19.

Here is my attempt:

Code

int N;
vi t, a, laz1, laz2;
// laz1 stores the aggregate of the multiplications
// laz2 stores the aggregate the additions

void build(int u, int l, int r) {
    if (l == r) {
        t[u] = a[l];
    } else {
        int mid = (l + r)/2;
        build(2 * u, l, mid);
        build(2 * u + 1, mid+1, r);
        t[u] = t[2 * u] + t[2 * u + 1];
    }
}

void addd(int u) { // lazy propagation for additions
    laz2[2 * u] += laz2[u];
    laz2[2 * u + 1] += laz2[u];
    t[2 * u] += laz2[u];
    t[2 * u + 1] += laz2[u];
    laz2[u] = 0;
}

void multiply(int u) { // lazy propagation for multiplication
    laz1[2 * u] *= laz1[u];
    laz1[2 * u + 1] *= laz1[u];
    t[2 * u] *= laz1[u];
    t[2 * u + 1] *= laz1[u];
    laz1[u] = 1;
}

void mult(int u, int tl, int tr, int l, int r, int val) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[u] *= val;
        laz1[u] *= val;
    } else {
        int mid = (tl + tr)/2;
        multiply(u);
        addd(u);
        mult(2 * u, tl, mid, l, min(mid, r), val);
        mult(2 * u + 1, mid+1, tr, max(mid+1, l), r, val);
        t[u] = t[2 * u] + t[2 * u + 1];
    }
}

void add(int u, int tl, int tr, int l, int r, int val) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[u] += val;
        laz2[u] += val;
    } else {
        int mid = (tl + tr)/2;
        multiply(u);
        addd(u);
        add(2 * u, tl, mid, l, min(mid, r), val);
        add(2 * u + 1, mid+1, tr, max(mid+1, l), r, val);
        t[u] = t[2 * u] + t[2 * u + 1];
    }
}

int main() { 
    setIO("");
    cin >> N;
    t.rsz(4 * N, 0), a.rsz(N), laz1.rsz(4 * N, 1), laz2.rsz(4 * N, 0);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    build(1, 0, N-1);
    int Q;
    cin >> Q;
    while (Q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        mult(1, 0, N-1, l, r, 2);
        add(1, 0, N-1, l, r, 1);
        cout << t[1] << endl;
    }
}

I split up each query into two updates: multiplying everything in the range by 2 and then adding by 1.

It seems that I am propagating correctly, why am I getting the wrong answer? Thank you in advance!