結果
| 問題 | No.789 範囲の合計 |
| ユーザー |
 pitP
|
| 提出日時 | 2023-11-18 15:53:13 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 76 ms / 1,000 ms |
| コード長 | 6,854 bytes |
| コンパイル時間 | 5,345 ms |
| コンパイル使用メモリ | 255,624 KB |
| 最終ジャッジ日時 | 2025-02-17 22:28:09 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 15 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; }ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); }istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); }typedef long long ll;typedef vector<vector<int>> Graph;typedef pair<int, int> pii;typedef pair<ll, ll> pll;#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)#define rep(i,n) for (int i = 0;i < (int)(n); i++)#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define my_sort(x) sort(x.begin(), x.end())#define my_max(x) *max_element(all(x))#define my_min(x) *min_element(all(x))template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }const int INF = (1<<30) - 1;const ll LINF = (1LL<<62) - 1;const int MOD = 998244353;const int MOD2 = 1e9+7;const double PI = acos(-1);vector<int> di = {1,0,-1,0};vector<int> dj = {0,1,0,-1};#ifdef LOCAL# include <debug_print.hpp># define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)#else# define debug(...) (static_cast<void>(0))#endiftemplate <class S, S (*op)(S, S), S (*e)()> class dynamic_segtree {public:dynamic_segtree(size_t n) : n(n), root(nullptr) {}void set(size_t p, S x) {assert(p < n);set(root, 0, n, p, x);}S get(size_t p) const {assert(p < n);return get(root, 0, n, p);}S prod(size_t l, size_t r) const {assert(l <= r && r <= n);return prod(root, 0, n, l, r);}S all_prod() const { return root ? root->product : e(); }void reset(size_t l, size_t r) {assert(l <= r && r <= n);return reset(root, 0, n, l, r);}template <bool (*f)(S)> size_t max_right(size_t l) const {return max_right(l, [](S x) { return f(x); });}template <class F> size_t max_right(size_t l, const F& f) const {assert(l <= n);S product = e();assert(f(product));return max_right(root, 0, n, l, f, product);}template <bool (*f)(S)> size_t min_left(size_t r) const {return min_left(r, [](S x) { return f(x); });}template <class F> size_t min_left(size_t r, const F& f) const {assert(r <= n);S product = e();assert(f(product));return min_left(root, 0, n, r, f, product);}private:struct node;using node_ptr = std::unique_ptr<node>;struct node {size_t index;S value, product;node_ptr left, right;node(size_t index, S value): index(index),value(value),product(value),left(nullptr),right(nullptr) {}void update() {product = op(op(left ? left->product : e(), value),right ? right->product : e());}};const size_t n;node_ptr root;void set(node_ptr& t, size_t a, size_t b, size_t p, S x) const {if (!t) {t = std::make_unique<node>(p, x);return;}if (t->index == p) {t->value = x;t->update();return;}size_t c = (a + b) >> 1;if (p < c) {if (t->index < p) std::swap(t->index, p), std::swap(t->value, x);set(t->left, a, c, p, x);} else {if (p < t->index) std::swap(p, t->index), std::swap(x, t->value);set(t->right, c, b, p, x);}t->update();}S get(const node_ptr& t, size_t a, size_t b, size_t p) const {if (!t) return e();if (t->index == p) return t->value;size_t c = (a + b) >> 1;if (p < c) return get(t->left, a, c, p);else return get(t->right, c, b, p);}S prod(const node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {if (!t || b <= l || r <= a) return e();if (l <= a && b <= r) return t->product;size_t c = (a + b) >> 1;S result = prod(t->left, a, c, l, r);if (l <= t->index && t->index < r) result = op(result, t->value);return op(result, prod(t->right, c, b, l, r));}void reset(node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {if (!t || b <= l || r <= a) return;if (l <= a && b <= r) {t.reset();return;}size_t c = (a + b) >> 1;reset(t->left, a, c, l, r);reset(t->right, c, b, l, r);t->update();}template <class F>size_t max_right(const node_ptr& t, size_t a, size_t b,size_t l, const F& f, S& product) const {if (!t || b <= l) return n;if (f(op(product, t->product))) {product = op(product, t->product);return n;}size_t c = (a + b) >> 1;size_t result = max_right(t->left, a, c, l, f, product);if (result != n) return result;if (l <= t->index) {product = op(product, t->value);if (!f(product)) return t->index;}return max_right(t->right, c, b, l, f, product);}template <class F>size_t min_left(const node_ptr& t, size_t a, size_t b,size_t r, const F& f, S& product) const {if (!t || r <= a) return 0;if (f(op(t->product, product))) {product = op(t->product, product);return 0;}size_t c = (a + b) >> 1;size_t result = min_left(t->right, c, b, r, f, product);if (result != 0) return result;if (t->index < r) {product = op(t->value, product);if (!f(product)) return t->index + 1;}return min_left(t->left, a, c, r, f, product);}};using S = long long;S op(S a, S b){return a + b;}S e(){return 0ll;}int main(){cin.tie(0);ios_base::sync_with_stdio(false);dynamic_segtree<S,op,e> seg(1e9+1);int N; cin >> N;ll ans = 0;rep(q,N){int op; cin >> op;if(op==0){int x,y; cin >> x >> y;auto v = seg.get(x);debug(x, y, v);seg.set(x, y + v);}else{int l,r; cin >> l >> r;ans += seg.prod(l, r + 1);}}cout << ans << endl;}