#line 1 "test/yc_878_reversed.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/878" #include #include #include #line 1 "DataStructure/basic_segment_tree.cpp" /** * @brief 単一更新セグメント木 * @author えびちゃん */ #include #line 12 "DataStructure/basic_segment_tree.cpp" template class basic_segment_tree { public: using value_type = Monoid; using size_type = size_t; private: std::vector M_c; size_type M_n; std::vector M_covering_segments(size_type l, size_type r) const { std::vector left, right; l += M_n; r += M_n; while (l < r) { if (l & 1) left.push_back(l++); if (r & 1) right.push_back(--r); l >>= 1; r >>= 1; } left.insert(left.end(), right.rbegin(), right.rend()); return left; } public: basic_segment_tree() = default; explicit basic_segment_tree(size_type n): M_c(n+n), M_n(n) {} explicit basic_segment_tree(size_type n, value_type const& x): M_c(n+n, x), M_n(n) { for (size_type i = n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1]; } template basic_segment_tree(InputIt first, InputIt last) { std::vector tmp(first, last); M_n = tmp.size(); M_c.resize(M_n); M_c.insert(M_c.end(), tmp.begin(), tmp.end()); for (size_type i = M_n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1]; } void assign(size_type n, value_type const& x) { M_c.assign(n+n, x); M_n = n; for (size_type i = n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1]; } template void assign(InputIt first, InputIt last) { std::vector tmp(first, last); M_n = tmp.size(); M_c.resize(M_n); M_c.insert(M_c.end(), tmp.begin(), tmp.end()); for (size_type i = M_n; i--;) M_c[i] = M_c[i<<1|0] + M_c[i<<1|1]; } void set(size_type i, value_type const& x) { i += M_n; M_c[i] = x; while (i > 1) { i >>= 1; M_c[i] = M_c[i<<1|0] + M_c[i<<1|1]; } } void set(size_type i, value_type&& x) { i += M_n; M_c[i] = std::move(x); while (i > 1) { i >>= 1; M_c[i] = M_c[i<<1|0] + M_c[i<<1|1]; } } value_type const& operator [](size_type i) const { return M_c[i + M_n]; } value_type fold(size_type l, size_type r) const { value_type resl{}, resr{}; l += M_n; r += M_n; while (l < r) { if (l & 1) resl += M_c[l++]; if (r & 1) resr = M_c[--r] + std::move(resr); l >>= 1; r >>= 1; } return resl += resr; } template size_type foldl_bisect(size_type l, Predicate pred) const { // Return minimum r such that pred(fold(l, r)) is false, // or n if such r does not exist. if (l == M_n) return l; l += M_n; size_type r = M_n+M_n; value_type x{}; size_type h = 0; auto bisect = [&](size_type v) -> size_type { while (v < M_n) { v <<= 1; if (pred(x + M_c[v])) x += M_c[v++]; } return v - M_n; }; for (; l < r; ++h, l >>= 1, r >>= 1) { if (l & 1) { if (!pred(x + M_c[l])) return bisect(l); ++l; } if (r & 1) --r; } for (--h, r <<= 1; r < M_n+M_n; --h, r <<= 1) { if (((r+1) << h) <= M_n+M_n) { if (!pred(x + M_c[r])) return bisect(r); ++r; } } return M_n; } template size_type foldr_bisect(size_type r, Predicate pred) const { // Return maximum l such that pred(fold(l, r)) is false, // of -1 (of size_type) if such does not exist. if (r == 0) return r; value_type x{}; size_type v = M_n+M_n; std::vector cs = M_covering_segments(0, r); std::reverse(cs.begin(), cs.end()); // search the subroot for (auto s: cs) { if (!pred(M_c[s] + x)) { v = s; break; } x = M_c[s] + std::move(x); } if (v == M_n+M_n) return -1; // always true // search the leaf while (v < M_n) { v <<= 1; if (pred(M_c[v|1] + x)) { x = M_c[v|1] + std::move(x); } else { v |= 1; } } return v - M_n; } }; #line 1 "DataStructure/wavelet_matrix.cpp" /** * @brief ウェーブレット行列 * @author えびちゃん */ #line 10 "DataStructure/wavelet_matrix.cpp" #include #include #line 13 "DataStructure/wavelet_matrix.cpp" #line 1 "utility/literals.cpp" /** * @brief ユーザ定義リテラル * @author えびちゃん */ #line 11 "utility/literals.cpp" constexpr intmax_t operator ""_jd(unsigned long long n) { return n; } constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; } constexpr size_t operator ""_zu(unsigned long long n) { return n; } constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; } #line 1 "DataStructure/bit_vector.cpp" /** * @brief rank/select 辞書 * @author えびちゃん */ #include #line 13 "DataStructure/bit_vector.cpp" #line 15 "DataStructure/bit_vector.cpp" class bit_vector { public: using underlying_type = uintmax_t; using size_type = size_t; using difference_type = ptrdiff_t; private: static const size_type S_ws = CHAR_BIT * sizeof(underlying_type); std::vector M_c; std::vector M_r; std::vector M_s0, M_s1; std::vector> M_ss0, M_ss1; static size_type S_popcount(underlying_type n) { return __builtin_popcountll(n); } static underlying_type S_least_n_bits(size_type n) { return (1_ju << n) - 1; } template static size_type S_rank_small(underlying_type x, size_type n) { if (Bp == 0) x = ~x; return S_popcount(x & S_least_n_bits(n)); } template static size_type S_select_small(underlying_type x, size_type n) { if (n == 0) return 0; size_type lb = 0; size_type ub = S_ws; while (ub-lb > 1) { size_type mid = (lb+ub) >> 1; ((S_rank_small(x, mid) < n)? lb: ub) = mid; } return ub; } template size_type M_rank_large(size_type n) const { // if (n == 0) return 0; size_type res = M_r[n]; if (Bp == 0) res = n * S_ws - res; return res; } template void M_prepare_select(std::vector const& bv, std::vector& s, std::vector>& ss) { size_type z = 0; size_type n = bv.size(); s.push_back(0); std::vector tmp; for (size_type i = 0; i < n; ++i) { if (bv[i] != Bp) continue; tmp.push_back(i); if (++z == S_ws) { size_type len = i+1 - s.back(); s.push_back(i+1); ss.emplace_back(); if (len >= S_ws * S_ws) ss.back() = std::move(tmp); tmp.clear(); z = 0; } } ss.push_back(std::move(tmp)); } template size_type M_select(size_type n, std::vector const& s, std::vector> const& ss) const { if (n-- == 0) return 0; size_type j0 = n / S_ws; size_type j1 = n % S_ws; if (j0 >= s.size()) return -1_zu; if (j0+1 == s.size() && j1 >= ss[j0].size()) return -1_zu; if (!ss[j0].empty()) return ss[j0][j1] + 1; size_type lb = s[j0] / S_ws; size_type ub = (j0+1 < s.size())? (s[j0+1]+S_ws-1) / S_ws: M_r.size(); while (ub-lb > 1) { size_type mid = (lb+ub) >> 1; ((M_rank_large(mid) <= n)? lb: ub) = mid; } return lb * S_ws + S_select_small(M_c[lb], n+1 - M_rank_large(lb)); } public: bit_vector() = default; bit_vector(bit_vector const&) = default; bit_vector(bit_vector&&) = default; template bit_vector(InputIt first, InputIt last) { assign(first, last); } bit_vector& operator =(bit_vector const&) = default; bit_vector& operator =(bit_vector&&) = default; template void assign(InputIt first, InputIt last) { std::vector tmp(first, last); M_c.resize(tmp.size() / S_ws + 1); for (size_type i = 0; i < tmp.size(); ++i) { if (!tmp[i]) continue; size_type j0 = i / S_ws; size_type j1 = i % S_ws; M_c[j0] |= 1_ju << j1; } // rank M_r.assign(M_c.size(), 0); for (size_type i = 1; i < M_c.size(); ++i) M_r[i] += M_r[i-1] + S_popcount(M_c[i-1]); // select M_prepare_select<0>(tmp, M_s0, M_ss0); M_prepare_select<1>(tmp, M_s1, M_ss1); } size_type rank0(size_type t) const { return t - rank1(t); } size_type rank1(size_type t) const { size_type j0 = t / S_ws; size_type j1 = t % S_ws; return M_r[j0] + S_popcount(S_least_n_bits(j1) & M_c[j0]); } size_type rank0(size_type s, size_type t) const { return (t-s) - rank1(s, t); } size_type rank1(size_type s, size_type t) const { if (s == t) return 0; return rank1(t) - rank1(s); } size_type select0(size_type n) const { return M_select<0>(n, M_s0, M_ss0); } size_type select1(size_type n) const { return M_select<1>(n, M_s1, M_ss1); } size_type select0(size_type n, size_type s) const { n += rank0(0, s); return M_select<0>(n, M_s0, M_ss0); } size_type select1(size_type n, size_type s) const { n += rank1(0, s); return M_select<1>(n, M_s1, M_ss1); } }; #line 16 "DataStructure/wavelet_matrix.cpp" template class wavelet_matrix { public: using value_type = Tp; using size_type = size_t; using difference_type = ptrdiff_t; using bitvector_type = Bv; private: std::array M_a = {}; std::array M_z = {}; std::vector M_c; enum S_three_way { S_less = 0, S_equal, S_greater }; static const value_type S_fail = -1; // XXX use std::optional? size_type M_startpos(value_type x) /* const */ { size_type s = 0; size_type t = 0; for (size_type i = Nb; i-- > 1;) { size_type j = Nb-i-1; if (x >> i & 1) { s = M_z[j] + M_a[j].rank1(s); t = M_z[j] + M_a[j].rank1(t); } else { s = M_a[j].rank0(s); t = M_a[j].rank0(t); } } return s; } public: wavelet_matrix() = default; template wavelet_matrix(InputIt first, InputIt last) { assign(first, last); } wavelet_matrix(std::initializer_list il): wavelet_matrix(il.begin(), il.end()) {} template void assign(InputIt first, InputIt last) { M_c.assign(first, last); M_z = {{}}; size_type n = M_c.size(); std::vector whole = M_c; for (size_type i = Nb; i--;) { std::vector zero, one; std::vector vb(n); for (size_type j = 0; j < n; ++j) { ((whole[j] >> i & 1)? one: zero).push_back(whole[j]); vb[j] = (whole[j] >> i & 1); } M_z[Nb-i-1] = zero.size(); M_a[Nb-i-1] = bitvector_type(vb.begin(), vb.end()); if (i == 0) break; whole = std::move(zero); whole.insert(whole.end(), one.begin(), one.end()); } } size_type rank(value_type x, size_type s, size_type t) /* const */ { if (s == t) return 0; for (size_type i = Nb; i--;) { size_type j = Nb-i-1; if (x >> i & 1) { s = M_z[j] + M_a[j].rank1(s); t = M_z[j] + M_a[j].rank1(t); } else { s = M_a[j].rank0(s); t = M_a[j].rank0(t); } } return t - s; } size_type select(value_type x, size_type n) /* const */ { if (n == 0) return 0; if (rank(x, 0, M_c.size()) < n) return -1; size_type si = M_startpos(x); if (x & 1) { n += M_a[Nb-1].rank1(si); n = M_a[Nb-1].select1(n); } else { n += M_a[Nb-1].rank0(si); n = M_a[Nb-1].select0(n); } for (size_type i = 1; i < Nb; ++i) { size_type j = Nb-i-1; if (x >> i & 1) { n -= M_z[j]; n = M_a[j].select1(n); } else { n = M_a[j].select0(n); } } return n; } size_type select(value_type x, size_type n, size_type s) /* const */ { if (n == 0) return s; n += rank(x, 0, s); return select(x, n); } std::array rank_3way(value_type x, size_type s, size_type t) /* const */ { if (s == t) return {0, 0, 0}; size_type lt = 0; size_type eq = t-s; size_type gt = 0; for (size_type i = Nb; i--;) { size_type j = Nb-i-1; size_type tmp = t-s; if (x >> i & 1) { s = M_z[j] + M_a[j].rank1(s); t = M_z[j] + M_a[j].rank1(t); } else { s = M_a[j].rank0(s); t = M_a[j].rank0(t); } size_type d = tmp - (t-s); eq -= d; ((x >> i & 1)? lt: gt) += d; } return {lt, eq, gt}; } std::array xored_rank_3way(value_type x, value_type y, size_type s, size_type t) /* const */ { if (s == t) return {0, 0, 0}; size_type lt = 0; size_type eq = t-s; size_type gt = 0; for (size_type i = Nb; i--;) { size_type j = Nb-i-1; size_type tmp = t-s; if ((x ^ y) >> i & 1) { s = M_z[j] + M_a[j].rank1(s); t = M_z[j] + M_a[j].rank1(t); } else { s = M_a[j].rank0(s); t = M_a[j].rank0(t); } size_type d = tmp - (t-s); eq -= d; ((y >> i & 1)? lt: gt) += d; } return {lt, eq, gt}; } value_type quantile(size_type k, size_type s, size_type t) /* const */ { value_type res = 0; for (size_type i = Nb; i--;) { size_type j = Nb-i-1; size_type z = M_a[j].rank0(s, t); if (k < z) { s = M_a[j].rank0(s); t = M_a[j].rank0(t); } else { res |= 1_ju << i; s = M_z[j] + M_a[j].rank1(s); t = M_z[j] + M_a[j].rank1(t); k -= z; } } return res; } value_type min_greater(value_type x, size_type s, size_type t) /* const */ { auto r3 = rank_3way(x, s, t); size_type k = r3[S_less] + r3[S_equal]; if (k == t-s) return S_fail; return quantile(k, s, t); } value_type min_greater_equal(value_type x, size_type s, size_type t) /* const */ { auto r3 = rank_3way(x, s, t); size_type k = r3[S_less]; if (k == t-s) return S_fail; return quantile(k, s, t); } value_type max_less(value_type x, size_type s, size_type t) /* const */ { auto r3 = rank_3way(x, s, t); size_type k = r3[S_less]; if (k == 0) return S_fail; return quantile(k-1, s, t); } value_type max_less_equal(value_type x, size_type s, size_type t) /* const */ { auto r3 = rank_3way(x, s, t); size_type k = r3[S_less] + r3[S_equal]; if (k == 0) return S_fail; return quantile(k-1, s, t); } size_type select_greater(value_type x, size_type n, size_type s) /* const */ { if (n == 0) return s; size_type lb = s; size_type ub = M_c.size(); while (ub-lb > 1) { size_type mid = (lb+ub) >> 1; auto r3 = rank_3way(x, s, mid); size_type k = r3[S_greater]; ((k < n)? lb: ub) = mid; } return ub; } size_type select_greater_equal(value_type x, size_type n, size_type s) /* const */ { if (n == 0) return s; size_type lb = s; size_type ub = M_c.size(); while (ub-lb > 1) { size_type mid = (lb+ub) >> 1; auto r3 = rank_3way(x, s, mid); size_type k = r3[S_equal] + r3[S_greater]; ((k < n)? lb: ub) = mid; } return ub; } size_type select_less(value_type x, size_type n, size_type s) /* const */ { if (n == 0) return s; size_type lb = s; size_type ub = M_c.size(); while (ub-lb > 1) { size_type mid = (lb+ub) >> 1; auto r3 = rank_3way(x, s, mid); size_type k = r3[S_less]; ((k < n)? lb: ub) = mid; } return ub; } size_type select_less_equal(value_type x, size_type n, size_type s) /* const */ { if (n == 0) return s; size_type lb = s; size_type ub = M_c.size(); while (ub-lb > 1) { size_type mid = (lb+ub) >> 1; auto r3 = rank_3way(x, s, mid); size_type k = r3[S_less] + r3[S_equal]; ((k < n)? lb: ub) = mid; } return ub; } // for dynamic bitvectors only void insert(size_type t, value_type x) { size_type s = 0; for (size_type i = Nb; i--;) { size_type j = Nb-i-1; M_a[j].insert(s+t, x >> i & 1); if (x >> i & 1) { t = M_a[j].rank(1, s+t+1) - 1; s = M_z[j]; } else { t = M_a[j].rank(0, s+t+1) - 1; s = 0; ++M_z[j]; } } } void erase(size_type t) { size_type s = 0; for (size_type i = Nb; i--;) { size_type j = Nb-i-1; size_type u = s+t; if (M_a[j][u]) { t = M_a[j].rank(1, u+1) - 1; s = M_z[j]; } else { t = M_a[j].rank(0, u+1) - 1; s = 0; --M_z[j]; } M_a[j].erase(u); } } void set(size_type t, value_type x) { erase(t); insert(t, x); } value_type operator [](size_type s) /* const */ { return quantile(0, s, s+1); } }; #line 1 "utility/monoid/max.cpp" /** * @brief max を得る演算のモノイド * @author えびちゃん */ #line 10 "utility/monoid/max.cpp" #include #line 1 "utility/limits.cpp" /** * @brief 型依存の定数 * @author えびちゃん */ #include template class limits: public std::numeric_limits {}; #line 13 "utility/monoid/max.cpp" template class max_monoid { public: using value_type = Tp; private: value_type M_x = limits::min(); public: max_monoid() = default; // identity max_monoid(max_monoid const&) = default; max_monoid(max_monoid&&) = default; max_monoid(value_type const& x): M_x(x) {}; max_monoid(value_type&& x): M_x(std::move(x)) {}; max_monoid& operator =(max_monoid const&) = default; max_monoid& operator =(max_monoid&&) = default; max_monoid& operator +=(max_monoid const& that) { M_x = std::max(M_x, that.M_x); return *this; } max_monoid& operator +=(max_monoid&& that) { M_x = std::max(M_x, std::move(that.M_x)); return *this; } max_monoid operator +(max_monoid const& that) const { return max_monoid(*this) += that; } max_monoid operator +(max_monoid&& that) const { return max_monoid(*this) += std::move(that); } value_type const& get() const { return M_x; } }; #line 10 "test/yc_878_reversed.test.cpp" int main() { size_t n, q; scanf("%zu %zu", &n, &q); std::vector a(n); for (auto& ai: a) scanf("%d", &ai); std::reverse(a.begin(), a.end()); basic_segment_tree> st(a.begin(), a.end()); std::vector top(n); for (size_t i = 0; i < n; ++i) { auto pred = [&](auto x) { return x.get() <= a[i]; }; top[i] = st.foldl_bisect(i, pred); } wavelet_matrix<31> wm(top.begin(), top.end()); for (size_t i = 0; i < q; ++i) { size_t l, r; scanf(" 1 %zu %zu", &r, &l); --l, --r; l = n-1-l; r = n-1-r; printf("%zu\n", wm.rank_3way(r, l, r+1)[2]); } }