#line 2 "library/src/data-structure/hash_map.hpp" #include #include namespace kyopro { /** * @brief Hash Map */ template class hash_map { using u32 = uint32_t; using u64 = uint64_t; u64* flag = new u64[n]; Key* keys = new Key[n]; Val* vals = new Val[n]; static constexpr u32 shift = 64 - std::__lg(n); u64 r; u32 get_hash(const Key& k) const { return ((u64)k * r) >> shift; } static constexpr int mod_msk = (1 << 6) - 1; public: explicit constexpr hash_map() { r = std::chrono::steady_clock::now().time_since_epoch().count(); r ^= r >> 16; r ^= r << 32; } Val& operator[](const Key& k) { u32 hash = get_hash(k); while (1) { if (!(flag[hash >> 6] & (static_cast(1) << (hash & mod_msk)))) { keys[hash] = k; flag[hash >> 6] |= static_cast(1) << (hash & mod_msk); return vals[hash] = default_val; } if (keys[hash] == k) return vals[hash]; hash = (hash + 1) & (n - 1); } } Val* find(const Key& k) const { u32 hash = get_hash(k); while (1) { if (!(flag[hash >> 6] & (static_cast(1) << (hash & mod_msk)))) return nullptr; if (keys[hash] == k) return &(vals[hash]); hash = (hash + 1) & (n - 1); } } }; }; // namespace kyopro /** * @docs docs/data-structure/hash_map.md */ #line 2 "library/src/stream.hpp" #include #include #include #line 2 "library/src/internal/type_traits.hpp" #include #include #include #include namespace kyopro { namespace internal { /* * @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8 */ template struct first_enabled {}; template struct first_enabled, Args...> { using type = T; }; template struct first_enabled, Args...> : first_enabled {}; template struct first_enabled { using type = T; }; template using first_enabled_t = typename first_enabled::type; template struct int_least { static_assert(dgt <= 128); using type = first_enabled_t, std::enable_if, std::enable_if, std::enable_if, std::enable_if >; }; template struct uint_least { static_assert(dgt <= 128); using type = first_enabled_t, std::enable_if, std::enable_if, std::enable_if, std::enable_if >; }; template using int_least_t = typename int_least::type; template using uint_least_t = typename uint_least::type; template using double_size_uint_t = uint_least_t<2 * std::numeric_limits::digits>; template using double_size_int_t = int_least_t<2 * std::numeric_limits::digits>; struct modint_base {}; template using is_modint = std::is_base_of; template using is_modint_t = std::enable_if_t::value>; // is_integral template using is_integral_t = std::enable_if_t || std::is_same_v || std::is_same_v>; }; // namespace internal }; // namespace kyopro #line 6 "library/src/stream.hpp" namespace kyopro { // read void single_read(char& c) { c = getchar_unlocked(); while (isspace(c)) c = getchar_unlocked(); } template * = nullptr> void single_read(T& a) { a = 0; bool is_negative = false; char c = getchar_unlocked(); while (isspace(c)) { c = getchar_unlocked(); } if (c == '-') is_negative = true, c = getchar_unlocked(); while (isdigit(c)) { a = 10 * a + (c - '0'); c = getchar_unlocked(); } if (is_negative) a *= -1; } template * = nullptr> void single_read(T& a) { long long x; single_read(x); a = T(x); } void single_read(std::string& str) { char c = getchar_unlocked(); while (isspace(c)) c = getchar_unlocked(); while (!isspace(c)) { str += c; c = getchar_unlocked(); } } template void read(T& x) {single_read(x);} template void read(Head& head, Tail&... tail) { single_read(head), read(tail...); } // write void single_write(char c) { putchar_unlocked(c); } template * = nullptr> void single_write(T a) { if (!a) { putchar_unlocked('0'); return; } if (a < 0) putchar_unlocked('-'), a *= -1; char s[37]; int now = 37; while (a) { s[--now] = (char)'0' + a % 10; a /= 10; } while (now < 37) putchar_unlocked(s[now++]); } template * = nullptr> void single_write(T a) { single_write(a.val()); } void single_write(const std::string& str) { for (auto c : str) { putchar_unlocked(c); } } template void write(T x) { single_write(x); } template void write(Head head, Tail... tail) { single_write(head); putchar_unlocked(' '); write(tail...); } template void put(Args... x) { write(x...); putchar_unlocked('\n'); } }; // namespace kyopro /** * @brief fastIO */ #line 3 "a.cpp" namespace kyopro { template class dynamic_BIT { hash_map bit; int n; public: dynamic_BIT(int n = std::numeric_limits::max()) : n(n) {} void add(size_t p, T w) { p++; for (size_t x = p; x <= n; x += x & -x) { bit[x] += w; } } T sum(size_t p) const { T s = 0; for (size_t x = p; x > 0; x -= x & -x) { auto p = bit.find(x); if (p) s += *p; } return s; } T sum(size_t l, size_t r) const { return sum(r) - sum(l); } }; }; // namespace kyopro int main() { const size_t n = 1000001; kyopro::dynamic_BIT seg; int q; kyopro::read(q); long long ans = 0; while (q--) { int type; kyopro::read(type); if (!type) { size_t x; long long y; kyopro::read(x, y); seg.add(x, y); } else { size_t l, r; kyopro::read(l, r); ans += seg.sum(l, r + 1); } } kyopro::put(ans); }