[HELP NEEDED!!!] CSES Range Updates and Sums
Разница между en1 и en2, 0 символ(ов) изменены
I have very recently learned about Segment Trees and started practicing problems from cses problemset. I am now stuck on [this](https://cses.fi/problemset/task/1735/) problem. I have tried everything from my side, please help me debug my code.↵

~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵

using ll = long long;↵
int const DEF = 0;  // default value of a node↵

template<typename T>↵
struct LazySegTree {↵
    int n;↵
    vector<int> ops;  // 1 -> delta, 2 -> assignment↵
    vector<T> tree;↵
    vector<T> lazy;  // store updates↵
    vector<bool> marked;↵
    LazySegTree() : n(0) {}↵
    LazySegTree(vector<T>& arr) : n(arr.size()) {↵
        // size of original arr may change↵
        while(__builtin_popcount(n) != 1) {↵
            n++;↵
            arr.push_back(DEF);  // change the initial value↵
        }↵
        tree.assign(2 * n, DEF);↵
        lazy.assign(2 * n, DEF);↵
        ops.assign(2 * n, DEF);↵
        marked.assign(2 * n, false);↵
        build(arr);↵
    }↵

    void build(vector<T>& arr) {↵
        for(int i = n; i < 2 * n; i++) {↵
            tree[i] = arr[i - n];↵
        }↵
        for(int i = n - 1; i > 0; i--) {↵
            tree[i] = op1(tree[2 * i], tree[2 * i + 1]);↵
        }↵
    }↵

    void take(int idx, int lo, int hi, T par_val) {  ↵
        // how will the update change the tree[idx] ?↵
        if(ops[idx] == 1) {↵
            lazy[idx] += par_val;↵
            tree[idx] += par_val * (hi - lo + 1);↵
            marked[idx] = true;↵
        } else if(ops[idx] == 2){↵
            lazy[idx] = par_val;↵
            tree[idx] = par_val * (hi - lo + 1);↵
            marked[idx] = true;↵
        }↵
    }↵

    void push(int idx, int lo, int hi) {  ↵
        // push the updates to the left and right children↵
        if(marked[idx]) {↵
            int mid = (lo + hi) / 2;↵
            ops[2 * idx] = ops[2 * idx + 1] = ops[idx];↵
            take(2 * idx, lo, mid, lazy[idx]);↵
            take(2 * idx + 1, mid + 1, hi, lazy[idx]);↵
            lazy[idx] = DEF;↵
            ops[idx] = 0;↵
            marked[idx] = false;↵
        }↵
    }↵

    void update(int idx, int l, int r, int lo, int hi, T v, int op) {   // last argument can be val or delta, val for assignment↵
        if(lo > r || hi < l) return;↵
        if(lo >= l && hi <= r) {↵
            ops[idx] = op;↵
            take(idx, lo, hi, v);↵
            return;↵
        }↵
        push(idx, lo, hi);↵
        int mid = (lo + hi) / 2;↵
        update(2 * idx, l, r, lo, mid, v, op);↵
        update(2 * idx + 1, l, r, mid + 1, hi, v, op);↵
        // update tree[idx] here ↵
        tree[idx] = op1(tree[2 * idx], tree[2 * idx + 1]);↵
    }↵

    T query(int idx, int l, int r, int lo, int hi) {↵
        if(lo > r || hi < l) return DEF;↵
        if(lo >= l && hi <= r) {↵
            return tree[idx];↵
        }↵
        push(idx, lo, hi);↵
        int mid = (lo + hi) / 2;↵
        return op1(query(2 * idx, l, r, lo, mid), query(2 * idx + 1, l, r, mid + 1, hi));↵
    }↵

    T query(int l, int r) { return query(1, l, r, 0, n - 1); }↵

    void update(int l, int r, T v, int op) { update(1, l, r, 0, n - 1, v, op); }↵

    T op1(T a, T b) {↵
        // query operation↵
        return a + b;↵
    }↵
};↵
void solve(int test_no) {↵
    int n, q;↵
    cin >> n >> q;↵
    vector<ll> arr(n);↵
    for(auto& x : arr) cin >> x;↵

    LazySegTree<ll> seg(arr);↵
    int a, b, x, op;↵
    while(q--) {↵
        cin >> op;↵
        if(op == 1) {↵
            cin >> a >> b >> x;↵
            a--, b--;↵
            seg.update(a, b, x, 1);↵
        } else if(op == 2) {↵
            cin >> a >> b >> x;↵
            a--, b--;↵
            seg.update(a, b, x, 2);↵
        } else {↵
            cin >> a >> b;↵
            a--, b--;↵
            cout << seg.query(a, b) << '\n';↵
        }↵
    }↵
}↵

int main() {↵

    ios_base::sync_with_stdio(false);↵
    cin.tie(NULL);↵
    int T = 1;↵
    // cin >> T;↵
    for(int t = 1; t <= T; t++) {↵
        solve(t);↵
    }↵
}↵
~~~~~↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский kar2003 2023-12-12 19:52:01 0 (published)
en1 Английский kar2003 2023-12-12 19:47:44 4066 Initial revision (saved to drafts)