Submit Info #3029

Problem Lang User Status Time Memory
Point Add Range Sum cpp tkr987 AC 1081 ms 42.36 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.62 MiB
max_random_00 AC 1055 ms 42.36 MiB
max_random_01 AC 1055 ms 42.24 MiB
max_random_02 AC 1081 ms 42.36 MiB
max_random_03 AC 1072 ms 42.29 MiB
max_random_04 AC 1061 ms 42.35 MiB
random_00 AC 859 ms 40.49 MiB
random_01 AC 905 ms 40.98 MiB
random_02 AC 544 ms 9.36 MiB
random_03 AC 239 ms 36.38 MiB
random_04 AC 313 ms 35.99 MiB

#include <bits/stdc++.h> //#include <boost/multiprecision/cpp_int.hpp> /***** type *****/ using namespace std; using ll = long long; using ld = long double; template <class T> using vt = vector<T>; template <class T> using vvt = vector<vector<T>>; template <class T> using vvvt = vector<vector<vector<T>>>; //using ml = boost::multiprecision::cpp_int; /***** define *****/ #define all(c) (c).begin(), (c).end() // begin to end #define rep(i, b, e) for (ll i = b; i < e; i++) // repeat #define repr(i, b, e) for (ll i = b; e < i; i--) // repeat reverse #define val(itr) *(itr) // get value /***** const value *****/ #define llong_max 9223372036854775807 // 9 * 10^18 #define ldbl_max 1.79769e+308 // 1.7 * 10^308 #define mod 1000000007 // 1e9 + 7 #define pi 3.14159265358979323846 // 3.14 ... /***** for each macro *****/ #define fori(i, ...) if(ll i = -1) for(__VA_ARGS__) if(i++, true) #define each(i, e, c) fori(i, auto e = c.begin(); e != c.end(); ++e) #define forir(i, v, ...) if(ll i = Size(v)) for(__VA_ARGS__) if(i--, true) #define eachr(i, e, c) forir(i, auto e = c.rbegin(); e != c.rend(); ++e) /***** lambda *****/ auto Count = [] // long long count value (auto b, auto e, auto x) { return (ll)count(b, e, x); }; auto CtoN = [] // char to number (auto c) { return (ll)(c - '0'); }; auto DivC = [] // long double div ceiling (auto a, auto b) { return ceil((ld)a / (ld)b); }; auto Fix = [] // fix value (auto b, auto e, auto fix) { for (auto it = b; it != e; ++it)*it += fix; }; auto Pow = [] // long long pow (auto a, auto b) { return (ll)pow(a, b); }; auto Pow2 = [] // long long pow2 (auto n) { return (1LL << n); }; auto Pow10 = [] // long long pow10 (auto n) { return (ll)pow(10, n); }; auto Size = [] // long long collection size (auto& c) { return (ll)(c).size(); }; auto Sum = [] // long long accumulate (auto b, auto e) { return accumulate(b, e, 0LL); }; /***** template *****/ template <class T> vvt<T> VVT (ll ys, ll xs, T fill = T()) { // vector<vector<T>> resize + fill vvt<T> v(ys); each(i, y, v) { val(y).resize(xs, fill); } return v; } template <class T> vvvt<T> VVVT (ll zs, ll ys, ll xs, T fill = T()) { // vector<vector<vector<T>>> resize + fill vvvt<T> v(zs); each(i, z, v) { val(z) = VVT(ys, xs, fill); } return v; } template <class T> vt<T> InputVT (ll size, T fix = T()) { // input vector<T> (T != struct) + fix vt<T> v(size); each(i, e, v) { cin >> val(e); val(e) += fix; } return v; } template <class T> vvt<T> InputVVT (ll ys, ll xs, T fix = T()) { // input vector<vector<T>> (T != struct) + fix vvt<T> v(ys); each(i, y, v) val(y).resize(xs); each(i, y, v) each(j, x, val(y)) { cin >> val(x); val(x) += fix; } return v; } template <class T> vvvt<T> InputVVVT (ll zs, ll ys, ll xs, T fix = T()) { // input vector<vector<vector<T>>> (T != struct) + fix vvvt<T> v(zs); each(i, z, v) { val(z) = InputVVT<T>(ys, xs, fix); } return v; } namespace NyaGadget { /*** 遅延評価セグメント木ライブラリ ***/ template <class T> struct Vertex { // 各頂点は対象閉区間[l,r]の合計値を持つ T value; // 頂点の値 long long lazy; // 遅延評価値 long long l; // 対象閉区間最小値 long long r; // 対象閉区間最大値 }; template <class T> struct LazySegmentTree { vector<Vertex<T>> tree; /** @brief コンストラクタ @note 初期値0で[0,n]を処理する木を作る **/ LazySegmentTree(long long n) { long long tsize = 2 * (long long)pow(2, ceil(log2(n))) - 1; tree.resize(tsize); long long depth = 1; long long range = tsize / 2; tree[0] = { 0, 0, 0, range }; for (long long i = 1; i < tsize; i++) { // 各ノードの区間範囲を設定する tree[i] = { 0, 0, tree[i - 1].l + range + 1, tree[i - 1].r + range + 1 }; if (i == pow(2, depth) - 1) { depth++; range /= 2; tree[i] = { 0, 0, 0, range }; } } } /** @brief コンストラクタ @note 初期値を配列vで与えて木を作る。 **/ LazySegmentTree(vector<T>& v) { long long tsize = 2 * (long long)pow(2, ceil(log2(Size(v)))) - 1; tree.resize(tsize); long long depth = 1; long long range = tsize / 2; tree[0] = { 0, 0, 0, range }; for (long long i = 1; i < tsize; i++) { // 各ノードの区間範囲を設定する tree[i] = { 0, 0, tree[i - 1].l + range + 1, tree[i - 1].r + range + 1 }; if (i == pow(2, depth) - 1) { depth++; range /= 2; tree[i] = { 0, 0, 0, range }; } } for (long long i = 0; i < (long long)v.size(); i++) tree[i + tsize / 2].value = v[i]; for (long long i = tsize / 2 - 1; -1 < i; i--) tree[i].value = tree[i * 2 + 1].value + tree[i * 2 + 2].value; } /** @brief 区間に対して加算処理をする関数 @param l 加算する区間の左端 @param r 加算する区間の右端 @param v 加算する値 @param vi 頂点インデックス @note [l, r]の区間にvを加算する **/ void Add(long long l, long long r, T v, long long vi = 0) { //Propagate(vi); // 完全に加算区間範囲外のとき枝刈り if (r < tree[vi].l || tree[vi].r < l) return; if (l <= tree[vi].l && tree[vi].r <= r) { // 加算区間に全範囲が含まれる tree[vi].lazy += (tree[vi].r - tree[vi].l + 1) * v; Propagate(vi); } else { // 加算区間に一部範囲が含まれる Add(l, r, v, 2 * vi + 1); Add(l, r, v, 2 * vi + 2); tree[vi].value = tree[2 * vi + 1].value + tree[2 * vi + 2].value; } } /** @brief 伝搬関数 @note 頂点viの遅延評価を伝搬させる。 **/ void Propagate(long long vi) { if (tree[vi].lazy != 0) { tree[vi].value += tree[vi].lazy; if (1 <= tree[vi].r - tree[vi].l) { // 子ノードが存在する tree[2 * vi + 1].lazy += tree[vi].lazy / 2; tree[2 * vi + 2].lazy += tree[vi].lazy / 2; } tree[vi].lazy = 0; } } /** @brief 区間合計値を取得する関数 @note [l,r]の合計値を取得して返す **/ void RangeSum(long long l, long long r, T& sum, long long vi = 0) { if (r < l) { sum = 0; return; } if (vi == 0) { Propagate(vi); sum = tree[vi].value; } if (tree[vi].l == l && tree[vi].r == r) return; vi *= 2; if (tree[vi + 1].r < l) { Propagate(vi + 1); sum -= tree[vi + 1].value; RangeSum(l, r, sum, vi + 2); } else if (r < tree[vi + 2].l) { Propagate(vi + 2); sum -= tree[vi + 2].value; RangeSum(l, r, sum, vi + 1); } else { RangeSum(l, tree[vi + 1].r, sum, vi + 1); RangeSum(tree[vi + 2].l, r, sum, vi + 2); } } }; } using namespace NyaGadget; int main(void) { ll N, Q; cin >> N >> Q; vt<ll> v = InputVT<ll>(N); vt<ll> ans; LazySegmentTree<ll> LST(v); rep(i, 0, Q) { ll q1, q2, q3; cin >> q1 >> q2 >> q3; if (q1 == 0) LST.Add(q2, q2, q3); if (q1 == 1) { ll sum = 0; LST.RangeSum(q2, q3 - 1, sum); ans.push_back(sum); } } each(i, e, ans) cout << val(e) << endl; return 0; }