This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ageprocpp/competitive-programming-library
#include "data-structure/SegTree.hpp"
要素の更新と区間への演算の適用を行うデータ構造です。
template <class T, T (*nodef)(const T&, const T&)> class SegTree;
T は扱う要素の型、nodef は要素同士に適用する演算を表します。
T
nodef
SegTree(T e_); // (1) SegTree(unsigned int m_, T e_); // (2) SegTree(unsigned int m_, T init, T e_); // (3) template <class U> SegTree(const std::vector<U>& initvec, T e_); // (4)
単位元 e_ の Segment Tree を構築します。
e_
長さ m_、単位元 e_ の Segment Tree を構築し、T() で初期化します。$O(m\_)$ で動作します。
m_
T()
長さ m_、単位元 e_ の Segment Tree を構築し、init で初期化します。$O(m\_)$ で動作します。
init
単位元 e_ で初期状態 initvec をもつ Segment Tree を構築します。$m\_$ を initvec の長さとして、$O(m\_)$ で動作します。
initvec
void update(int i, T x);
$i$ 番目の要素を $x$ に変更します。$O(\log m\_)$ で動作します。
T query(int l, int r) const;
$[l, r)$ に nodef を作用させた結果を返します。$O(\log m\_)$ で動作します。
T query_all() const;
全体に nodef を作用させた結果を返します。$O(1)$ で動作します。
const T& operator[](const int& x) const;
$i$ 番目の要素への const な参照を返します。$O(1)$ で動作します。
const
void fill(T x);
全体を $x$ に変更します。$O(m\_)$ で動作します。
template <class F> int max_right(int st, F check) const; // (1) template <bool (*check)(const T&)> int max_right(int st) const; // (2)
$[st, r)$ に nodef を作用させた結果が check を満たす最小の $r$ を返します。$O(\log m\_)$ で動作します。
check
template <class F> int min_left(int st, F check) const; // (1) template <bool (*check)(const T&)> int min_left(int st) const; // (2)
$[l, st)$ に nodef を作用させた結果が check を満たす最大の $l$ を返します。$O(\log m\_)$ で動作します。
template <typename T> class RSQ : public SegTree<T, RSQ_nodef>;
RSQ_nodef は加法を表します。
RSQ_nodef
template <typename T, typename U = void> class RMiQ : public SegTree<T, RMiQ_nodef>; // (1) template <typename T> class RMiQ<T, std::enable_if_t<std::numeric_limits<T>::is_specialized, std::nullptr_t>> : public SegTree<T, RMiQ_nodef>; // (2)
RMiQ_nodef は min 演算を表します。 T が std::numeric_limits で特殊化された型の場合、その型の最大値を単位元とします。
RMiQ_nodef
min
std::numeric_limits
template <typename T, typename U = void> class RMaQ : public SegTree<T, RMaQ_nodef>; // (1) template <typename T> class RMaQ<T, std::enable_if_t<std::numeric_limits<T>::is_specialized, std::nullptr_t>> : public SegTree<T, RMaQ_nodef>; // (2)
RMaQ_nodef は max 演算を表します。 T が std::numeric_limits で特殊化された型の場合、その型の最小値を単位元とします。
RMaQ_nodef
max
#pragma once #include "../basic/template.hpp" template <class T, T (*nodef)(const T&, const T&)> class SegTree { protected: unsigned int n = 1, m = 1, rank = 0; std::vector<T> node; T ident; public: SegTree(T e_) : ident(e_) {} SegTree(unsigned int m_, T e_) : m(m_), ident(e_) { while (n < m) { n *= 2; rank++; } node.resize(2 * n, ident); } SegTree(unsigned int m_, T init, T e_) : m(m_), ident(e_) { while (n < m) { n *= 2; rank++; } node.resize(2 * n, ident); for (unsigned int i = n; i < 2 * n; i++) node[i] = init; for (unsigned int i = n - 1; i > 0; i--) node[i] = nodef(node[i << 1], node[i << 1 | 1]); } template <class U> SegTree(const std::vector<U>& initvec, T e_) : ident(e_) { m = initvec.size(); while (n < m) { n *= 2; rank++; } node.resize(2 * n, ident); for (unsigned int i = n; i < 2 * n; i++) { if (i - n < m) node[i] = initvec[i - n]; } for (unsigned int i = n - 1; i > 0; i--) node[i] = nodef(node[i << 1], node[i << 1 | 1]); } void update(int i, T x) { i += n; node[i] = x; while (i != 1) { i >>= 1; node[i] = nodef(node[2 * i], node[2 * i + 1]); } } T query(int l, int r) const { l += n; r += n; T ls = ident, rs = ident; while (l < r) { if (l & 1) ls = nodef(ls, node[l++]); if (r & 1) rs = nodef(node[--r], rs); l >>= 1; r >>= 1; } return nodef(ls, rs); } const T& operator[](const int& i) const { return node[n + i]; } T query_all() const { return node[1]; } void fill(T x) { for (unsigned int i = n; i < 2 * n; i++) node[i] = x; for (unsigned int i = n - 1; i > 0; i--) node[i] = nodef(node[i << 1], node[i << 1 | 1]); } private: template <class F> int max_right(int st, F& check, T& acc, int k, int l, int r) const { if (l + 1 == r) { acc = nodef(acc, node[k]); return check(acc) ? m : k - n; } int mid = (l + r) >> 1; if (mid <= st) return max_right(st, check, acc, (k << 1) | 1, mid, r); if (st <= l && check(nodef(acc, node[k]))) { acc = nodef(acc, node[k]); return m; } int vl = max_right(st, check, acc, k << 1, l, mid); if (vl != m) return vl; return max_right(st, check, acc, (k << 1) | 1, mid, r); } template <class F> int min_left(int st, F& check, T& acc, int k, int l, int r) const { if (l + 1 == r) { acc = nodef(node[k], acc); return check(acc) ? 0 : k - n + 1; } int mid = (l + r) >> 1; if (st <= mid) return min_left(st, check, acc, k << 1, l, mid); if (r <= st && check(nodef(node[k], acc))) { acc = nodef(node[k], acc); return 0; } int vr = min_left(st, check, acc, (k << 1) | 1, mid, r); if (vr != 0) return vr; return min_left(st, check, acc, k << 1, l, mid); } public: template <class F> int max_right(int st, F check) const { T acc = ident; return max_right(st, check, acc, 1, 0, n); } template <bool (*check)(const T&)> int max_right(int st) const { T acc = ident; return max_right(st, check, acc, 1, 0, n); } template <class F> int min_left(int st, F check) const { T acc = ident; return min_left(st, check, acc, 1, 0, n); } template <bool (*check)(const T&)> int min_left(int st) const { T acc = ident; return min_left(st, check, acc, 1, 0, n); } }; namespace { template <typename T> T RSQ_nodef(const T& lhs, const T& rhs) { return lhs + rhs; } template <typename T> T RMiQ_nodef(const T& lhs, const T& rhs) { return std::min(lhs, rhs); } template <typename T> T RMaQ_nodef(const T& lhs, const T& rhs) { return std::max(lhs, rhs); } } // namespace template <typename T> class RSQ : public SegTree<T, RSQ_nodef> { using Base = SegTree<T, RSQ_nodef>; public: template <class... Args> RSQ(Args&&... args) : Base(std::forward<Args>(args)..., 0) {} }; template <typename T, typename U = void> class RMiQ : public SegTree<T, RMiQ_nodef> { using Base = SegTree<T, RMiQ_nodef>; public: template <class... Args> RMiQ(Args&&... args) : Base(std::forward<Args>(args)...) {} }; template <typename T> class RMiQ<T, std::enable_if_t<std::numeric_limits<T>::is_specialized>> : public SegTree<T, RMiQ_nodef> { using Base = SegTree<T, RMiQ_nodef>; public: template <class... Args> RMiQ(Args&&... args) : Base(std::forward<Args>(args)..., std::numeric_limits<T>::max()) {} }; template <typename T, typename U = void> class RMaQ : public SegTree<T, RMaQ_nodef> { using Base = SegTree<T, RMaQ_nodef>; public: template <class... Args> RMaQ(Args&&... args) : Base(std::forward<Args>(args)...) {} }; template <typename T> class RMaQ<T, std::enable_if_t<std::numeric_limits<T>::is_specialized>> : public SegTree<T, RMaQ_nodef> { using Base = SegTree<T, RMaQ_nodef>; public: template <class... Args> RMaQ(Args&&... args) : Base(std::forward<Args>(args)..., std::numeric_limits<T>::min()) {} };
#line 2 "basic/template.hpp" #define _CRT_SECURE_NO_WARNINGS #ifndef __clang__ #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include <string.h> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cfloat> #include <chrono> #include <climits> #include <cmath> #include <complex> #include <ctime> #include <deque> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <list> #include <map> #include <memory> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> #define rep(i, n) for (int i = 0; i < int(n); i++) #define REP(i, n) for (int i = 1; i <= int(n); i++) #define all(V) V.begin(), V.end() using i128 = __int128_t; using u128 = __uint128_t; using uint = unsigned int; using lint = long long; using ulint = unsigned long long; using IP = std::pair<int, int>; using LP = std::pair<lint, lint>; constexpr int INF = INT_MAX / 2; constexpr lint LINF = LLONG_MAX / 2; constexpr double eps = DBL_EPSILON * 10; constexpr double PI = 3.141592653589793238462643383279; template <class T> class prique : public std::priority_queue<T, std::vector<T>, std::greater<T>> {}; int popcount(uint x) { #if __cplusplus >= 202002L return std::popcount(x); #else #ifndef __clang__ return __builtin_popcount(x); #endif #endif x = (x & 0x55555555) + (x >> 1 & 0x55555555); x = (x & 0x33333333) + (x >> 2 & 0x33333333); x = (x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f); x = (x & 0x00ff00ff) + (x >> 8 & 0x00ff00ff); return (x & 0x0000ffff) + (x >> 16 & 0x0000ffff); } template <class F> inline constexpr decltype(auto) lambda_fix(F&& f) { return [f = std::forward<F>(f)](auto&&... args) { return f(f, std::forward<decltype(args)>(args)...); }; } template <class T> constexpr std::vector<T> make_vec(size_t n) { return std::vector<T>(n); } template <class T, class... Args> constexpr auto make_vec(size_t n, Args&&... args) { return std::vector<decltype(make_vec<T>(args...))>(n, make_vec<T>(std::forward<Args>(args)...)); } template <class T, class U, class Stream> Stream& operator>>(Stream& ist, std::pair<T, U>& x) { return ist >> x.first >> x.second; } template <class T, class U, class Stream> Stream& operator<<(Stream& ost, const std::pair<T, U>& x) { return ost << x.first << " " << x.second; } template <class Container, std::enable_if_t<!std::is_same<Container, std::string>::value, std::nullptr_t> = nullptr> auto operator>>(std::istream& ist, Container& cont) -> decltype(typename Container::iterator(), std::cin)& { Container tmp; while (true) { typename Container::value_type t; ist >> t; tmp.emplace_back(t); if (getchar() == '\n') break; } cont = Container(std::move(tmp)); return ist; } template <class Container, class Stream, std::enable_if_t<!std::is_same<Container, std::string>::value, std::nullptr_t> = nullptr> auto operator<<(Stream& ost, const Container& cont) -> decltype(typename Container::iterator(), ost)& { for (auto it = cont.begin(); it != cont.end(); it++) { if (it != cont.begin()) ost << ' '; ost << *it; } return ost; } template <class Container> auto sum(const Container& cont) -> decltype(typename Container::iterator(), 0LL) { lint res = 0; for (auto it = cont.begin(); it != cont.end(); it++) res += *it; return res; } template <class T, class U> constexpr inline bool chmax(T& lhs, const U& rhs) noexcept { if (lhs < rhs) { lhs = rhs; return true; } return false; } template <class T, class U> constexpr inline bool chmin(T& lhs, const U& rhs) noexcept { if (lhs > rhs) { lhs = rhs; return true; } return false; } constexpr inline lint gcd(lint a, lint b) noexcept { while (b) { lint c = a; a = b; b = c % b; } return a; } inline lint lcm(lint a, lint b) noexcept { return a / gcd(a, b) * b; } constexpr bool isprime(lint n) noexcept { if (n == 1) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } template <class T> constexpr T mypow(T a, lint b) noexcept { T res(1); while (true) { if (b & 1) res *= a; b >>= 1; if (!b) break; a *= a; } return res; } constexpr lint modpow(lint a, lint b, lint m) noexcept { a %= m; lint res(1); while (b) { if (b & 1) res *= a, res %= m; a *= a, a %= m, b >>= 1; } return res; } LP extGcd(lint a, lint b) noexcept { if (b == 0) return {1, 0}; LP s = extGcd(b, a % b); std::swap(s.first, s.second); s.second -= a / b * s.first; return s; } LP ChineseRem(const lint& b1, const lint& m1, const lint& b2, const lint& m2) noexcept { auto p = extGcd(m1, m2); lint g = gcd(m1, m2), l = m1 / g * m2; lint tmp = (b2 - b1) / g * p.first % (m2 / g); lint r = (b1 + m1 * tmp + l) % l; return {r, l}; } int LCS(const std::string& a, const std::string& b) { auto dp = make_vec<int>(a.size() + 1, b.size() + 1); rep(i, a.size()) { rep(j, b.size()) { chmax(dp[i + 1][j], dp[i][j]); chmax(dp[i][j + 1], dp[i][j]); if (a[i] == b[j]) chmax(dp[i + 1][j + 1], dp[i][j] + 1); } chmax(dp[i + 1][b.size()], dp[i][b.size()]); } rep(j, b.size()) chmax(dp[a.size()][j + 1], dp[a.size()][j]); return dp[a.size()][b.size()]; } template <class T, std::enable_if_t<std::is_convertible<int, T>::value, std::nullptr_t> = nullptr> void compress(std::vector<T>& vec) { auto tmp = vec; std::sort(all(tmp)); tmp.erase(std::unique(all(tmp)), tmp.end()); for (T& i : vec) i = std::lower_bound(all(tmp), i) - tmp.begin(); } template <class T> void compress(T* l, T* r) { std::vector<T> tmp(l, r); std::sort(all(tmp)); tmp.erase(std::unique(all(tmp)), tmp.end()); for (auto i = l; i < r; i++) { *i = std::lower_bound(all(tmp), *i) - tmp.begin(); } } template <class InputIter> void compress(InputIter l, InputIter r) { std::vector<typename InputIter::value_type> tmp(l, r); std::sort(all(tmp)); tmp.erase(std::unique(all(tmp)), tmp.end()); for (auto i = l; i < r; i++) { *i = std::lower_bound(all(tmp), *i) - tmp.begin(); } } template <class InputIter, std::enable_if_t<std::is_same<typename InputIter::value_type, std::pair<IP, int>>::value, std::nullptr_t> = nullptr> void mo_sort(InputIter l, InputIter r, int N) { const int M = std::max(1.0, std::sqrt(lint(N) * N / std::distance(l, r))); std::sort(l, r, [M](const auto& lhs, const auto& rhs) { if (lhs.first.first / M < rhs.first.first / M) return true; if (lhs.first.first / M == rhs.first.first / M) return lhs.first.second < rhs.first.second; return false; }); int before = -1, cnt = 0; bool f = false; for (InputIter i = l; i != r; i++) { if (before != i->first.first / M) { if (f) std::reverse(i - cnt, i); f ^= true, before = i->first.first / M, cnt = 1; } else cnt++; } if (f) std::reverse(r - cnt, r); } template <class T> std::vector<T> xor_bases(const std::vector<T>& vec) { std::vector<T> res; for (T i : vec) { for (T j : res) { chmin(i, i ^ j); } if (i) res.emplace_back(i); } return res; } #line 3 "data-structure/SegTree.hpp" template <class T, T (*nodef)(const T&, const T&)> class SegTree { protected: unsigned int n = 1, m = 1, rank = 0; std::vector<T> node; T ident; public: SegTree(T e_) : ident(e_) {} SegTree(unsigned int m_, T e_) : m(m_), ident(e_) { while (n < m) { n *= 2; rank++; } node.resize(2 * n, ident); } SegTree(unsigned int m_, T init, T e_) : m(m_), ident(e_) { while (n < m) { n *= 2; rank++; } node.resize(2 * n, ident); for (unsigned int i = n; i < 2 * n; i++) node[i] = init; for (unsigned int i = n - 1; i > 0; i--) node[i] = nodef(node[i << 1], node[i << 1 | 1]); } template <class U> SegTree(const std::vector<U>& initvec, T e_) : ident(e_) { m = initvec.size(); while (n < m) { n *= 2; rank++; } node.resize(2 * n, ident); for (unsigned int i = n; i < 2 * n; i++) { if (i - n < m) node[i] = initvec[i - n]; } for (unsigned int i = n - 1; i > 0; i--) node[i] = nodef(node[i << 1], node[i << 1 | 1]); } void update(int i, T x) { i += n; node[i] = x; while (i != 1) { i >>= 1; node[i] = nodef(node[2 * i], node[2 * i + 1]); } } T query(int l, int r) const { l += n; r += n; T ls = ident, rs = ident; while (l < r) { if (l & 1) ls = nodef(ls, node[l++]); if (r & 1) rs = nodef(node[--r], rs); l >>= 1; r >>= 1; } return nodef(ls, rs); } const T& operator[](const int& i) const { return node[n + i]; } T query_all() const { return node[1]; } void fill(T x) { for (unsigned int i = n; i < 2 * n; i++) node[i] = x; for (unsigned int i = n - 1; i > 0; i--) node[i] = nodef(node[i << 1], node[i << 1 | 1]); } private: template <class F> int max_right(int st, F& check, T& acc, int k, int l, int r) const { if (l + 1 == r) { acc = nodef(acc, node[k]); return check(acc) ? m : k - n; } int mid = (l + r) >> 1; if (mid <= st) return max_right(st, check, acc, (k << 1) | 1, mid, r); if (st <= l && check(nodef(acc, node[k]))) { acc = nodef(acc, node[k]); return m; } int vl = max_right(st, check, acc, k << 1, l, mid); if (vl != m) return vl; return max_right(st, check, acc, (k << 1) | 1, mid, r); } template <class F> int min_left(int st, F& check, T& acc, int k, int l, int r) const { if (l + 1 == r) { acc = nodef(node[k], acc); return check(acc) ? 0 : k - n + 1; } int mid = (l + r) >> 1; if (st <= mid) return min_left(st, check, acc, k << 1, l, mid); if (r <= st && check(nodef(node[k], acc))) { acc = nodef(node[k], acc); return 0; } int vr = min_left(st, check, acc, (k << 1) | 1, mid, r); if (vr != 0) return vr; return min_left(st, check, acc, k << 1, l, mid); } public: template <class F> int max_right(int st, F check) const { T acc = ident; return max_right(st, check, acc, 1, 0, n); } template <bool (*check)(const T&)> int max_right(int st) const { T acc = ident; return max_right(st, check, acc, 1, 0, n); } template <class F> int min_left(int st, F check) const { T acc = ident; return min_left(st, check, acc, 1, 0, n); } template <bool (*check)(const T&)> int min_left(int st) const { T acc = ident; return min_left(st, check, acc, 1, 0, n); } }; namespace { template <typename T> T RSQ_nodef(const T& lhs, const T& rhs) { return lhs + rhs; } template <typename T> T RMiQ_nodef(const T& lhs, const T& rhs) { return std::min(lhs, rhs); } template <typename T> T RMaQ_nodef(const T& lhs, const T& rhs) { return std::max(lhs, rhs); } } // namespace template <typename T> class RSQ : public SegTree<T, RSQ_nodef> { using Base = SegTree<T, RSQ_nodef>; public: template <class... Args> RSQ(Args&&... args) : Base(std::forward<Args>(args)..., 0) {} }; template <typename T, typename U = void> class RMiQ : public SegTree<T, RMiQ_nodef> { using Base = SegTree<T, RMiQ_nodef>; public: template <class... Args> RMiQ(Args&&... args) : Base(std::forward<Args>(args)...) {} }; template <typename T> class RMiQ<T, std::enable_if_t<std::numeric_limits<T>::is_specialized>> : public SegTree<T, RMiQ_nodef> { using Base = SegTree<T, RMiQ_nodef>; public: template <class... Args> RMiQ(Args&&... args) : Base(std::forward<Args>(args)..., std::numeric_limits<T>::max()) {} }; template <typename T, typename U = void> class RMaQ : public SegTree<T, RMaQ_nodef> { using Base = SegTree<T, RMaQ_nodef>; public: template <class... Args> RMaQ(Args&&... args) : Base(std::forward<Args>(args)...) {} }; template <typename T> class RMaQ<T, std::enable_if_t<std::numeric_limits<T>::is_specialized>> : public SegTree<T, RMaQ_nodef> { using Base = SegTree<T, RMaQ_nodef>; public: template <class... Args> RMaQ(Args&&... args) : Base(std::forward<Args>(args)..., std::numeric_limits<T>::min()) {} };