src/math/ds/trygub/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/num/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <int B = 1 << 30> | ||
| 8 | class trygub_num { | ||
| 9 | std::map<int, i64> d; | ||
| 10 | |||
| 11 | public: | ||
| 12 | ✗ | void add(i64 x, int y) NE { | |
| 13 | ✗ | d[y] += x; | |
| 14 | ✗ | auto it = d.find(y); | |
| 15 | ✗ | while (true) { | |
| 16 | ✗ | i64 t = it->second / B; | |
| 17 | ✗ | if (!t) break; | |
| 18 | ✗ | it->second %= B, d.insert(it, {++y, 0}); | |
| 19 | ✗ | (!it->second ? it = d.erase(it) : ++it)->second += t; | |
| 20 | } | ||
| 21 | ✗ | if (!it->second) d.erase(it); | |
| 22 | ✗ | } | |
| 23 | ✗ | i64 get(int k) NE { | |
| 24 | ✗ | auto it = d.lower_bound(k); | |
| 25 | ✗ | i64 res = (it != end(d) && it->first == k ? it->second : 0); | |
| 26 | ✗ | return (res - (it != begin(d) && prev(it)->second < 0) + B) % B; | |
| 27 | } | ||
| 28 | }; | ||
| 29 | |||
| 30 | } // namespace tifa_libs | ||
| 31 |