結果

問題 No.789 範囲の合計
コンテスト
ユーザー ZOI-dayo
提出日時 2024-05-30 01:29:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 8,680 bytes
コンパイル時間 6,822 ms
コンパイル使用メモリ 398,516 KB
実行使用メモリ 227,584 KB
最終ジャッジ日時 2024-12-20 21:05:30
合計ジャッジ時間 11,851 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 MLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "test/yukicoder/789__dynamic_seg.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/789"

#line 2 "common/util.hpp"

#line 2 "common/alias.hpp"

#include <boost/multiprecision/cpp_int.hpp>

#include <bits/stdc++.h>
using namespace std;
// using namespace std::views;
// using namespace boost::multiprecision;

// --- 型エイリアス ---
using ll = long long;
using ull = unsigned long long;
template <typename T> using vec = vector<T>;
template <typename T> using vvec = vector<vector<T>>;
template <typename T> using vvvec = vector<vector<vector<T>>>;
template <typename T> using p_queue = priority_queue<T>;
template <typename T> using rp_queue = priority_queue<T, vec<T>, greater<T>>;
using bint = boost::multiprecision::cpp_int;

// --- 黒魔術 ---
#define int ll

// --- 制御マクロ ---
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define all(v) begin(v), end(v)
// #define BIT(n) (1LL << (n))
#define MAX(type) numeric_limits<type>::max()
#define MIN(type) numeric_limits<type>::min()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pb push_back
#define mp make_pair
#define fir first
#define sec second

// --- 定数 ---
constexpr ll INF = 1LL << 60;
// constexpr ll INF = numeric_limits<ll>::max();

inline signed bit_width(ll x) { return bit_width((ull)x); }
inline ull bit_ceil(ll x) { return bit_ceil((ull)x); }
#line 2 "common/concepts.hpp"

#line 4 "common/concepts.hpp"

template <class T>
concept addable = requires(T a, T b) {
  { a + b } -> convertible_to<T>;
};
#line 5 "common/util.hpp"

// --- Utils ---

// 二分探索
template <typename T>
inline T bin_search(T ok, T ng, const function<bool(T)> is_ok) {
  assert(is_ok(ok));
  assert(!is_ok(ng));
  assert(ok < ng);
  while (abs(ok - ng) > 1) {
    T mid = (ok + ng) / 2;
    if (is_ok(mid))
      ok = mid;
    else
      ng = mid;
  }
  return ok;
}

// 順列全探索
inline void rep_perm(int n, function<void(vec<int> &)> f) {
  vec<int> v(n);
  iota(v.begin(), v.end(), 0);
  do {
    f(v);
  } while (next_permutation(v.begin(), v.end()));
}

inline void rep_bit(int n, function<void(int)> f) { rep(i, 1LL << n) f(i); }

// 配列 to string
template <typename T> inline string join(const vec<T> &v, string sep = " ") {
  string res = "";
  rep(i, v.size()) res += to_string(v[i]) + (i == v.size() - 1 ? "" : sep);
  return res;
}
template <typename T>
inline void join_out(ostream &os, const vec<T> &v, string sep = " ",
                     string end = "\n") {
  int n = v.size();
  rep(i, n) os << v[i] << (i == n - 1 ? end : sep);
}

template <typename T>
inline void transform(vec<T> &src, function<void(T &)> f) {
  for (auto &val : src)
    f(val);
}

// ベース指定ceil
inline ll ceil(ll x, ll base) { return (x + base - 1) / base * base; }
// ベース指定floor
inline ll floor(ll x, ll base) { return x / base * base; }

// 合計値を求める
// ll sum(const vec<ll> &v) { return accumulate(all(v), 0LL); }
template <addable T> T sum(const vec<T> &v) { return accumulate(all(v), T()); }

// 可変引数min
template <class... T> auto min(T... a) {
  return min(initializer_list<common_type_t<T...>>{a...});
}

// 可変引数max
template <class... T> auto max(T... a) {
  return max(initializer_list<common_type_t<T...>>{a...});
}

template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}

// 3項間不等式
// 広義単調増加
inline bool is_increasing(int x, int y, int z) { return x <= y && y <= z; }

// 半開区間[x, z)にyが含まれるか?
inline bool is_contained(int x, int y, int z) { return x <= y && y < z; }

// 頂点(x, y)が範囲に含まれるか
inline bool is_contained(int H, int W, int x, int y) {
  return is_contained(0, x, H) && is_contained(0, y, W);
}

// rootに対し、aとbが同じ側にあるか (=は含まない)
inline bool is_same_side(int root, int a, int b) {
  return (root < a) == (root < b);
}

