test/AOJ-DLS-2-D.test.cpp

• View this file on GitHub
• Last update: 2021-04-09 16:57:09+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_D

Depends on

• Dual-Segment-Tree (segtree/dual-segment-tree.cpp)

Code

#define PROBLEM \
    "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_D"

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

#include "../segtree/dual-segment-tree.cpp"

using S = int;
using F = int;
F id() { return -1; }
S mapping(F f, S s) { return f == id() ? s : f; }
F composition(F f, F g) { return f == id() ? g : f; }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;

    DualSegmentTree<S, F, mapping, composition, id> seg(vector<S>(n, INT_MAX));

    for(int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if(t) {
            int p;
            cin >> p;
            cout << seg.get(p) << "\n";
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            seg.apply(l, r + 1, x);
        }
    }

    return 0;
}

#line 1 "test/AOJ-DLS-2-D.test.cpp"
#define PROBLEM \
    "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_D"

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

#line 3 "segtree/dual-segment-tree.cpp"
using namespace std;

template <class S, class F, S (*mapping)(F, S), F (*composition)(F, F),
          F (*id)()>
class DualSegmentTree {
    int _n, sz, lg;
    vector<S> data;
    vector<F> lazy;

    void _push(int k, F f) {
        if(k < sz)
            lazy[k] = composition(f, lazy[k]);
        else
            data[k - sz] = mapping(f, data[k - sz]);
    }
    void push(int k) {
        _push(k << 1, lazy[k]);
        _push(k << 1 | 1, lazy[k]);
        lazy[k] = id();
    }

public:
    DualSegmentTree() = default;
    explicit DualSegmentTree(const vector<S>& v) : _n(v.size()) {
        lg = 0;
        while(1U << lg < (uint)_n) lg++;
        sz = 1 << lg;
        data = v;
        data.resize(sz);
        lazy.assign(sz, id());
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += sz;
        for(int i = lg; i >= 1; i--) push(p >> i);
        data[p - sz] = x;
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += sz;
        for(int i = lg; i >= 1; i--) push(p >> i);
        return data[p - sz];
    }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += sz;
        for(int i = lg; i >= 1; i--) push(p >> i);
        data[p - sz] = mapping(f, data[p]);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if(l == r) return;
        l += sz;
        r += sz;

        for(int i = lg; i >= 1; i--) {
            if(((l >> i) << i) != l) push(l >> i);
            if(((r >> i) << i) != r) push((r - 1) >> i);
        }

        while(l < r) {
            if(l & 1) _push(l++, f);
            if(r & 1) _push(--r, f);
            l >>= 1;
            r >>= 1;
        }
    }
};
/*
 * @brief Dual-Segment-Tree
 * @docs docs/dual-segment-tree.md
 */
#line 8 "test/AOJ-DLS-2-D.test.cpp"

using S = int;
using F = int;
F id() { return -1; }
S mapping(F f, S s) { return f == id() ? s : f; }
F composition(F f, F g) { return f == id() ? g : f; }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;

    DualSegmentTree<S, F, mapping, composition, id> seg(vector<S>(n, INT_MAX));

    for(int i = 0; i < q; i++) {
        int t;
        cin >> t;
        if(t) {
            int p;
            cin >> p;
            cout << seg.get(p) << "\n";
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            seg.apply(l, r + 1, x);
        }
    }

    return 0;
}

Back to top page