#include #include #include #include #include #include #include #include #include #include // #include "Src/Number/IntegerDivision.hpp" // #include "Src/Utility/BinarySearch.hpp" // #include "Src/Sequence/CompressedSequence.hpp" // #include "Src/Sequence/RunLengthEncoding.hpp" namespace zawa { template class AdditiveGroup { public: using Element = T; static constexpr T identity() noexcept { return T{}; } static constexpr T operation(const T& l, const T& r) noexcept { return l + r; } static constexpr T inverse(const T& v) noexcept { return -v; } }; } // namespace zawa #include #include namespace zawa { using i16 = std::int16_t; using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u8 = std::uint8_t; using u16 = std::uint16_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using usize = std::size_t; } // namespace zawa #include namespace zawa { namespace concepts { template concept Semigroup = requires { typename T::Element; { T::operation(std::declval(), std::declval()) } -> std::same_as; }; } // namespace concepts } // namespace zawa namespace zawa { namespace concepts { template concept Identitiable = requires { typename T::Element; { T::identity() } -> std::same_as; }; template concept Monoid = Semigroup and Identitiable; } // namespace } // namespace zawa namespace zawa { namespace concepts { template concept Inversible = requires { typename T::Element; { T::inverse(std::declval()) } -> std::same_as; }; template concept Group = Monoid and Inversible; } // namespace Concept } // namespace zawa #include #include #include namespace zawa { template class FenwickTree { public: using VM = Monoid; using V = typename VM::Element; FenwickTree() = default; explicit FenwickTree(usize n) : m_n{ n }, m_bitwidth{ std::__lg(n) + 1 }, m_a(n, VM::identity()), m_dat(n + 1, VM::identity()) { m_dat.shrink_to_fit(); m_a.shrink_to_fit(); } explicit FenwickTree(const std::vector& a) : m_n{ a.size() }, m_bitwidth{ std::__lg(a.size()) + 1 }, m_a(a), m_dat(a.size() + 1, VM::identity()) { m_dat.shrink_to_fit(); m_a.shrink_to_fit(); for (i32 i{} ; i < static_cast(m_n) ; i++) { addDat(i, a[i]); } } inline usize size() const noexcept { return m_n; } // return a[i] const V& get(usize i) const noexcept { assert(i < size()); return m_a[i]; } // return a[i] const V& operator[](usize i) const noexcept { assert(i < size()); return m_a[i]; } // a[i] <- a[i] + v void operation(usize i, const V& v) { assert(i < size()); addDat(i, v); m_a[i] = VM::operation(m_a[i], v); } // a[i] <- v void assign(usize i, const V& v) requires concepts::Inversible { assert(i < size()); addDat(i, VM::operation(VM::inverse(m_a[i]), v)); m_a[i] = v; } // return a[0] + a[1] + ... + a[r - 1] V prefixProduct(usize r) const { assert(r <= size()); return product(r); } // return a[l] + a[l + 1] ... + a[r - 1] V product(usize l, usize r) const requires concepts::Inversible { assert(l <= r and r <= size()); return VM::operation(VM::inverse(product(l)), product(r)); } template usize maxRight(usize l, const Function& f) const requires concepts::Inversible { static_assert(std::is_convertible_v>, "maxRight's argument f must be function bool(T)"); assert(l <= size()); assert(f(VM::identity())); V sum{ VM::inverse(product(l)) }; usize r{}; for (usize bit{ m_bitwidth } ; bit ; ) { bit--; usize nxt{ r | (1u << bit) }; if (nxt < m_dat.size() and (nxt <= l or f(VM::operation(sum, m_dat[nxt])))) { sum = VM::operation(sum, m_dat[nxt]); r = std::move(nxt); } } assert(l <= r); return r; } template usize minLeft(usize r, const Function& f) const requires concepts::Inversible { static_assert(std::is_convertible_v>, "minLeft's argument f must be function bool(T)"); assert(r <= size()); assert(f(VM::identity())); V sum{ product(r) }; usize l{}; for (usize bit{ m_bitwidth } ; bit ; ) { bit--; usize nxt{ l | (1u << bit) }; if (nxt <= r and not f(VM::operation(VM::inverse(m_dat[nxt]), sum))) { sum = VM::operation(VM::inverse(m_dat[nxt]), sum); l = std::move(nxt); } } assert(l <= r); return l; } // debug print friend std::ostream& operator<<(std::ostream& os, const FenwickTree& ft) { for (usize i{} ; i <= ft.size() ; i++) { os << ft.prefixProduct(i) << (i == ft.size() ? "" : " "); } return os; } private: usize m_n{}; usize m_bitwidth{}; std::vector m_a, m_dat; constexpr i32 lsb(i32 x) const noexcept { return x & -x; } // a[i] <- a[i] + v void addDat(i32 i, const V& v) { assert(0 <= i and i < static_cast(m_n)); for ( i++ ; i < static_cast(m_dat.size()) ; i += lsb(i)) { m_dat[i] = VM::operation(m_dat[i], v); } } // return a[0] + a[1] + .. + a[i - 1] V product(i32 i) const { assert(0 <= i and i <= static_cast(m_n)); V res{ VM::identity() }; for ( ; i > 0 ; i -= lsb(i)) { res = VM::operation(res, m_dat[i]); } return res; } }; } // namespace zawa // #include "Src/DataStructure/SegmentTree/SegmentTree.hpp" // #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp" // #include "Src/DataStructure/Heap/BinaryHeap.hpp" namespace zawa {} using namespace zawa; // #include "atcoder/modint" // using mint = atcoder::modint998244353; // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; template ostream& operator<<(ostream& os, const pair& p) { os << '(' << p.first << ',' << p.second << ')'; return os; } template ostream& operator<<(ostream& os, const vector& v) { for (int i = 0 ; i < ssize(v) ; i++) os << v[i] << (i + 1 == ssize(v) ? "" : " "); return os; } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20); #if !defined DEBUG int N,Q; cin >> N >> Q; FenwickTree> fen(N); for (int i = 0 ; i < N ; i++) { int a; cin >> a; fen.operation(i,a); } while (Q--) { long long x; cin >> x; cout << fen.maxRight(0,[&](long long v) { return v <= x; }) << '\n'; } #else mt19937_64 mt{random_device{}()}; for (int testcase = 0 ; ; ) { cerr << "----------" << ++testcase << "----------" << endl; auto a = solve(), b = naive(); if (a != b) { // print testcase cerr << "you: " << a << endl; cout << "correct: " << b << endl; exit(0); } } #endif }