test/aoj/DSL2E.test.cpp

• View this file on GitHub
• Last update: 2023-07-03 22:10:06+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_E

Depends on

• segment_tree/dual_segment_tree.hpp

Code

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

#include "../../segment_tree/dual_segment_tree.hpp"
using namespace std;
using llong = long long;

struct RAQ {
    using value_type = long long;
    using T = value_type;

    inline static T identity() {
        return 0;
    };
    inline static T operation(T a, T b) {
        return a + b;
    };
};

int main() {
    llong n, q;
    llong com;
    llong s, t, x;
    llong idx;

    cin >> n >> q;
    DualSegmentTree<RAQ> seg(n);
    for (int i = 0; i < q; i++) {
        cin >> com;

        if (com == 0) {
            cin >> s >> t >> x;
            s--;
            seg.update(s, t, x);
        } else if (com == 1) {
            cin >> idx;
            idx--;
            cout << seg[idx] << '\n';
        }
    }
};

#line 1 "test/aoj/DSL2E.test.cpp"
#define PROBLEM \
    "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_E"
#include <iostream>

#line 1 "segment_tree/dual_segment_tree.hpp"



#include <cstdint>
#include <vector>

//===
template <class Monoid>
struct DualSegmentTree {
    using T = typename Monoid::value_type;
    std::vector<T> lazy;

    DualSegmentTree() = default;
    explicit DualSegmentTree(uint32_t n) : lazy(n << 1, Monoid::identity()){};

    inline int size() {
        return (int)(lazy.size() >> 1);
    };

    inline void propagate(uint32_t k) {
        if (k >= size()) return;
        lazy[(k << 1) | 0] = Monoid::operation(lazy[(k << 1) | 0], lazy[k]);
        lazy[(k << 1) | 1] = Monoid::operation(lazy[(k << 1) | 1], lazy[k]);
        lazy[k] = Monoid::identity();
    };

    inline void push_down(uint32_t k) {
        for (uint32_t i = 31; i > 0; i--) propagate(k >> i);
    };

    // [l, r)
    void update(uint32_t l, uint32_t r, T op) {
        l += size();
        r += size();
        push_down(l);
        push_down(r - 1);

        while (l < r) {
            if (l & 1) lazy[l] = Monoid::operation(lazy[l], op), l++;
            if (r & 1) --r, lazy[r] = Monoid::operation(lazy[r], op);

            l >>= 1;
            r >>= 1;
        }
    };

    T get(uint32_t k) {
        k += size();
        push_down(k);
        return lazy[k];
    };

    T operator[](uint32_t k) {
        return get(k);
    };
};
//===


#line 6 "test/aoj/DSL2E.test.cpp"
using namespace std;
using llong = long long;

struct RAQ {
    using value_type = long long;
    using T = value_type;

    inline static T identity() {
        return 0;
    };
    inline static T operation(T a, T b) {
        return a + b;
    };
};

int main() {
    llong n, q;
    llong com;
    llong s, t, x;
    llong idx;

    cin >> n >> q;
    DualSegmentTree<RAQ> seg(n);
    for (int i = 0; i < q; i++) {
        cin >> com;

        if (com == 0) {
            cin >> s >> t >> x;
            s--;
            seg.update(s, t, x);
        } else if (com == 1) {
            cin >> idx;
            idx--;
            cout << seg[idx] << '\n';
        }
    }
};

Back to top page