Mỗi thông tin loại ~2~ đều có thể chuyển thành thông tin loại ~1~ bằng cách thực hiện ngược lại thông tin bị sai kia.

Ví dụ: thông tin thứ ~3~ yêu cầu tăng các phần tử trong đoạn [~1~, ~2~] thêm ~1~ đơn vị. Thông tin thứ ~5~ nói rằng thông tin thứ ~3~ là thông tin sai, vậy thông tin thứ ~5~ có thể chuyển thành: giảm các phần tử trong đoạn [~1~, ~2~] đi ~1~ đơn vị.

Bài toán trở thành một bài cấu trúc dữ liệu cơ bản, có thể dùng Segment Tree hoặc cây BIT để giải.

Code mẫu

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long INF = 1e18;
const long long N = 1e5 + 5;

int n, q;
ll lazy[4 * N], st[4 * N], a[N];

void build(int id, int l, int r) {
    if (l > r) return;
    if (l == r) {
        st[id] = a[l];
        return;
    }

    int mid = l + r >> 1;

    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);

    st[id] = st[id << 1] + st[id << 1 | 1];
}

void push(int id, int l, int r, int mid) {
    ll &t = lazy[id], u = id << 1, v = id << 1 | 1;
    st[u] += (mid - l + 1) * t; st[v] += (r - mid) * t;
    lazy[u] += t; lazy[v] += t;
    t = 0; 
}

void upd(int id, int l, int r, int lef, int rig, int v) {
    if (l > rig || r < lef) return;
    if (lef <= l && r <= rig) {
        st[id] += 1ll * (r - l + 1) * v;
        lazy[id] += v;
        return;
    }

    int mid = l + r >> 1;
    push(id, l, r, mid);

    upd(id << 1, l, mid, lef, rig, v);
    upd(id << 1 | 1, mid + 1, r, lef, rig, v);

    st[id] = st[id << 1] + st[id << 1 | 1];
}

ll get(int id, int l, int r, int lef, int rig) {
    if (l > rig || r < lef) return 0;
    if (lef <= l && r <= rig) return st[id];
    int mid = l + r >> 1;
    push(id, l, r, mid);
    return get(id << 1, l, mid, lef, rig) + get(id << 1 | 1, mid + 1, r, lef, rig);
}

struct queries {
    ll op, l, r, v;
    void flip() {
        v = -v;
    }
} qr[N];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n >> q;
    for (int i = 1; i <= n; i ++) cin >> a[i];

    build(1, 1, n);

    int op, l, r, x;

    for (int i = 1; i <= q; i ++) {
        cin >> op >> l;

        if (op == 1) {
            cin >> r >> x;
            qr[i] = {op, l, r, x};
            upd(1, 1, n, l, r, x);
        } 

        if (op == 2) {
            qr[l].flip();
            qr[i] = qr[l];
            upd(1, 1, n, qr[i].l, qr[i].r, qr[i].v);
        }

        if (op == 3) {
            cin >> r;
            cout << get(1, 1, n, l, r) << '\n';
        }
    }   

    return 0;
}