C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title データ構造/Fenwick tree/Fenwick tree(二分探索) * * verification-helper: IGNORE * verification-helper: PROBLEM https://atcoder.jp/contests/arc033/tasks/arc033_3 */ #include <iostream> #include "emthrm/data_structure/fenwick_tree/fenwick_tree.hpp" int main() { constexpr int M = 200000; emthrm::FenwickTree<int> bit(M + 1); int q; std::cin >> q; while (q--) { int t, x; std::cin >> t >> x; if (t == 1) { bit.add(x, 1); } else if (t == 2) { const int ans = bit.lower_bound(x); std::cout << ans << '\n'; bit.add(ans, -1); } } return 0; }
#line 1 "test/data_structure/fenwick_tree/fenwick_tree.2.test.cpp" /* * @title データ構造/Fenwick tree/Fenwick tree(二分探索) * * verification-helper: IGNORE * verification-helper: PROBLEM https://atcoder.jp/contests/arc033/tasks/arc033_3 */ #include <iostream> #line 1 "include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp" #include <bit> #include <vector> namespace emthrm { template <typename Abelian> struct FenwickTree { explicit FenwickTree(const int n, const Abelian ID = 0) : n(n), ID(ID), data(n, ID) {} void add(int idx, const Abelian val) { for (; idx < n; idx |= idx + 1) { data[idx] += val; } } Abelian sum(int idx) const { Abelian res = ID; for (--idx; idx >= 0; idx = (idx & (idx + 1)) - 1) { res += data[idx]; } return res; } Abelian sum(const int left, const int right) const { return left < right ? sum(right) - sum(left) : ID; } Abelian operator[](const int idx) const { return sum(idx, idx + 1); } int lower_bound(Abelian val) const { if (val <= ID) [[unlikely]] return 0; int res = 0; for (int mask = std::bit_ceil(static_cast<unsigned int>(n + 1)) >> 1; mask > 0; mask >>= 1) { const int idx = res + mask - 1; if (idx < n && data[idx] < val) { val -= data[idx]; res += mask; } } return res; } private: const int n; const Abelian ID; std::vector<Abelian> data; }; } // namespace emthrm #line 11 "test/data_structure/fenwick_tree/fenwick_tree.2.test.cpp" int main() { constexpr int M = 200000; emthrm::FenwickTree<int> bit(M + 1); int q; std::cin >> q; while (q--) { int t, x; std::cin >> t >> x; if (t == 1) { bit.add(x, 1); } else if (t == 2) { const int ans = bit.lower_bound(x); std::cout << ans << '\n'; bit.add(ans, -1); } } return 0; }