結果
| 問題 |
No.789 範囲の合計
|
| コンテスト | |
| ユーザー |
 sapphire__15
|
| 提出日時 | 2023-02-26 05:04:54 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 402 ms / 1,000 ms |
| コード長 | 6,429 bytes |
| コンパイル時間 | 2,809 ms |
| コンパイル使用メモリ | 209,852 KB |
| 最終ジャッジ日時 | 2025-02-10 23:32:38 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge6 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 15 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define per(i, n) for (int i = (n)-1; 0 <= i; i--)
#define rep2(i, l, r) for (ll i = (l); i < ll(r); i++)
#define per2(i, l, r) for (int i = (r)-1; int(l) <= i; i--)
#define MM << " " <<
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)x.size()
template<typename T>
void print(const vector<T> &v, T x = 0) {
int n = v.size();
for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');
if (v.empty()) cout << '\n';
}
template<class T>
using MaxHeap = priority_queue<T>;
template<class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T>
bool chmax(T &x, const T &y) {
return (x < y) ? (x = y, true) : false;
}
template<typename T>
bool chmin(T &x, const T &y) {
return (x > y) ? (x = y, true) : false;
}
#include <algorithm>
#include <iostream>
#include <memory>
template<class T, class Merge>
class DynamicSegTree {
public:
using index_t = int64_t;
using value_t = T;
private:
struct Node;
using node_ptr = std::unique_ptr<Node>;
node_ptr body;
const T _e;
const Merge merge;
struct Node {
static constexpr index_t ub = (index_t)1
<< (numeric_limits<index_t>::digits - 1);
static constexpr index_t lb = -ub;
value_t val;
const index_t _l;
const index_t _r;
node_ptr child[2];
Node(const value_t &x, const index_t l, const index_t r)
: val(x), _l(l), _r(r), child{nullptr, nullptr} {
}
std::pair<index_t, index_t> next_lr() const {
assert(_l < _r);
auto intv = _r - _l;
if ((_l | intv) == _r) {
if (_l == 0 && _r == ub) {
return {lb, ub};
} else {
return {_l, _r + intv};
}
} else {
if (_l == lb && _r == 0) {
return {lb, ub};
} else {
return {_l - intv, _r};
}
}
}
value_t get_value() const {
return val;
}
index_t get_l() const {
return _l;
}
index_t get_r() const {
return _r;
}
void update(const index_t i,
const value_t &x,
const value_t e,
const Merge merge) {
if (get_l() + 1 == get_r()) {
val = x;
} else {
index_t mid = (get_l() + get_r()) / 2;
if (i < mid) {
if (!child[0]) {
child[0].reset(new Node(x, get_l(), mid));
}
child[0]->update(i, x, e, merge);
} else {
if (!child[1]) {
child[1].reset(new Node(x, mid, get_r()));
}
child[1]->update(i, x, e, merge);
}
val = merge(child[0] ? child[0]->get_value() : e,
child[1] ? child[1]->get_value() : e);
}
}
value_t query(index_t l,
index_t r,
const value_t e,
const Merge merge) const {
if (l <= get_l() && get_r() <= r) {
return val;
} else if (r < get_l() || get_r() < l) {
return e;
} else {
return merge(child[0] ? child[0]->query(l, r, e, merge) : e,
child[1] ? child[1]->query(l, r, e, merge) : e);
}
}
void deb(string prefix = "") const {
auto s = string("--") + to_string(val) + string("[") +
to_string(_l) + string("-") + to_string(_r) + string("]");
cout << s;
int k = prefix.size();
k += 2;
auto npre = prefix;
for (unsigned int i = 0; i < s.size(); i++) npre += " ";
if (child[1]) npre[k] = '|';
if (child[0])
child[0]->deb(npre);
else
cout << "\n";
if (child[1]) {
npre[k] = '|';
cout << npre << "\n";
cout << prefix << " *";
for (unsigned int i = 0; i < s.size() - 3; i++) cout << "-";
npre[k] = ' ';
child[1]->deb(npre);
}
}
};
void inflate() {
auto [l, r] = body->next_lr();
node_ptr next_body = std::make_unique<Node>(body->get_value(), l, r);
if (l == body->get_l()) {
next_body->child[0] = move(body);
} else {
next_body->child[1] = move(body);
}
body = move(next_body);
}
public:
DynamicSegTree(const value_t &e, const Merge merge_func)
: body(nullptr), _e(e), merge(merge_func) {
}
void update(const index_t i, const value_t &x) {
assert(Node::lb <= i);
assert(i < Node::ub);
if (body) {
while (i < body->get_l() || body->get_r() <= i) {
inflate();
}
body->update(i, x, _e, merge);
} else {
body.reset(new Node(x, i, i + 1));
}
}
value_t query(index_t l, index_t r) {
assert(Node::lb <= l);
assert(Node::lb < r);
assert(l < Node::ub);
assert(r <= Node::ub);
if (!body) {
return _e;
}
return body->query(l, r, _e, merge);
}
void deb() const {
body->deb();
cout << "\n\n";
}
};
int main() {
DynamicSegTree st(0LL, [](ll x, ll y) { return x + y; });
int n;
std::cin >> n;
ll ans = 0;
for (int i = 0; i < n; i++) {
int id;
std::cin >> id;
if (id == 0) {
int x, y;
cin >> x >> y;
st.update(x, st.query(x, x + 1) + y);
} else {
int l, r;
std::cin >> l >> r;
ans += st.query(l, r + 1);
}
}
cout << ans << endl;
}