結果
| 問題 |
No.789 範囲の合計
|
| コンテスト | |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2019-02-19 17:00:36 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 407 ms / 1,000 ms |
| コード長 | 7,253 bytes |
| コンパイル時間 | 1,890 ms |
| コンパイル使用メモリ | 201,972 KB |
| 最終ジャッジ日時 | 2025-01-06 21:15:49 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 15 |
ソースコード
#include <bits/stdc++.h>
//!===========================================================!//
//! dP dP dP !//
//! 88 88 88 !//
//! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !//
//! 88 88 88ooood8 88' `88 88' `88 88ooood8 88' `88 !//
//! 88 88 88. ... 88. .88 88. .88 88. ... 88 !//
//! dP dP `88888P' `88888P8 `88888P8 `88888P' dP !//
//!===========================================================!//
using ld = long double;
using ll = long long;
std::mt19937 mt{std::random_device{}()};
template <typename F>
constexpr F PI() { return 3.1415926535897932385; }
template <typename T, std::size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
template <typename T, typename A>
std::ostream& operator<<(std::ostream& os, const std::deque<T, A>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
template <typename K, typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::multimap<K, T, C, A>& v)
{
os << "[";
for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
return (os << "]" << std::endl);
}
template <typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::multiset<T, C, A>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
template <typename K, typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::map<K, T, C, A>& v)
{
os << "[";
for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
return (os << "]" << std::endl);
}
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& v) { return (os << "<" << v.first << "," << v.second << ">"); }
template <typename T, typename C, typename A>
std::ostream& operator<<(std::ostream& os, const std::set<T, C, A>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
template <typename K, typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_multimap<K, T, H, P, A>& v)
{
os << "[";
for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
return (os << "]" << std::endl);
}
template <typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_multiset<T, H, P, A>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
template <typename K, typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_map<K, T, H, P, A>& v)
{
os << "[";
for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; }
return (os << "]" << std::endl);
}
template <typename T, typename H, typename P, typename A>
std::ostream& operator<<(std::ostream& os, const std::unordered_set<T, H, P, A>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
template <typename T, typename A>
std::ostream& operator<<(std::ostream& os, const std::vector<T, A>& v)
{
os << "[";
for (const auto& e : v) { os << e << ","; }
return (os << "]" << std::endl);
}
#define show(x) std::cerr << #x << " = " << (x) << std::endl
//!==============================================================================================!//
//! 888888ba oo .d88888b !//
//! 88 `8b 88. "' !//
//! 88 88 dP dP 88d888b. .d8888b. 88d8b.d8b. dP .d8888b. `Y88888b. .d8888b. .d8888b. !//
//! 88 88 88 88 88' `88 88' `88 88'`88'`88 88 88' `"" `8b 88ooood8 88' `88 !//
//! 88 .8P 88. .88 88 88 88. .88 88 88 88 88 88. ... d8' .8P 88. ... 88. .88 !//
//! 8888888P `8888P88 dP dP `88888P8 dP dP dP dP `88888P' Y88888P `88888P' `8888P88 !//
//! .88 .88 !//
//! d8888P d8888P !//
//!=================================================================--===========================!//
template <typename Monoid, std::size_t SUPBIT = 30, typename Ind = std::size_t>
class DynamicSeg
{
public:
static constexpr Ind SUP = (Ind)1 << SUPBIT;
using BaseMonoid = Monoid;
using T = typename Monoid::T;
DynamicSeg() : root{std::make_shared<Node>()} {}
T get(const Ind a) const
{
Ptr p = root;
Ind L = 0, R = SUP;
for (; p->left;) {
const Ind M = (L + R) / 2;
p = (a < M ? p->left : p->right), (a < M ? R : L) = M;
}
return p->V;
}
void set(const Ind a, const T& val)
{
auto rec = [&](auto&& self, const Ptr p, Ind L, Ind R) -> void {
if (L == a and R == a + 1) {
p->V = val;
} else {
if (not p->left) { p->bear(); }
const Ind M = (L + R) / 2;
Ptr next = (a < M ? p->left : p->right);
(a < M ? R : L) = M, self(self, next, L, R);
p->V = acc(p->left->V, p->right->V);
}
};
rec(rec, root, 0, SUP);
}
T accumulate(const Ind L, const Ind R) const
{
auto rec = [&](auto&& self, const Ptr p, const Ind l, const Ind r, const Ind L, const Ind R) -> T {
if (L >= r or R <= l) { return Monoid::id(); }
if (l == L and r == R) { return p->V; }
if (not p->left) { return p->V; }
const Ind M = (L + R) / 2;
const T lv = self(self, p->left, l, std::min(M, r), L, M), rv = self(self, p->right, std::max(l, M), r, M, R);
return acc(lv, rv);
};
return rec(rec, root, L, R, 0, SUP);
}
private:
const Monoid acc{};
struct Node
{
Node() : V{Monoid::id()} {}
void bear() { left = std::make_shared<Node>(), right = std::make_shared<Node>(); }
using Ptr = std::shared_ptr<Node>;
T V;
Ptr left, right;
};
using Ptr = typename Node::Ptr;
Ptr root;
};
struct Monoid
{
using T = ll;
T operator()(const T& a, const T& b) const { return a + b; }
static constexpr T id() { return 0; }
};
int main()
{
DynamicSeg<Monoid, 40> dseg;
int Q;
std::cin >> Q;
ll ans = 0;
for (int q = 0; q < Q; q++) {
int t;
std::cin >> t;
if (t == 0) {
int x;
ll y;
std::cin >> x >> y;
dseg.set(x, dseg.get(x) + y);
} else {
int l, r;
std::cin >> l >> r, r++;
ans += dseg.accumulate(l, r);
}
}
std::cout << ans << std::endl;
return 0;
}