This documentation is automatically generated by online-judge-tools/verification-helper
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1508
#include "../../template/template.hpp"
#include "../../other/vector-pool.hpp"
#include "../../structure/bbst/weight-balanced-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); };
WeightBalancedTree< 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-3.test.cpp"
// competitive-verifier: 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 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-3.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/weight-balanced-tree.hpp"
/**
* @brief Weight-Balanced-Tree(重み平衡木)
*/
template <typename Monoid, typename F>
struct WeightBalancedTree {
public:
struct Node {
Node *l, *r;
int cnt;
Monoid key, sum;
Node() {}
Node(const Monoid &k) : key(k), sum(k), l(nullptr), r(nullptr), cnt(1) {}
Node(Node *l, Node *r, const Monoid &k) : key(k), l(l), r(r) {}
bool is_leaf() { return !l || !r; }
};
private:
Node *update(Node *t) {
t->cnt = count(t->l) + count(t->r) + t->is_leaf();
t->sum = f(f(sum(t->l), t->key), sum(t->r));
return t;
}
inline Node *alloc(Node *l, Node *r) {
auto t = &(*pool.alloc() = Node(l, r, M1));
return update(t);
}
Node *submerge(Node *l, Node *r) {
if (count(l) > count(r) * 4) {
l = clone(l);
auto nl = clone(l->l);
auto nr = submerge(l->r, r);
if (count(nl) * 4 >= count(nr)) {
l->r = nr;
return update(l);
}
if (count(nr->l) * 3 <= count(nr->r) * 5) {
l->r = nr->l;
nr->l = l;
update(l);
return update(nr);
}
Node *t = clone(nr->l);
l->r = nr->l->l;
update(l);
nr->l = nr->l->r;
update(nr);
t->l = l;
t->r = nr;
return update(t);
}
if (count(l) * 4 < count(r)) {
r = clone(r);
auto nl = submerge(l, r->l);
auto nr = clone(r->r);
if (count(nl) <= count(nr) * 4) {
r->l = nl;
return update(r);
}
if (count(nl->l) * 5 >= count(nl->r) * 3) {
r->l = nl->r;
nl->r = r;
update(r);
return update(nl);
}
Node *t = clone(nl->r);
r->l = nl->r->r;
update(r);
nl->r = nl->r->l;
update(nl);
t->r = r;
t->l = nl;
return update(t);
}
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));
}
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);
}
virtual Node *clone(Node *t) { return t; }
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;
WeightBalancedTree(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)); }
static 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;
return submerge(l, r);
}
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->c;
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-3.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); };
WeightBalancedTree< 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);
}
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | testcase_00 | AC | 7 ms | 4 MB |
g++ | testcase_01 | AC | 6 ms | 4 MB |
g++ | testcase_02 | AC | 6 ms | 4 MB |
g++ | testcase_03 | AC | 6 ms | 4 MB |
g++ | testcase_04 | AC | 6 ms | 4 MB |
g++ | testcase_05 | AC | 6 ms | 4 MB |
g++ | testcase_06 | AC | 6 ms | 4 MB |
g++ | testcase_07 | AC | 6 ms | 4 MB |
g++ | testcase_08 | AC | 7 ms | 4 MB |
g++ | testcase_09 | AC | 6 ms | 4 MB |
g++ | testcase_10 | AC | 6 ms | 4 MB |
g++ | testcase_11 | AC | 6 ms | 4 MB |
g++ | testcase_12 | AC | 6 ms | 4 MB |
g++ | testcase_13 | AC | 7 ms | 4 MB |
g++ | testcase_14 | AC | 7 ms | 4 MB |
g++ | testcase_15 | AC | 7 ms | 4 MB |
g++ | testcase_16 | AC | 7 ms | 4 MB |
g++ | testcase_17 | AC | 7 ms | 4 MB |
g++ | testcase_18 | AC | 7 ms | 4 MB |
g++ | testcase_19 | AC | 8 ms | 4 MB |
g++ | testcase_20 | AC | 8 ms | 4 MB |
g++ | testcase_21 | AC | 7 ms | 4 MB |
g++ | testcase_22 | AC | 7 ms | 4 MB |
g++ | testcase_23 | AC | 6 ms | 4 MB |
g++ | testcase_24 | AC | 6 ms | 4 MB |
g++ | testcase_25 | AC | 6 ms | 4 MB |
g++ | testcase_26 | AC | 6 ms | 4 MB |
g++ | testcase_27 | AC | 6 ms | 4 MB |
g++ | testcase_28 | AC | 7 ms | 4 MB |
g++ | testcase_29 | AC | 6 ms | 4 MB |
g++ | testcase_30 | AC | 7 ms | 4 MB |
g++ | testcase_31 | AC | 8 ms | 4 MB |
g++ | testcase_32 | AC | 29 ms | 7 MB |
g++ | testcase_33 | AC | 45 ms | 9 MB |
g++ | testcase_34 | AC | 91 ms | 15 MB |
g++ | testcase_35 | AC | 101 ms | 27 MB |
g++ | testcase_36 | AC | 171 ms | 31 MB |
g++ | testcase_37 | AC | 14 ms | 4 MB |
g++ | testcase_38 | AC | 13 ms | 4 MB |
g++ | testcase_39 | AC | 15 ms | 4 MB |
g++ | testcase_40 | AC | 14 ms | 4 MB |
g++ | testcase_41 | AC | 13 ms | 4 MB |
g++ | testcase_42 | AC | 14 ms | 4 MB |
g++ | testcase_43 | AC | 13 ms | 4 MB |
g++ | testcase_44 | AC | 13 ms | 4 MB |
g++ | testcase_45 | AC | 13 ms | 4 MB |
g++ | testcase_46 | AC | 14 ms | 5 MB |
g++ | testcase_47 | AC | 29 ms | 7 MB |
g++ | testcase_48 | AC | 28 ms | 7 MB |
g++ | testcase_49 | AC | 29 ms | 7 MB |
g++ | testcase_50 | AC | 46 ms | 9 MB |
g++ | testcase_51 | AC | 46 ms | 9 MB |
g++ | testcase_52 | AC | 46 ms | 9 MB |
g++ | testcase_53 | AC | 208 ms | 27 MB |
g++ | testcase_54 | AC | 194 ms | 27 MB |
g++ | testcase_55 | AC | 194 ms | 27 MB |
g++ | testcase_56 | AC | 196 ms | 27 MB |
g++ | testcase_57 | AC | 196 ms | 27 MB |
g++ | testcase_58 | AC | 211 ms | 27 MB |
g++ | testcase_59 | AC | 192 ms | 27 MB |
g++ | testcase_60 | AC | 223 ms | 27 MB |
g++ | testcase_61 | AC | 208 ms | 27 MB |
g++ | testcase_62 | AC | 204 ms | 27 MB |
clang++ | testcase_00 | AC | 7 ms | 4 MB |
clang++ | testcase_01 | AC | 6 ms | 4 MB |
clang++ | testcase_02 | AC | 7 ms | 4 MB |
clang++ | testcase_03 | AC | 7 ms | 4 MB |
clang++ | testcase_04 | AC | 6 ms | 4 MB |
clang++ | testcase_05 | AC | 7 ms | 4 MB |
clang++ | testcase_06 | AC | 7 ms | 4 MB |
clang++ | testcase_07 | AC | 7 ms | 4 MB |
clang++ | testcase_08 | AC | 6 ms | 4 MB |
clang++ | testcase_09 | AC | 6 ms | 4 MB |
clang++ | testcase_10 | AC | 6 ms | 4 MB |
clang++ | testcase_11 | AC | 7 ms | 4 MB |
clang++ | testcase_12 | AC | 6 ms | 4 MB |
clang++ | testcase_13 | AC | 7 ms | 4 MB |
clang++ | testcase_14 | AC | 7 ms | 4 MB |
clang++ | testcase_15 | AC | 7 ms | 4 MB |
clang++ | testcase_16 | AC | 7 ms | 4 MB |
clang++ | testcase_17 | AC | 7 ms | 4 MB |
clang++ | testcase_18 | AC | 7 ms | 4 MB |
clang++ | testcase_19 | AC | 7 ms | 4 MB |
clang++ | testcase_20 | AC | 7 ms | 4 MB |
clang++ | testcase_21 | AC | 7 ms | 4 MB |
clang++ | testcase_22 | AC | 7 ms | 4 MB |
clang++ | testcase_23 | AC | 6 ms | 4 MB |
clang++ | testcase_24 | AC | 7 ms | 4 MB |
clang++ | testcase_25 | AC | 7 ms | 4 MB |
clang++ | testcase_26 | AC | 6 ms | 4 MB |
clang++ | testcase_27 | AC | 6 ms | 4 MB |
clang++ | testcase_28 | AC | 6 ms | 4 MB |
clang++ | testcase_29 | AC | 6 ms | 4 MB |
clang++ | testcase_30 | AC | 7 ms | 4 MB |
clang++ | testcase_31 | AC | 7 ms | 4 MB |
clang++ | testcase_32 | AC | 31 ms | 7 MB |
clang++ | testcase_33 | AC | 50 ms | 9 MB |
clang++ | testcase_34 | AC | 103 ms | 15 MB |
clang++ | testcase_35 | AC | 135 ms | 27 MB |
clang++ | testcase_36 | AC | 232 ms | 31 MB |
clang++ | testcase_37 | AC | 15 ms | 4 MB |
clang++ | testcase_38 | AC | 13 ms | 4 MB |
clang++ | testcase_39 | AC | 14 ms | 4 MB |
clang++ | testcase_40 | AC | 13 ms | 4 MB |
clang++ | testcase_41 | AC | 14 ms | 4 MB |
clang++ | testcase_42 | AC | 14 ms | 4 MB |
clang++ | testcase_43 | AC | 14 ms | 4 MB |
clang++ | testcase_44 | AC | 13 ms | 4 MB |
clang++ | testcase_45 | AC | 14 ms | 4 MB |
clang++ | testcase_46 | AC | 14 ms | 4 MB |
clang++ | testcase_47 | AC | 30 ms | 7 MB |
clang++ | testcase_48 | AC | 31 ms | 7 MB |
clang++ | testcase_49 | AC | 32 ms | 7 MB |
clang++ | testcase_50 | AC | 50 ms | 9 MB |
clang++ | testcase_51 | AC | 50 ms | 9 MB |
clang++ | testcase_52 | AC | 50 ms | 9 MB |
clang++ | testcase_53 | AC | 219 ms | 27 MB |
clang++ | testcase_54 | AC | 230 ms | 27 MB |
clang++ | testcase_55 | AC | 236 ms | 27 MB |
clang++ | testcase_56 | AC | 237 ms | 27 MB |
clang++ | testcase_57 | AC | 229 ms | 27 MB |
clang++ | testcase_58 | AC | 238 ms | 27 MB |
clang++ | testcase_59 | AC | 230 ms | 27 MB |
clang++ | testcase_60 | AC | 221 ms | 27 MB |
clang++ | testcase_61 | AC | 231 ms | 27 MB |
clang++ | testcase_62 | AC | 219 ms | 27 MB |