TWOARR Tester

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define F first
#define S second

const int MAXN = 2e5 + 10;
const int XX = 2e5 * 20 * 10;

int n, A[MAXN], B[MAXN], q;
int root[XX], tl[XX], tr[XX], sz;
ll smPers[XX], sm[MAXN<<2];

int plantPers(int b, int e){
    int id = sz++;
    if (e - b == 1){
        smPers[id] = B[b];
        return id;
    }

    int mid = b+e>>1;
    tl[id] = plantPers(b, mid);
    tr[id] = plantPers(mid, e);
    smPers[id] = smPers[tl[id]] + smPers[tr[id]];
    return id;
}

int updPers(int id, int b, int e, int pos, int val){
    int newId = sz++;
    if (e - b == 1){
        smPers[newId] = val;
        return newId;
    }

    int mid = b + e >> 1;
    tl[newId] = tl[id];
    tr[newId] = tr[id];
    if (pos < mid)
        tl[newId] = updPers(tl[newId], b, mid, pos, val);
    else
        tr[newId] = updPers(tr[newId], mid, e, pos, val);
    smPers[newId] = smPers[tl[newId]] + smPers[tr[newId]];
    return newId;
}

ll getPers(int id, int b, int e, int l, int r){
    if (l <= b && e <= r) return smPers[id];
    if (r <= b || e <= l) return 0;

    int mid = b + e >> 1;
    return getPers(tl[id], b, mid, l, r) + getPers(tr[id], mid, e, l, r);
}

int lzL[MAXN<<2], lzRoot[MAXN<<2];

void plant(int v, int b, int e){
    lzL[v] = -1;
    if (e - b == 1){
        sm[v] = A[b];
        return;
    }

    int mid = b + e >> 1;
    plant(v<<1, b, mid);
    plant(v<<1^1, mid, e);
    sm[v] = sm[v<<1] + sm[v<<1^1];
}

void pushDown(int v, int b, int e, int mid){
    if (lzL[v] == -1) return;

    lzL[v<<1] = lzL[v];
    sm[v<<1] = getPers(lzRoot[v], 0, n, lzL[v], lzL[v] + (mid - b));
    lzRoot[v<<1] = lzRoot[v<<1^1] = lzRoot[v];

    lzL[v<<1^1] = lzL[v] + (mid - b);
    sm[v<<1^1] = getPers(lzRoot[v], 0, n, lzL[v<<1^1], lzL[v<<1^1] + (e - mid));

    lzL[v] = -1;
}

int curRoot;
void upd(int v, int b, int e, int l, int r, int beg){
    if (l <= b && e <= r){
        beg += (b - l);
        sm[v] = getPers(root[curRoot], 0, n, beg, beg + (e-b));
        lzL[v] = beg;
        lzRoot[v] = root[curRoot];
        return;
    }
    if (r <= b || e <= l) return;

    int mid = b + e >> 1;
    pushDown(v, b, e, mid);
    upd(v<<1, b, mid, l, r, beg);
    upd(v<<1^1, mid, e, l, r, beg);
    sm[v] = sm[v<<1] + sm[v<<1^1];
}

ll get(int v, int b, int e, int l, int r){
    if (l <= b && e <= r) return sm[v];
    if (r <= b || e <= l) return 0;

    int mid = b + e >> 1;
    pushDown(v, b, e, mid);
    return get(v<<1, b, mid, l, r) + get(v<<1^1, mid, e, l, r);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> A[i];
    for (int i = 0; i < n; i++) cin >> B[i];

    root[0] = plantPers(0, n);
    plant(1, 0, n);

    while (q--){
        int tp; cin >> tp;
        if (tp == 1){
            int pos, val; cin >> pos >> val, pos--;
            root[curRoot+1] = updPers(root[curRoot], 0, n, pos, val);
            curRoot++;
        }
        else if (tp == 2){
            int l1, r1, l2; cin >> l1 >> r1 >> l2, l1--, l2--;
            upd(1, 0, n, l1, r1, l2);
        }
        else{
            int l, r; cin >> l >> r, l--;
            cout << get(1, 0, n, l, r) << "\n";
        }
    }
    return 0;
}