test/aoj/1508.rbst.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 01:52:54+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1508

Depends on

• Randomized Binary Search Tree (data-structure/bst/rbst.hpp)

Code

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

#include <bits/stdc++.h>

#include "../../data-structure/bst/rbst.hpp"
using namespace std;

struct MinMonoid {
    using T = int;
    static T op() { return (1u << 31) - 1; }
    static T op(T a, T b) { return min(a, b); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    using ST = RBST<MinMonoid>;
    ST st;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        st.push_back(a);
    }
    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;
        if (x == 0) {
            st.reverse(y, z + 1);
            st.reverse(y + 1, z + 1);
        } else if (x == 1) {
            cout << st.fold(y, z + 1) << "\n";
        } else {
            st.update(y, z);
        }
    }
}

#line 1 "test/aoj/1508.rbst.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1508"

#include <bits/stdc++.h>

#line 6 "data-structure/bst/rbst.hpp"

template <typename M>
class RBST {
    using T = typename M::T;

   public:
    RBST() = default;

    static RBST join(RBST l, RBST r) {
        return RBST(join(std::move(l.root), std::move(r.root)));
    }

    std::pair<RBST, RBST> split(int k) {
        auto p = split(std::move(root), k);
        return {RBST(std::move(p.first)), RBST(std::move(p.second))};
    }

    void update(int k, const T& x) const { update(root, k, x); }

    T fold(int l, int r) {
        assert(0 <= l && l < r && r <= size());
        node_ptr a, b, c;
        std::tie(a, b) = split(std::move(root), l);
        std::tie(b, c) = split(std::move(b), r - l);
        auto ret = b->sum;
        root = join(join(std::move(a), std::move(b)), std::move(c));
        return ret;
    }

    void reverse(int l, int r) {
        assert(0 <= l && l < r && r <= size());
        node_ptr a, b, c;
        std::tie(a, b) = split(std::move(root), l);
        std::tie(b, c) = split(std::move(b), r - l);
        b->rev ^= true;
        root = join(join(std::move(a), std::move(b)), std::move(c));
    }

    void insert(int k, const T& x) {
        auto s = split(std::move(root), k);
        root = join(join(std::move(s.first), std::make_unique<Node>(x)),
                    std::move(s.second));
    }

    void erase(int k) {
        auto p = split(std::move(root), k);
        auto q = split(std::move(p.second), 1);
        return join(std::move(p.first), std::move(q.second));
    }

    void push_front(const T& x) {
        root = join(std::make_unique<Node>(x), std::move(root));
    }

    void push_back(const T& x) {
        root = join(std::move(root), std::make_unique<Node>(x));
    }

    void pop_front() { root = split(std::move(root), 1).second; }

    void pop_back() { root = split(std::move(root), size() - 1).first; }

    int size() const { return size(root); }

    bool empty() const { return size() == 0; }

   private:
    struct Node;
    using node_ptr = std::unique_ptr<Node>;

    static unsigned int rand() {
        static std::random_device rd;
        static std::mt19937 rng(rd());
        return rng();
    }

    struct Node {
        node_ptr left, right;
        T val, sum;
        int sz;
        bool rev;

        Node() : Node(M::id()) {}
        Node(const T& x)
            : left(nullptr),
              right(nullptr),
              val(x),
              sum(val),
              sz(1),
              rev(false) {}
    };

    node_ptr root;

    explicit RBST(node_ptr root) : root(std::move(root)) {}

    static int size(const node_ptr& t) { return t ? t->sz : 0; }

    static void recalc(const node_ptr& t) {
        if (!t) return;
        t->sz = size(t->left) + 1 + size(t->right);
        t->sum = t->val;
        if (t->left) t->sum = M::op(t->left->sum, t->sum);
        if (t->right) t->sum = M::op(t->sum, t->right->sum);
    }

    static void push(const node_ptr& t) {
        if (t->rev) {
            std::swap(t->left, t->right);
            if (t->left) t->left->rev ^= true;
            if (t->right) t->right->rev ^= true;
            t->rev = false;
        }
    }

    static node_ptr join(node_ptr l, node_ptr r) {
        if (!l) return r;
        if (!r) return l;
        push(l);
        push(r);
        if ((int)(rand() % (size(l) + size(r))) < size(l)) {
            l->right = join(std::move(l->right), std::move(r));
            recalc(l);
            return l;
        } else {
            r->left = join(std::move(l), std::move(r->left));
            recalc(r);
            return r;
        }
    }

    static std::pair<node_ptr, node_ptr> split(node_ptr t, int k) {
        assert(0 <= k && k <= size(t));
        if (k == 0) return {nullptr, std::move(t)};
        if (k == size(t)) return {std::move(t), nullptr};
        push(t);
        if (k <= size(t->left)) {
            auto s = split(std::move(t->left), k);
            t->left = std::move(s.second);
            recalc(t);
            return {std::move(s.first), std::move(t)};
        } else {
            auto s = split(std::move(t->right), k - size(t->left) - 1);
            t->right = std::move(s.first);
            recalc(t);
            return {std::move(t), std::move(s.second)};
        }
    }

    static void update(const node_ptr& t, int k, const T& x) {
        push(t);
        int lsize = size(t->left);
        if (k < lsize) {
            update(t->left, k, x);
        } else if (lsize < k) {
            update(t->right, k - lsize - 1, x);
        } else {
            t->val = x;
        }
        recalc(t);
    }
};
#line 6 "test/aoj/1508.rbst.test.cpp"
using namespace std;

struct MinMonoid {
    using T = int;
    static T op() { return (1u << 31) - 1; }
    static T op(T a, T b) { return min(a, b); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    using ST = RBST<MinMonoid>;
    ST st;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        st.push_back(a);
    }
    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;
        if (x == 0) {
            st.reverse(y, z + 1);
            st.reverse(y + 1, z + 1);
        } else if (x == 1) {
            cout << st.fold(y, z + 1) << "\n";
        } else {
            st.update(y, z);
        }
    }
}

Back to top page