#line 2 "main.cpp" #include #include #line 2 "src/data-structure/hash_map.hpp" #include #include namespace kyopro { /// @brief HashMap 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 uint8_t 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 #line 5 "main.cpp" #include namespace kyopro { /// @brief Segment Tree template class segtree { int lg, sz, n; hash_map dat; public: segtree() {} segtree(int n) : segtree() { sz = 1, lg = 0; while (sz <= n) { sz <<= 1; lg++; } } segtree(const std::vector& vec) : n((int)vec.size()) { sz = 1, lg = 0; while (sz <= n) { sz <<= 1; lg++; } for (int i = 0; i < n; i++) { set(i, vec[i]); } build(); } void set(int p, const S& v) { dat[sz + p] = v; } void build() { for (int i = sz - 1; i > 0; i--) { dat[i] = op(dat[i << 1], dat[(i << 1) ^ 1]); } } S operator[](int p) { return dat[sz + p]; } void update(int p, const S& v) { p += sz; dat[p] = v; while (p >>= 1) { dat[p] = op(dat[(p << 1)], dat[(p << 1) ^ 1]); } } S prod(int l, int r) { if (l == 0 && r == n) { return dat[1]; } l += sz, r += sz; S sml = e(), smr = e(); while (l != r) { if (l & 1) sml = op(sml, dat[l++]); if (r & 1) smr = op(dat[--r], smr); l >>= 1, r >>= 1; } return op(sml, smr); } void apply(int p, const S& v) { update(p, op(dat[sz + p], v)); } }; }; // namespace kyopro /// @docs docs/data-structure/segtree.md /// @docs docs/data-structure/dynamic_segtree.md #include inline int op(int x, int y) { return x + y; } inline int e() { return 0; } int main() { const size_t n = 1000000001; kyopro::segtree seg(n); int q; std::cin >> q; long long ans = 0; while (q--) { int type; std::cin >> type; if (type == 0) { size_t x; long long y; std::cin >> x >> y; seg.apply(x, y); } else { size_t l, r; std::cin >> l >> r; ans += seg.prod(l, r + 1); } } std::cout << ans << '\n'; }