This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ei1333/library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1508" #include "../../template/template.hpp" #include "../../other/vector-pool.hpp" #include "../../structure/bbst/red-black-tree.hpp" int main() { int N, Q; cin >> N >> Q; vector< int > A(N); for(auto &a : A) cin >> a; auto f = [](int a, int b) { return min(a, b); }; RedBlackTree< int, decltype(f) > rbt((N + Q) * 2, f, inf); auto V = rbt.build(A); while(Q--) { int X, Y, Z; cin >> X >> Y >> Z; if(X == 0) { auto S = rbt.split3(V, Y, Z + 1); auto val = rbt.pop_back(get< 1 >(S)); rbt.push_front(get< 1 >(S), val); V = rbt.merge(get< 0 >(S), get< 1 >(S), get< 2 >(S)); } else if(X == 1) { cout << rbt.query(V, Y, Z + 1) << "\n"; } else { rbt.set_element(V, Y, Z); } } }
#line 1 "test/verify/aoj-1508-2.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1508" #line 1 "template/template.hpp" #include<bits/stdc++.h> using namespace std; using int64 = long long; const int mod = 1e9 + 7; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); } template< typename F > struct FixPoint : F { explicit FixPoint(F &&f) : F(forward< F >(f)) {} template< typename... Args > decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, forward< Args >(args)...); } }; template< typename F > inline decltype(auto) MFP(F &&f) { return FixPoint< F >{forward< F >(f)}; } #line 4 "test/verify/aoj-1508-2.test.cpp" #line 1 "other/vector-pool.hpp" template< class T > struct VectorPool { vector< T > pool; vector< T * > stock; int ptr; VectorPool() = default; VectorPool(int sz) : pool(sz), stock(sz) {} inline T *alloc() { return stock[--ptr]; } inline void free(T *t) { stock[ptr++] = t; } void clear() { ptr = (int) pool.size(); for(int i = 0; i < pool.size(); i++) stock[i] = &pool[i]; } }; #line 1 "structure/bbst/red-black-tree.hpp" /** * @brief Red-Black-Tree(赤黒木) * @docs docs/red-black-tree.md */ template< typename Monoid, typename F > struct RedBlackTree { public: enum COLOR { BLACK, RED }; struct Node { Node *l, *r; COLOR color; int level, cnt; Monoid key, sum; Node() {} Node(const Monoid &k) : key(k), sum(k), l(nullptr), r(nullptr), color(BLACK), level(0), cnt(1) {} Node(Node *l, Node *r, const Monoid &k) : key(k), color(RED), l(l), r(r) {} bool is_leaf() const { return l == nullptr; } }; private: inline Node *alloc(Node *l, Node *r) { auto t = &(*pool.alloc() = Node(l, r, M1)); return update(t); } virtual Node *clone(Node *t) { return t; } Node *rotate(Node *t, bool b) { t = clone(t); Node *s; if(b) { s = clone(t->l); t->l = s->r; s->r = t; } else { s = clone(t->r); t->r = s->l; s->l = t; } update(t); return update(s); } Node *submerge(Node *l, Node *r) { if(l->level < r->level) { r = clone(r); Node *c = (r->l = submerge(l, r->l)); if(r->color == BLACK && c->color == RED && c->l && c->l->color == RED) { r->color = RED; c->color = BLACK; if(r->r->color == BLACK) return rotate(r, true); r->r->color = BLACK; } return update(r); } if(l->level > r->level) { l = clone(l); Node *c = (l->r = submerge(l->r, r)); if(l->color == BLACK && c->color == RED && c->r && c->r->color == RED) { l->color = RED; c->color = BLACK; if(l->l->color == BLACK) return rotate(l, false); l->l->color = BLACK; } return update(l); } return alloc(l, r); } Node *build(int l, int r, const vector< Monoid > &v) { if(l + 1 >= r) return alloc(v[l]); return merge(build(l, (l + r) >> 1, v), build((l + r) >> 1, r, v)); } Node *update(Node *t) { t->cnt = count(t->l) + count(t->r) + (!t->l || !t->r); t->level = t->l ? t->l->level + (t->l->color == BLACK) : 0; t->sum = f(f(sum(t->l), t->key), sum(t->r)); return t; } void dump(Node *r, typename vector< Monoid >::iterator &it) { if(r->is_leaf()) { *it++ = r->key; return; } dump(r->l, it); dump(r->r, it); } Node *merge(Node *l) { return l; } Monoid query(Node *t, int a, int b, int l, int r) { if(r <= a || b <= l) return M1; if(a <= l && r <= b) return t->sum; return f(query(t->l, a, b, l, l + count(t->l)), query(t->r, a, b, r - count(t->r), r)); } public: VectorPool< Node > pool; const F f; const Monoid M1; RedBlackTree(int sz, const F &f, const Monoid &M1) : pool(sz), M1(M1), f(f) { pool.clear(); } inline Node *alloc(const Monoid &key) { return &(*pool.alloc() = Node(key)); } inline int count(const Node *t) { return t ? t->cnt : 0; } inline const Monoid &sum(const Node *t) { return t ? t->sum : M1; } pair< Node *, Node * > split(Node *t, int k) { if(!t) return {nullptr, nullptr}; if(k == 0) return {nullptr, t}; if(k >= count(t)) return {t, nullptr}; t = clone(t); Node *l = t->l, *r = t->r; pool.free(t); if(k < count(l)) { auto pp = split(l, k); return {pp.first, merge(pp.second, r)}; } if(k > count(l)) { auto pp = split(r, k - count(l)); return {merge(l, pp.first), pp.second}; } return {l, r}; } tuple< Node *, Node *, Node * > split3(Node *t, int a, int b) { auto x = split(t, a); auto y = split(x.second, b - a); return make_tuple(x.first, y.first, y.second); } template< typename ... Args > Node *merge(Node *l, Args ...rest) { Node *r = merge(rest...); if(!l || !r) return l ? l : r; Node *c = submerge(l, r); c->color = BLACK; return c; } Node *build(const vector< Monoid > &v) { return build(0, (int) v.size(), v); } vector< Monoid > dump(Node *r) { vector< Monoid > v((size_t) count(r)); auto it = begin(v); dump(r, it); return v; } string to_string(Node *r) { auto s = dump(r); string ret; for(int i = 0; i < s.size(); i++) { ret += std::to_string(s[i]); ret += ", "; } return ret; } void insert(Node *&t, int k, const Monoid &v) { auto x = split(t, k); t = merge(merge(x.first, alloc(v)), x.second); } Monoid erase(Node *&t, int k) { auto x = split(t, k); auto y = split(x.second, 1); auto v = y.first->key; pool.free(y.first); t = merge(x.first, y.second); return v; } Monoid query(Node *t, int a, int b) { return query(t, a, b, 0, count(t)); } void set_element(Node *&t, int k, const Monoid &x) { t = clone(t); if(t->is_leaf()) { t->key = t->sum = x; return; } if(k < count(t->l)) set_element(t->l, k, x); else set_element(t->r, k - count(t->l), x); t = update(t); } void push_front(Node *&t, const Monoid &v) { t = merge(alloc(v), t); } void push_back(Node *&t, const Monoid &v) { t = merge(t, alloc(v)); } Monoid pop_front(Node *&t) { auto ret = split(t, 1); t = ret.second; return ret.first->key; } Monoid pop_back(Node *&t) { auto ret = split(t, count(t) - 1); t = ret.first; return ret.second->key; } }; #line 7 "test/verify/aoj-1508-2.test.cpp" int main() { int N, Q; cin >> N >> Q; vector< int > A(N); for(auto &a : A) cin >> a; auto f = [](int a, int b) { return min(a, b); }; RedBlackTree< int, decltype(f) > rbt((N + Q) * 2, f, inf); auto V = rbt.build(A); while(Q--) { int X, Y, Z; cin >> X >> Y >> Z; if(X == 0) { auto S = rbt.split3(V, Y, Z + 1); auto val = rbt.pop_back(get< 1 >(S)); rbt.push_front(get< 1 >(S), val); V = rbt.merge(get< 0 >(S), get< 1 >(S), get< 2 >(S)); } else if(X == 1) { cout << rbt.query(V, Y, Z + 1) << "\n"; } else { rbt.set_element(V, Y, Z); } } }