結果

問題 No.789 範囲の合計
ユーザー tonegawatonegawa
提出日時 2023-05-01 16:58:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,544 bytes
コンパイル時間 996 ms
コンパイル使用メモリ 101,928 KB
実行使用メモリ 814,848 KB
最終ジャッジ日時 2024-04-30 17:45:49
合計ジャッジ時間 4,351 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 MLE -
testcase_03 WA -
testcase_04 WA -
testcase_05 MLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<typename monoid, typename Val>
struct persistent_segment_tree_iter;

#include <random>
unsigned long long random_once(){
  static unsigned long long ret = 0;
  if(ret == 0){
    std::random_device seed_gen;
    std::mt19937_64 engine(seed_gen());
    return ret = engine();
  }
  return ret;
}

int X = random_once();

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

template<typename monoid, typename Val>
struct persistent_segment_tree_iter{
private:
  using I = int;
  using node = persistent_segment_tree<monoid, Val, I>;
  using iter = persistent_segment_tree_iter<monoid, Val>;
  I minx, maxx;
  int h;
  node *root;
  persistent_segment_tree_iter(I minx, I maxx, node *v): minx(minx), maxx(maxx), root(v){}
public:
  persistent_segment_tree_iter(I _minx, I _maxx):minx(0), root(nullptr){
    I tmp = 1;
    int c = 0;
    while(tmp < _maxx) tmp <<= 1, c++;
    h = c;
    maxx = tmp;
  }
  iter set(I k, Val x){
    assert(minx <= k && k < maxx);
    node *r = root;
    node::set(r, X ^ k, x, minx, maxx);
    return iter(minx, maxx, r);
  }
  iter update(int k, Val x){
    assert(minx <= k && k < maxx);
    node *r = root;
    node::update(r, (X ^ k) % maxx, x, minx, maxx);
    return iter(minx, maxx, r);
  }
  Val get(I k){
    assert(minx <= k && k < maxx);
    return node::get(root, X ^ k, minx, maxx);
  }
  Val query(I l, I r){
    assert(minx <= l && r <= maxx);
    return node::query(root, l, r, minx, maxx, h - 1);
  }
  // f(sum[l, r])がtrueになる最左のr. ない場合はmaxx
  template<typename F>
  int bisect_from_left(I l, const F &f){
    assert(minx <= l && l < maxx);
    Val x = monoid::template id<Val>();
    return node::bisect_from_left(root, l, f, minx, maxx, x, maxx);
  }
  // f(sum[l, r])がtrueになる最右のl. ない場合はmaxx
  template<typename F>
  int bisect_from_right(int r, const F &f){
    assert(minx <= r && r < maxx);
    Val x = monoid::template id<Val>();
    return node::bisect_from_right(root, r, f, minx, maxx, x, maxx);
  }
};


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