結果

問題 No.789 範囲の合計
コンテスト
ユーザー tonegawa
提出日時 2023-05-16 05:50:12
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 139 ms / 1,000 ms
コード長 2,580 bytes
コンパイル時間 2,349 ms
コンパイル使用メモリ 109,476 KB
最終ジャッジ日時 2025-02-13 00:46:09
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

ソースコード

diff # 

#pragma once
#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>

template<typename Val>
struct sparse_binary_indexed_tree{
private:
  using I = int;
  static constexpr int bitlen = sizeof(I) * 8;
  // idxの2進数においてk-bitから下位bitに向けて1がいくつ続くか
  static int count_consecutive_one(I idx, int k){
    static_assert(bitlen == 32 || bitlen == 64);
    if(bitlen == 32) return __builtin_clz(~((uint32_t)idx << (31 - k)));
    return __builtin_clzll(~((uint64_t)idx << (63 - k)));
  }
  static int count_trailing_one(I idx){
    static_assert(bitlen == 32 || bitlen == 64);
    if(bitlen == 32) return __builtin_ctz(~(uint32_t)idx);
    return __builtin_ctzll(~(uint64_t)idx);
  }
  I maxn;
  int h;
  struct node{
    I idx;
    std::vector<node*> ch;
    Val val, sum;
    node(I idx, Val val): idx(idx), val(val), sum(val){}
  };
  node *root;
  void update(node* &v, I idx, Val x, int h_cur){
    if(!v) v = new node(idx, x);
    else v->sum += x;
    if(h_cur == -1 || count_trailing_one(idx) == h_cur + 1) return; // 残りの下位bitが全て1なら終了
    int k = count_consecutive_one(idx, h_cur);
    if(v->ch.size() <= k) v->ch.resize(k + 1, nullptr);

    update(v->ch[k], idx, x, h_cur - 1 - k);
  }
  Val query(node *v, I idx, int h_cur){
    if(!v || h_cur == -1) return Val(0);
    Val res = Val(0);
    int k = count_consecutive_one(idx, h_cur);
    int maxk = std::min(k, (int)v->ch.size());
    for(int i = 0; i < maxk; i++) if(v->ch[i]) res += v->ch[i]->sum;
    if(v->ch.size() > k) res += query(v->ch[k], idx, h_cur - 1 - k);
    return res;
  }
public:
  sparse_binary_indexed_tree(): root(nullptr){}
  // [0, n)
  sparse_binary_indexed_tree(I n): root(nullptr){
    n = std::max(n + 1, 2);
    maxn = 1, h = 0;
    while(maxn < n) maxn <<= 1, h++;
  }
  void update(I idx, Val x){
    assert(0 <= idx && idx < maxn);
    update(root, idx, x, h - 1);
  }
  Val query(I r){
    assert(0 <= r && r <= maxn);
    return query(root, r, h - 1);
  }
  Val query(I l, I r){
    assert(0 <= l && l <= r && r <= maxn);
    if(l == r) return Val(0);
    return query(root, r, h - 1) - query(root, l, h - 1);
  }
};

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

  sparse_binary_indexed_tree<long long> t(1000000001);

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