test/data_structure/Range_Add_Query.test.cpp

• View this file on GitHub
• Last update: 2023-10-26 13:46:37+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_E

Depends on

• dual segtree (commutative) (data_structure/dual_segtree_commutative.hpp)

Code

#define PROBLEM \
    "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_E"

#include <iostream>

#include <vector>


#include "../../data_structure/dual_segtree_commutative.hpp"


int op(int a, int b) {
    return a + b;
}

int e() {
    return 0;
}

int main() {
    int n, q;
    std::cin >> n >> q;
    ebi::DualSegtree<int, op, e> dseg(n);
    while (q--) {
        int flag;
        std::cin >> flag;
        if (flag == 0) {
            int s, t, x;
            std::cin >> s >> t >> x;
            s--;
            dseg.apply(s, t, x);
        } else {
            int t;
            std::cin >> t;
            t--;
            std::cout << dseg.get(t) << std::endl;
        }
    }
}

#line 1 "test/data_structure/Range_Add_Query.test.cpp"
#define PROBLEM \
    "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_E"

#include <iostream>

#include <vector>


#line 2 "data_structure/dual_segtree_commutative.hpp"

#include <cassert>

#line 5 "data_structure/dual_segtree_commutative.hpp"

namespace ebi {

template <class Monoid, Monoid (*op)(Monoid, Monoid), Monoid (*e)()>
struct DualSegtree {
  public:
    DualSegtree(int n) : n(n) {
        size = 1;
        while (size < n) size <<= 1;
        data.assign(2 * size, e());
    }

    DualSegtree(const std::vector<Monoid> &vec) : n(vec.size()) {
        size = 1;
        while (size < n) size <<= 1;
        data.assign(2 * size, e());
        std::copy(vec.begin(), vec.end(), data.begin() + size);
    }

    Monoid get(int idx) const {
        assert(0 <= idx && idx < n);
        idx += size;
        Monoid val = e();
        while (idx > 0) {
            val = op(val, data[idx]);
            idx >>= 1;
        }
        return val;
    }

    void apply(int l, int r, Monoid x) {
        assert(0 <= l && l <= r && r <= n);
        l += size;
        r += size;
        while (l < r) {
            if (l & 1) {
                data[l] = op(data[l], x);
                l++;
            }
            if (r & 1) {
                r--;
                data[r] = op(data[r], x);
            }
            l >>= 1;
            r >>= 1;
        }
        return;
    }

  private:
    std::vector<Monoid> data;
    int n;
    int size;
};

}  // namespace ebi
#line 8 "test/data_structure/Range_Add_Query.test.cpp"

int op(int a, int b) {
    return a + b;
}

int e() {
    return 0;
}

int main() {
    int n, q;
    std::cin >> n >> q;
    ebi::DualSegtree<int, op, e> dseg(n);
    while (q--) {
        int flag;
        std::cin >> flag;
        if (flag == 0) {
            int s, t, x;
            std::cin >> s >> t >> x;
            s--;
            dseg.apply(s, t, x);
        } else {
            int t;
            std::cin >> t;
            t--;
            std::cout << dseg.get(t) << std::endl;
        }
    }
}

Back to top page