// vector継承にする?
template <typename T> struct vec_accumulate : public vec<T> {
  explicit vec_accumulate(vec<T> &v) : vec<T>(v.size()) {
    assert(v.size() > 0);
    this->at(0) = v[0];
    for (int i = 1; i < v.size(); ++i)
      this->at(i) = this->at(i - 1) + v[i];
  }

  // [0, i]の和
  // なので、-1 <= i < size()
  T operator[](int i) {
    assert(is_contained(-1, i, this->size()));
    if (i == -1)
      return T();
    return this->at(i);
  }
};

// vector func
template <typename T> inline void unique_erase(vec<T> &v) {
  sort(all(v));
  v.erase(unique(all(v)), v.end());
}

void io_setup() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << std::fixed << std::setprecision(15);
}
#line 2 "datastructure/dynamic-segment-tree.hpp"

#line 4 "datastructure/dynamic-segment-tree.hpp"

/**
 * @brief セグメント木
 *
 * @tparam T ノードの型
 */
template <typename T> struct DynamicSegmentTree {

private:
  /// 単位元
  T e;
  /// 演算
  function<T(T, T)> op;

  /// 要素数
  int n;

  /// ノードの構造体
  struct Node {

    /// ノードの値
    T val;

    /// 初期化用の値
    T e;

    /// 親ノード, 左の子ノード, 右の子ノード
    Node *p, *l_child, *r_child;

    /// ノードの範囲
    int l, r;

    Node(T val, T e, int l, int r) :
      val(val), e(e),
      p(nullptr), l_child(nullptr), r_child(nullptr),
      l(l), r(r) {}

    Node(T val, Node *p, bool child_index) :
      val(val), e(p->e),
      p(p), l_child(nullptr), r_child(nullptr),
      l(!child_index ? p->l : p->mid()),
      r(!child_index ? p->mid() : p->r) {}

    /// ノードの範囲の中央
    int mid() const { return (l + r) / 2; }

    /// 子ノードを取得する
    Node* child(bool child_index) {
      if(child_index == 0) {
        if(l_child == nullptr) l_child = new Node(e, this, 0);
        return l_child;
      } else {
        if(r_child == nullptr) r_child = new Node(e, this, 1);
        return r_child;
      }
    }

    /// 子ノードの情報からvalを更新する
    void update(auto &op) {
      T l_val = l_child == nullptr ? e : l_child->val;
      T r_val = r_child == nullptr ? e : r_child->val;
      val = op(l_val, r_val);
    }
  };

  Node* root;

public:
  /**
   * @brief 個数から空のSegmentTreeを生成する O(1)
   *
   * @param length 要素数
   * @param e 単位元
   * @param op 演算
   */
  inline explicit DynamicSegmentTree(int length, T e, function<T(T, T)> op)
      : e(e), op(op), n(bit_ceil(length)), root(new Node(e, e, 0, n)) {}

  /**
    * @brief i番目の要素を取得する O(log n)
    */
  inline Node* get_node(int i) const {
    Node *node = root;
    while(node->l + 1 < node->r) {
      node = node->child(node->mid() <= i);
    }
    return node;
  }

  /**
   * @brief i番目の要素を変更する O(log n) * op
   *
   * @param i インデックス (0-indexed)
   * @param a 更新後の要素
   */
  inline void set(int i, T a) {
    Node *node = get_node(i);
    node->val = a;
    while(node->p != nullptr) {
      node = node->p;
      node->update(op);
    }
  }

  /**
   * @brief i番目の要素を取得する O(log n)
   *
   * @param i インデックス (0-indexed)
   * @return i番目の要素
   */
  inline T get(int i) const { return get_node(i)->val; }

  /**
   * @brief [l, r)の範囲に対するクエリを行う O(log n) * op
   *
   * @param l クエリの左端 (0-indexed)
   * @param r クエリの右端 (0-indexed)
   * @return クエリの結果
   */
  inline T query(int l, int r) const {
    return _query(root, l, r);
  }

private:
  /**
    * @brief 特定のノードに対し、[l, r)の範囲に対するクエリを行う O(log n) * op
    *
    * @param node クエリを行うノード
    * @param l クエリの左端 (0-indexed)
    * @param r クエリの右端 (0-indexed)
    * @return クエリの結果
    */
  inline T _query(Node *node, int l, int r) const {
    if(r <= node->l || node->r <= l) return e;
    if(l <= node->l && node->r <= r) return node->val;
    return op(_query(node->child(0), l, r), _query(node->child(1), l, r));
  }

};
#line 5 "test/yukicoder/789__dynamic_seg.test.cpp"

signed main() {
  io_setup();
  int N;
  cin >> N;

  DynamicSegmentTree<int> seg(1'000'000'001, 0, [](int a, int b) { return a + b; });
  int ans = 0;
  rep(i, N) {
    int type;
    cin >> type;
    if(type == 0) {
      int x, y;
      cin >> x >> y;
      seg.set(x, seg.get(x) + y);
    } else {
      int l, r;
      cin >> l >> r;
      ans += seg.query(l, r + 1);
    }
  }
  cout << ans << endl;
}
0