cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
test/src/datastructure/deque_aggregation/staticrmq.test.cpp
- View this file on GitHub
- Last update: 2023-07-09 04:04:16+09:00
- Problem: https://judge.yosupo.jp/problem/staticrmq
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <iostream>
#include "library/algorithm/mo.hpp"
#include "library/datastructure/deque_aggregation.hpp"
int op(int x, int y) {
return std::min(x, y);
}
int e() {
return 1000000000;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<int> a(n);
for (auto &e : a) std::cin >> e;
std::vector<std::pair<int, int>> queries(q);
for (int i = 0; i < q; ++i) {
int l, r;
std::cin >> l >> r;
queries[i] = { l, r };
}
suisen::DequeAggregation<int, op, e> dq;
auto ans = suisen::Mo{ n, queries }.solve(
[&] { return dq.prod(); },
[&](int l) { dq.push_front(a[l]); },
[&](int) { dq.pop_front(); },
[&](int r) { dq.push_back(a[r]); },
[&](int) { dq.pop_back(); }
);
for (int v : ans) std::cout << v << '\n';
return 0;
}#line 1 "test/src/datastructure/deque_aggregation/staticrmq.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <iostream>
#line 1 "library/algorithm/mo.hpp"
#include <algorithm>
#include <cmath>
#include <numeric>
#include <vector>
namespace suisen {
struct Mo {
Mo() = default;
Mo(const int n, const std::vector<std::pair<int, int>> &queries) : n(n), q(queries.size()), b(bucket_size(n, q)), qs(queries), ord(q) {
std::iota(ord.begin(), ord.end(), 0);
std::sort(
ord.begin(), ord.end(),
[&, this](int i, int j) {
const auto &[li, ri] = qs[i];
const auto &[lj, rj] = qs[j];
const int bi = li / b, bj = lj / b;
if (bi != bj) return bi < bj;
if (ri != rj) return bi & 1 ? ri > rj : ri < rj;
return li < lj;
}
);
}
// getter methods used in updating functions: AddL, DelL, etc.
auto get_left() const { return l; }
auto get_right() const { return r; }
auto get_range() const { return std::make_pair(l, r); }
auto get_query_id() const { return query_id; }
/**
* [Parameters]
* Eval : () -> T : return the current answer
* AddL : int -> any (discarded) : add `l` to the current range [l + 1, r)
* DelL : int -> any (discarded) : delete `l` from the current range [l, r)
* AddR : int -> any (discarded) : add `r` to the current range [l, r)
* DelR : int -> any (discarded) : delete `r` from the current range [l, r + 1)
*
* [Note]
* starting from the range [0, 0).
*/
template <typename Eval, typename AddL, typename DelL, typename AddR, typename DelR>
auto solve(Eval eval, AddL add_l, DelL del_l, AddR add_r, DelR del_r) {
l = 0, r = 0;
std::vector<decltype(eval())> res(q);
for (int qi : ord) {
const auto &[nl, nr] = qs[query_id = qi];
while (r < nr) add_r(r), ++r;
while (l > nl) --l, add_l(l);
while (r > nr) --r, del_r(r);
while (l < nl) del_l(l), ++l;
res[qi] = eval();
}
return res;
}
/**
* [Parameters]
* Eval : () -> T : return the current answer
* Add : int -> any (discarded) : add `i` to the current range [i + 1, r) or [l, i)
* Del : int -> any (discarded) : delete `i` from the current range [i, r) or [l, i + 1)
*
* [Note]
* starting from the range [0, 0).
*/
template <typename Eval, typename Add, typename Del>
auto solve(Eval eval, Add add, Del del) {
return solve(eval, add, del, add, del);
}
private:
int n, q, b;
int query_id = -1;
std::vector<std::pair<int, int>> qs;
std::vector<int> ord;
int l = 0, r = 0;
static int bucket_size(int n, int q) {
return std::max(1, int(::sqrt(3) * n / ::sqrt(std::max(1, 2 * q))));
}
};
} // namespace suisen
#line 1 "library/datastructure/deque_aggregation.hpp"
#include <cassert>
#line 6 "library/datastructure/deque_aggregation.hpp"
/**
* [Idea] reference : https://motsu-xe.hatenablog.com/entry/2021/05/13/224016
*
* SWAG + simulate a deque with 2 stacks
*
* [Operations] reference : https://www.slideshare.net/catupper/amortize-analysis-of-deque-with-2-stack
*
* `l`, `r` is a stack of { value, sum }
*
* accumulate
* <---------- ------> fold values from inside
* ( l ][ r )
*
* pop_front:
* 1. `l` is not empty
* ( l ][ r ) -> ( l ][ r ) # pop from `l`. O(1)
* 2. `l` is empty
* (][ r ) -> ( l ][ r ) # split `r` at its middle point. amortized O(1)
* ( l ][ r ) -> ( l ][ r ) # pop from `l`. O(1)
*
* pop_back:
* 1. `r` is not empty
* ( l ][ r ) -> ( l ][ r ) # pop from `r`. O(1)
* 2. `r` is empty
* ( l ][) -> ( l ][ r ) # split `l` at its middle point. amortized O(1)
* ( l ][ r ) -> ( l ][ r ) # pop from `r`. O(1)
*
* push_front:
* ( l ][ r ) -> ( l ][ r ) # push to `l`. O(1)
*
* push_back:
* ( l ][ r ) -> ( l ][ r ) # push to `r`. O(1)
*/
namespace suisen {
template <typename T, T(*op)(T, T), T(*e)()>
struct DequeAggregation {
struct DequeAggregationIterator {
using difference_type = int;
using value_type = T;
using pointer = value_type*;
using reference = value_type&;
using iterator_category = std::random_access_iterator_tag;
using fi_iterator_type = typename std::vector<std::pair<value_type, value_type>>::const_reverse_iterator;
using se_iterator_type = typename std::vector<std::pair<value_type, value_type>>::const_iterator;
fi_iterator_type it_l;
fi_iterator_type it_l_end;
se_iterator_type it_r_begin;
se_iterator_type it_r;
DequeAggregationIterator& operator++() {
if (it_l == it_l_end) ++it_r;
else ++it_l;
return *this;
}
DequeAggregationIterator operator++(int) { DequeAggregationIterator ret = *this; ++(*this); return ret; }
DequeAggregationIterator& operator--() {
if (it_r == it_r_begin) --it_l;
else --it_r;
return *this;
}
DequeAggregationIterator operator--(int) { DequeAggregationIterator ret = *this; --(*this); return ret; }
DequeAggregationIterator& operator+=(difference_type dif) {
if (dif < 0) return *this -= -dif;
if (int d = it_l_end - it_l; d < dif) it_l = it_l_end, it_r += dif - d;
else it_l += dif;
return *this;
}
friend DequeAggregationIterator operator+(DequeAggregationIterator it, difference_type dif) { it += dif; return it; }
friend DequeAggregationIterator operator+(difference_type dif, DequeAggregationIterator it) { it += dif; return it; }
DequeAggregationIterator& operator-=(difference_type dif) {
if (dif < 0) return *this += -dif;
if (int d = it_r - it_r_begin; d < dif) it_r = it_r_begin, it_l -= dif - d;
else it_r -= dif;
return *this;
}
friend DequeAggregationIterator operator-(DequeAggregationIterator it, difference_type dif) { it -= dif; return it; }
difference_type operator-(const DequeAggregationIterator &rhs) const {
difference_type d1 = it_l == it_l_end ? it_r - it_r_begin : it_l - it_l_end;
difference_type d2 = rhs.it_l == rhs.it_l_end ? rhs.it_r - rhs.it_r_begin : rhs.it_l - rhs.it_l_end;
return d1 - d2;
}
const value_type& operator[](difference_type i) const { return *((*this) + i); }
const value_type& operator*() const { return it_l == it_l_end ? it_r->first : it_l->first; }
bool operator!=(const DequeAggregationIterator &rhs) const { return it_l != rhs.it_l or it_r != rhs.it_r; }
bool operator==(const DequeAggregationIterator &rhs) const { return not (*this != rhs); }
bool operator< (const DequeAggregationIterator &rhs) const { return (*this) - rhs < 0; }
bool operator<=(const DequeAggregationIterator &rhs) const { return (*this) - rhs <= 0; }
bool operator> (const DequeAggregationIterator &rhs) const { return (*this) - rhs > 0; }
bool operator>=(const DequeAggregationIterator &rhs) const { return (*this) - rhs >= 0; }
};
using iterator = DequeAggregationIterator;
using difference_type = typename iterator::difference_type;
using value_type = typename iterator::value_type;
using pointer = typename iterator::pointer;
using reference = typename iterator::reference;
DequeAggregation() = default;
template <typename InputIterator, std::enable_if_t<std::is_constructible_v<value_type, typename InputIterator::value_type>, std::nullptr_t> = nullptr>
DequeAggregation(InputIterator first, InputIterator last) {
for (; first != last; ++first) push_back(*first);
}
template <typename Container, std::enable_if_t<std::is_constructible_v<value_type, typename Container::value_type>, std::nullptr_t> = nullptr>
DequeAggregation(const Container &c) : DequeAggregation(std::begin(c), std::end(c)) {}
value_type prod() const {
return op(prod(_st_l), prod(_st_r));
}
void push_back(const value_type &val) { _st_r.emplace_back(val, op(prod(_st_r), val)); }
void push_front(const value_type &val) { _st_l.emplace_back(val, op(val, prod(_st_l))); }
void pop_back() {
if (_st_r.size()) return _st_r.pop_back();
const int siz = _st_l.size();
const int l = siz >> 1, r = siz - l;
assert(r); // <=> siz > 0
for (int i = r - 1; i > 0; --i) push_back(std::move(_st_l[i].first));
_st_l.erase(_st_l.begin(), _st_l.begin() + r);
if (l == 0) return;
_st_l[0].second = _st_l[0].first;
for (int i = 1; i < l; ++i) _st_l[i].second = op(_st_l[i].first, _st_l[i - 1].second);
}
void pop_front() {
if (_st_l.size()) return _st_l.pop_back();
const int siz = _st_r.size();
const int r = siz >> 1, l = siz - r;
assert(l); // <=> siz > 0
for (int i = l - 1; i > 0; --i) push_front(std::move(_st_r[i].first));
_st_r.erase(_st_r.begin(), _st_r.begin() + l);
if (r == 0) return;
_st_r[0].second = _st_r[0].first;
for (int i = 1; i < r; ++i) _st_r[i].second = op(_st_r[i - 1].second, _st_r[i].first);
}
const value_type& front() const { return _st_l.size() ? _st_l.back().first : _st_r.front().first; }
const value_type& back() const { return _st_r.size() ? _st_r.back().first : _st_l.front().first; }
const value_type& operator[](int i) const {
const int k = i - _st_l.size();
return k < 0 ? _st_l[~k].first : _st_r[k].first;
}
int size() const { return _st_l.size() + _st_r.size(); }
void clear() { _st_l.clear(), _st_r.clear(); }
void shrink_to_fit() { _st_l.shrink_to_fit(), _st_r.shrink_to_fit(); }
iterator begin() const { return iterator { _st_l.rbegin(), _st_l.rend(), _st_r.begin(), _st_r.begin() }; }
iterator end() const { return iterator { _st_l.rend(), _st_l.rend(), _st_r.begin(), _st_r.end() }; }
iterator cbegin() const { return begin(); }
iterator cend() const { return end(); }
private:
std::vector<std::pair<value_type, value_type>> _st_l, _st_r;
value_type prod(const std::vector<std::pair<value_type, value_type>> &st) const {
return st.empty() ? e() : st.back().second;
}
};
} // namespace suisen
#line 7 "test/src/datastructure/deque_aggregation/staticrmq.test.cpp"
int op(int x, int y) {
return std::min(x, y);
}
int e() {
return 1000000000;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<int> a(n);
for (auto &e : a) std::cin >> e;
std::vector<std::pair<int, int>> queries(q);
for (int i = 0; i < q; ++i) {
int l, r;
std::cin >> l >> r;
queries[i] = { l, r };
}
suisen::DequeAggregation<int, op, e> dq;
auto ans = suisen::Mo{ n, queries }.solve(
[&] { return dq.prod(); },
[&](int l) { dq.push_front(a[l]); },
[&](int) { dq.pop_front(); },
[&](int r) { dq.push_back(a[r]); },
[&](int) { dq.pop_back(); }
);
for (int v : ans) std::cout << v << '\n';
return 0;
}