#1169822 (C++23) No.789 範囲の合計

• 問題: No.789 範囲の合計
• ユーザー: hidehic0
• 提出日時: 2026-06-29 17:12:14
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 172 ms / 1,000 ms
• コード長: 6,685 bytes
• コンパイル時間: 2,222 ms
• コンパイル使用メモリ: 339,960 KB
• 実行使用メモリ: 34,816 KB
• 最終ジャッジ日時: 2026-06-29 17:12:44
• 合計ジャッジ時間: 4,835 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
other	AC * 15

ソースコード

#line 1 "test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/789"
#include <bits/stdc++.h>
using namespace std;

#line 7 "/home/hidehic0/src/github.com/hidehic0/library_cpp/templates/alias.hpp"

template <class T> using VC = std::vector<T>;
template <class T>
using rpriority_queue = std::priority_queue<T, VC<T>, std::greater<T>>;
using ll = long long;
using ld = long double;
using pii = std::pair<ll, ll>;
using vi = VC<ll>;
using vvi = VC<vi>;
using vvvi = VC<vvi>;
using vb = VC<bool>;
using vvb = VC<vb>;
using vf = VC<double>;
using vvf = VC<vf>;
using vpii = VC<pii>;
using vvpii = VC<vpii>;
using si = std::set<ll>;
using spii = std::set<pii>;
using mii = std::map<ll, ll>;
const std::string upperlist = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const std::string lowerlist = "abcdefghijklmnopqrstuvwxyz";
#define mp make_pair
#define dms << " " <<

constexpr int MOD998 = 998244353;
#line 4 "/home/hidehic0/src/github.com/hidehic0/library_cpp/templates/macro.hpp"

// 引数の長さで内容が変わるrep 参考: https://trap.jp/post/1224
#define overload4(a, b, c, d, ...) d
#define _rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rep(...) overload4(__VA_ARGS__, REP, _rep)(__VA_ARGS__)
#define _rrep(i, n) for (int i = n - 1; i >= 0; i--)
#define RREP(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); i--)
#define rrep(...) overload4(__VA_ARGS__, RREP, _rrep)(__VA_ARGS__)

#define all(a) (a).begin(), (a).end()

template <typename T> bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T> bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

template <typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
  for (T &in : v)
    is >> in;
  return is;
}

template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    os << v[i] << (i + 1 == v.size() ? "" : " ");
  }
  return os;
}

// pythonのprintライクな関数 参考:
// https://nyaannyaan.github.io/library/template/inout.hpp
inline void out() { std::cout << std::endl; }
template <typename T, typename... U, char sep = ' '>
void out(const T &t, const U &...u) {
  std::cout << t;

  if (sizeof...(u))
    std::cout << sep;

  out(u...);
}

// cinの短縮関数 参考: https://nyaannyaan.github.io/library/template/inout.hpp
inline void in() {}
template <typename T, class... U> void in(T &t, U &...u) {
  std::cin >> t;
  in(u...);
}

template <typename T> inline T ceil_div(T a, T b) { return (a + b - 1) / b; }
template <typename T> inline T mod_pow(T a, T n, T mod) {
  T res = 1;
  while (n) {
    if (n % 2 != 0) {
      res *= a;
      res %= mod;
    }

    a *= a;
    a %= mod;

    n >>= 1;
  }

  return res;
}
template <typename T> inline T minus_mod(T a, T b) { return ((a % b) + b) % b; }

template <typename T> void apply_vec(std::vector<T> &v, T (*fn)(T)) {
  for (int i = 0; i < v.size(); i++)
    v[i] = fn(v[i]);
}

template <typename T, class Comp> struct Top2 {
  T a, b;

  Top2() {}
  Top2(T a) : a(a) {}
  Top2(T a, T b) : a(a), b(b) {}

  void add(const T &v) {
    if (Comp{}(v, a))
      b = a, a = v;
    else if (Comp{}(v, b))
      b = v;
  }

  friend Top2<T, Comp> operator*(const Top2<T, Comp> &lhs,
                                 const Top2<T, Comp> &rhs) {
    auto n = lhs;
    n.add(rhs.a), n.add(rhs.b);

    return n;
  }

  Top2<T, Comp> &operator*=(const Top2<T, Comp> &rhs) {
    (*this) = (*this) * rhs;

    return *this;
  }
};

template <typename T> struct TopMin2 : public Top2<T, std::less<T>> {
  using Top2<T, std::less<T>>::Top2;
};

template <typename T> struct TopMax2 : public Top2<T, std::greater<T>> {
  using Top2<T, std::greater<T>>::Top2;
};
#line 7 "test.cpp"

#line 3 "/home/hidehic0/src/github.com/hidehic0/library_cpp/segtree/dynamic-segtree.hpp"

template <class S, auto op, auto e> struct DynamicSegtree {
  static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                "op must work as S(S, S)");
  static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                "e must work as S()");

public:
  long long _n;

  DynamicSegtree(long long n) : _n(n), root(nullptr) {}

  void set(long long p, const S &x) {
    assert(0 <= p && p < _n);
    set(root, 0, _n, p, x);
  }

  std::optional<S> get(long long p) {
    assert(0 <= p && p < _n);
    return get(root, 0, _n, p);
  }

  S prod(long long l, long long r) {
    assert(0 <= l && l <= r && r <= _n);

    return prod(root, 0, _n, l, r);
  }

private:
  struct Node;
  using node_ptr = std::unique_ptr<Node>;

  struct Node {
    S value;

    node_ptr left, right;

    Node(S value) : value(value), left(nullptr), right(nullptr) {}
  };

  node_ptr root;

  void set(node_ptr &node, long long a, long long b, long long p, const S &x) {
    if (!node)
      node = std::make_unique<Node>(e());

    if (b - a == 1) {
      node->value = x;
      return;
    }

    long long mid = (a + b) >> 1LL;

    if (p < mid)
      set(node->left, a, mid, p, x);
    else
      set(node->right, mid, b, p, x);

    node->value = e();

    if (node->left)
      node->value = op(node->value, node->left->value);
    if (node->right)
      node->value = op(node->value, node->right->value);
  }

  std::optional<S> get(const node_ptr &node, long long a, long long b,
                       long long p) {
    if (!node)
      return std::nullopt;
    if (b - a == 1)
      return node->value;

    long long mid = (a + b) >> 1LL;

    if (p < mid)
      return get(node->left, a, mid, p);
    else
      return get(node->right, mid, b, p);
  }

  S prod(const node_ptr &node, long long a, long long b, long long l,
         long long r) {
    if (!node || b <= l || r <= a)
      return e();

    if (l <= a && b <= r)
      return node->value;

    long long mid = (a + b) >> 1;

    return op(prod(node->left, a, mid, l, r), prod(node->right, mid, b, l, r));
  }
};
#line 9 "test.cpp"

int main() {
  ll Q;
  in(Q);

  DynamicSegtree<ll, [](ll a, ll b) { return a + b; }, []() { return 0; }> seg(
      1e9 + 10);

  ll ans = 0;

  while (Q--) {
    ll t;
    in(t);

    if (t == 0) {
      ll x, y;
      in(x, y);

      auto t = seg.get(x);

      if (!t)
        seg.set(x, y);
      else
        seg.set(x, *t + y);
    } else {
      ll l, r;
      in(l, r);

      ans += seg.prod(l, r + 1);
    }
  }

  out(ans);
}