結果

問題 No.789 範囲の合計
ユーザー tonegawatonegawa
提出日時 2023-05-01 16:27:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 189 ms / 1,000 ms
コード長 5,410 bytes
コンパイル時間 808 ms
コンパイル使用メモリ 78,972 KB
実行使用メモリ 68,096 KB
最終ジャッジ日時 2024-04-30 17:34:21
合計ジャッジ時間 4,081 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 174 ms
54,400 KB
testcase_03 AC 117 ms
54,272 KB
testcase_04 AC 189 ms
61,440 KB
testcase_05 AC 142 ms
51,840 KB
testcase_06 AC 148 ms
54,528 KB
testcase_07 AC 135 ms
67,840 KB
testcase_08 AC 163 ms
68,096 KB
testcase_09 AC 145 ms
61,440 KB
testcase_10 AC 136 ms
35,840 KB
testcase_11 AC 133 ms
60,160 KB
testcase_12 AC 135 ms
60,288 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<typename monoid, typename Val>
struct persistent_segment_tree_iter;

template<typename monoid, typename Val>
struct persistent_segment_tree{
private:
  using node = persistent_segment_tree<monoid, Val>;
  node *l, *r;
  Val sum;
  persistent_segment_tree(){}
  persistent_segment_tree(Val val): l(nullptr), r(nullptr), sum(val){}
  static node *make_node(Val x = monoid::template id<Val>()){
    return new node(x);
  }
  static node *copy_node(node *v){
    if(!v) return new node(monoid::template id<Val>());
    return new node(*v);
  }
  static node *eval(node *v){
    v->sum = monoid::template merge<Val>(v->l ? v->l->sum : monoid::template id<Val>(), v->r ? v->r->sum : monoid::template id<Val>());
    return v;
  }
  static node *set(node *v, int k, Val x, int l, int r){
    v = copy_node(v);
    if(r - l == 1){
      v->sum = x;
      return v;
    }
    int mid = ((long long)l + r) >> 1;
    if(mid <= k) v->r = set(v->r, k, x, mid, r);
    else v->l = set(v->l, k, x, l, mid);
    return eval(v);
  }
  static node *update(node *v, int k, Val x, int l, int r){
    v = copy_node(v);
    if(r - l == 1){
      v->sum = monoid::template merge<Val>(v->sum, x);
      return v;
    }
    int mid = ((long long)l + r) >> 1;
    if(mid <= k) v->r = update(v->r, k, x, mid, r);
    else v->l = update(v->l, k, x, l, mid);
    return eval(v);
  }
  static Val get(node *v, int k, int l, int r){
    if(!v) return monoid::template id<Val>();
    if(r - l == 1) return v->sum;
    int mid = ((long long)l + r) >> 1;
    if(mid <= k) return get(v->r, k, mid, r);
    else return get(v->l, k, l, mid);
  }
  static Val query(node *v, int a, int b, int l, int r){
    if(!v || b <= l || r <= a) return monoid::template id<Val>();
    if(a <= l && r <= b) return v->sum;
    int mid = ((long long)l + r) >> 1;
    return monoid::template merge<Val>(query(v->l, a, b, l, mid), query(v->r, a, b, mid, r));
  }
  template<typename F>
  static std::pair<int, Val> bisect_from_left(node *v, const int l, int a, int b, const F &f, Val ok){
    if(b <= l) return {-1, ok};
    if(l <= a){
      Val m = monoid::template merge<Val>(ok, v->sum);
      if(!f(m)) return {-1, m};
      if(b - a == 1) return {a, m};
    }
    std::pair<int, Val> x{-1, monoid::template id<Val>()};
    int mid = (a + b) >> 1;
    if(v->l) x = bisect_from_left(v->l, l, a, mid, f, ok);
    if(x.first != -1) return x;
    if(v->r) x = bisect_from_left(v->r, l, mid, b, f, ok);
    return x;
  }
  template<typename F>
  static std::pair<int, Val> bisect_from_right(node *v, const int r, int a, int b, const F &f, Val ok){
    if(r < a) return {-1, ok};
    if(b <= r + 1){
      Val m = monoid::template merge<Val>(v->sum, ok);
      if(!f(m)) return {-1, m};
      if(b - a == 1) return {a, m};
    }
    std::pair<int, Val> x{-1, monoid::template id<Val>()};
    int mid = (a + b) >> 1;
    if(v->r) x = bisect_from_right(v->r, r, mid, b, f, ok);
    if(x.first != -1) return x;
    if(v->l) x = bisect_from_right(v->l, r, a, mid, f, ok);
    return x;
  }
  friend persistent_segment_tree_iter<monoid, Val>;
};

template<typename monoid, typename Val>
struct persistent_segment_tree_iter{
private:
  using node = persistent_segment_tree<monoid, Val>;
  using iter = persistent_segment_tree_iter<monoid, Val>;
  int lx, rx;
  node *root;
  persistent_segment_tree_iter(int minx, int maxx, node *v): lx(minx), rx(maxx), root(v){}
public:
  persistent_segment_tree_iter(int minx, int maxx): lx(minx), rx(maxx){
    assert(lx < rx);
    root = node::make_node();
  }
  iter set(int k, Val x){
    assert(lx <= k && k < rx);
    return iter(lx, rx, node::set(root, k, x, lx, rx));
  }
  iter update(int k, Val x){
    assert(lx <= k && k < rx);
    return iter(lx, rx, node::update(root, k, x, lx, rx));
  }
  Val get(int k){
    assert(lx <= k && k < rx);
    return node::get(root, k, lx, rx);
  }
  Val query(int l, int r){
    assert(lx <= l && r <= rx);
    return node::query(root, l, r, lx, rx);
  }
  // f(sum[l, r])がtrueになる最左のr. ない場合は-1
  template<typename F>
  int bisect_from_left(int l, const F &f){
    assert(root && lx <= l && l < rx);
    assert(!f(monoid::template id<Val>()));
    return node::bisect_from_left(root, l, lx, rx, 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 && lx <= r && r < rx);
    assert(!f(monoid::template id<Val>()));
    return node::bisect_from_right(root, r, lx, rx, 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;

  persistent_segment_tree_iter<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 = seg.update(b, c);
    }else{
      ans += seg.query(b, c + 1);
    }
  }
  std::cout << ans << '\n';
}
0