結果

問題 No.789 範囲の合計
コンテスト
ユーザー tonegawa
提出日時 2023-05-01 13:35:13
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 140 ms / 1,000 ms
コード長 4,698 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 922 ms
コンパイル使用メモリ 76,960 KB
最終ジャッジ日時 2025-02-12 16:16:45
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <vector>
#include <cassert>
#include <limits>

template<typename monoid, typename Val>
struct sparse_segment_tree{
private:
  struct node{
    int lx, rx;
    node *l, *r;
    Val sum;
    node(int lx, int rx, Val val): lx(lx), rx(rx),
    l(nullptr), r(nullptr), sum(val){}
  };
  node *make_node(int lx, int rx, Val val = monoid::template id<Val>()){
    return new node(lx, rx, val);
  }
  Val set(node *v, int k, Val x){
    if(v->rx - v->lx == 1) return v->sum = x;
    int mid = ((long long)v->lx + v->rx) >> 1;
    if(mid <= k){
      if(!v->r) v->r = make_node(mid, v->rx);
      if(!v->l) return v->sum = set(v->r, k, x);
      else return v->sum = monoid::template merge<Val>(v->l->sum, set(v->r, k, x));
    }else{
      if(!v->l) v->l = make_node(v->lx, mid);
      if(!v->r) return v->sum = set(v->l, k, x);
      else return v->sum = monoid::template merge<Val>(set(v->l, k, x), v->r->sum);
    }
  }
  Val get(node *v, int k){
    if(!v) return monoid::template id<Val>();
    if(v->rx - v->lx == 1) return v->sum;
    int mid = ((long long)v->lx + v->rx) >> 1;
    if(mid <= k) return get(v->r, k);
    else return get(v->l, k);
  }
  Val update(node *v, int k, Val x){
    if(v->rx - v->lx == 1) return v->sum = monoid::template merge<Val>(v->sum, x);
    int mid = ((long long)v->lx + v->rx) >> 1;
    if(mid <= k){
      if(!v->r) v->r = make_node(mid, v->rx);
      if(!v->l) return v->sum = update(v->r, k, x);
      else return v->sum = monoid::template merge<Val>(v->l->sum, update(v->r, k, x));
    }else{
      if(!v->l) v->l = make_node(v->lx, mid);
      if(!v->r) return v->sum = update(v->l, k, x);
      else return v->sum = monoid::template merge<Val>(update(v->l, k, x), v->r->sum);
    }
  }
  Val query(node *v, int l, int r){
    if(!v || r <= v->lx || v->rx <= l) return monoid::template id<Val>();
    if(l <= v->lx && v->rx <= r) return v->sum;
    return monoid::template merge<Val>(query(v->l, l, r), query(v->r, l, r));
  }
  template<typename F>
  std::pair<int, Val> bisect_from_left(node *v, const int l, const F &f, Val ok){
    if(v->rx <= l) return {-1, ok};
    if(l <= v->lx){
      Val m = monoid::template merge<Val>(ok, v->sum);
      if(!f(m)) return {-1, m};
      if(v->rx - v->lx == 1) return {v->lx, m};
    }
    std::pair<int, Val> x{-1, monoid::template id<Val>()};
    if(v->l) x = bisect_from_left(v->l, l, f, ok);
    if(x.first != -1) return x;
    if(v->r) x = bisect_from_left(v->r, l, f, ok);
    return x;
  }
  template<typename F>
  std::pair<int, Val> bisect_from_right(node *v, const int r, const F &f, Val ok){
    if(r < v->lx) return {-1, ok};
    if(v->rx <= r + 1){
      Val m = monoid::template merge<Val>(v->sum, ok);
      if(!f(m)) return {-1, m};
      if(v->rx - v->lx == 1) return {v->lx, m};
    }
    std::pair<int, Val> x{-1, monoid::template id<Val>()};
    if(v->r) x = bisect_from_right(v->r, r, f, ok);
    if(x.first != -1) return x;
    if(v->l) x = bisect_from_right(v->l, r, f, ok);
    return x;
  }
  node *root;
public:
  sparse_segment_tree(): root(nullptr){}
  sparse_segment_tree(int min_x, int max_x){
    root = make_node(min_x, max_x);
  }
  void set(int k, Val x){
    assert(root);
    set(root, k, x);
  }
  Val get(int k){
    assert(root);
    return get(root, k);
  }
  void update(int k, Val x){
    assert(root);
    update(root, k, x);
  }
  Val query(int l, int r){
    assert(root);
    return query(root, l, r);
  }
  // f(sum[l, r])がtrueになる最左のr. ない場合は-1
  template<typename F>
  int bisect_from_left(int l, const F &f){
    assert(root && root->lx <= l && l < root->rx);
    assert(!f(monoid::template id<Val>()));
    return bisect_from_left(root, l, f, monoid::template id<Val>()).first;
  }
  // f(sum[l, r])がtrueになる最右のl. ない場合は-1
  template<typename F>
  int bisect_from_right(int r, const F &f){
    assert(root && root->lx <= r && r < root->rx);
    assert(!f(monoid::template id<Val>()));
    return bisect_from_right(root, r, f, monoid::template id<Val>()).first;
  }
};

struct point_add_range_sum{
  template<typename T>
  static T id(){
    return 0;
  }
  template<typename T>
  static T update(T a, T b){
    return a + b;
  }
  template<typename T>
  static T merge(T a, T b){
    return a + b;
  }
};

#include <iostream>
int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int n;
  std::cin >> n;

  sparse_segment_tree<point_add_range_sum, int> seg(0, 1000000001);

  long long ans = 0;
  for(int i = 0; i < n; i++){
    int a, b, c;
    std::cin >> a >> b >> c;
    if(!a){
      seg.update(b, c);
    }else{
      ans += seg.query(b, c + 1);
    }
  }
  std::cout << ans << '\n';
}
0