#937932 (C++17) No.789 範囲の合計

• 問題: No.789 範囲の合計
• ユーザー: Feishi Li
• 提出日時: 2023-12-11 18:40:32
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 75 ms / 1,000 ms
• コード長: 5,893 bytes
• コンパイル時間: 4,582 ms
• コンパイル使用メモリ: 267,504 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2024-09-27 04:35:43
• 合計ジャッジ時間: 6,976 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	72 ms; 6,016 KB
testcase_03	AC	46 ms; 5,376 KB
testcase_04	AC	75 ms; 6,272 KB
testcase_05	AC	55 ms; 5,760 KB
testcase_06	AC	57 ms; 5,888 KB
testcase_07	AC	34 ms; 5,376 KB
testcase_08	AC	53 ms; 6,528 KB
testcase_09	AC	48 ms; 6,016 KB
testcase_10	AC	72 ms; 5,376 KB
testcase_11	AC	45 ms; 6,144 KB
testcase_12	AC	45 ms; 6,016 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB

ソースコード

#include <bits/stdc++.h>
#include <bits/extc++.h>
using i64 = long long;
template <typename S, S (*op)(S, S), S (*e)()>
class dynamic_segtree
{
public:
    dynamic_segtree(size_t n) : n(n), root(nullptr) {}
    void set(size_t p, S x)
    {
        assert(p < n);
        set(root, 0, n, p, x);
    }
    S get(size_t p) const
    {
        assert(p < n);
        return get(root, 0, n, p);
    }
    S prod(size_t l, size_t r) const
    {
        assert(l <= r && r <= n);
        return prod(root, 0, n, l, r);
    }
    S all_prod() const
    {
        return root ? root->product : e();
    }

    void reset(size_t l, size_t r)
    {
        assert(l <= r && r <= n);
        return reset(root, 0, n, l, r);
    }
    template <bool (*f)(S)>
    size_t max_right(size_t l) const
    {
        return max_right(l, [](S x)
                         { return f(x); });
    }
    template <typename F>
    size_t max_right(size_t l, const F &f) const
    {
        assert(l <= n);
        S product = e();
        assert(f(product));
        return max_right(root, 0, n, l, f, product);
    }
    template <bool (*f)(S)>
    size_t min_left(size_t r) const
    {
        return min_left(r, [](S x)
                        { return f(x); });
    }
    template <typename F>
    size_t min_left(size_t r, const F &f) const
    {
        assert(r <= n);
        S product = e();
        assert(f(product));
        return min_left(root, 0, n, r, f, product);
    }

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

    struct node
    {
        size_t idx;
        S value, product;
        node_ptr left, right;

        node(size_t idx, S value)
            : idx(idx),
              value(value),
              product(value),
              left(nullptr),
              right(nullptr) {}

        void update()
        {
            product = op(op(left ? left->product : e(), value),
                         right ? right->product : e());
        }
    };
    const size_t n;
    node_ptr root;
    void set(node_ptr &t, size_t lx, size_t rx, size_t p, S x) const
    {
        if (!t)
        {
            t = std::make_unique<node>(p, x);
            return;
        }
        if (t->idx == p)
        {
            t->value = x;
            t->update();
            return;
        }
        size_t m = (lx + rx) >> 1;
        if (p < m)
        {
            if (t->idx < p)
            {
                std::swap(t->idx, p);
                std::swap(t->value, x);
            }
            set(t->left, lx, m, p, x);
        }
        else
        {
            if (p < t->idx)
            {
                std::swap(p, t->idx);
                std::swap(x, t->value);
            }
            set(t->right, m, rx, p, x);
        }
        t->update();
    }

    S get(const node_ptr &t, size_t lx, size_t rx, size_t p) const
    {
        if (!t)
            return e();
        if (t->idx == p)
            return t->value;
        size_t m = (lx + rx) >> 1;
        if (p < m)
            return get(t->left, lx, m, p);
        else
            return get(t->right, m, rx, p);
    }

    S prod(const node_ptr &t, size_t lx, size_t rx, size_t l, size_t r) const
    {
        if (!t || rx <= l || lx >= r)
            return e();
        if (l <= lx && rx <= r)
            return t->product;
        size_t m = (lx + rx) >> 1;
        S res = prod(t->left, lx, m, l, r);
        if (l <= t->idx && t->idx < r)
        {
            res = op(res, t->value);
        }
        return op(res, prod(t->right, m, rx, l, r));
    }

    void reset(node_ptr &t, size_t lx, size_t rx, size_t l, size_t r) const
    {
        if (!t || rx <= l || r <= lx)
            return;
        if (l <= lx && rx <= r)
        {
            t.reset();
            return;
        }
        size_t m = (lx + rx) >> 1;
        reset(t->left, lx, m, l, r);
        reset(t->right, m, rx, l, r);
        t->update();
    }

    template <typename F>
    size_t max_right(const node_ptr &t, size_t lx, size_t rx, size_t l, size_t r, const F &f, S &product) const
    {
        if (!t || rx <= l)
            return n;
        if (f(op(product, t->product)))
        {
            product = op(product, t->product);
            return n;
        }
        size_t m = (lx + rx) >> 1;
        size_t res = max_right(t->left, lx, m, l, f, product);
        if (res != n)
            return res;
        if (l <= t->idx)
        {
            product = op(product, t->value);
            if (!f(product))
                return t->idx;
        }
        return max_right(t->right, m, rx, l, f, product);
    }

    template <typename F>
    size_t min_left(const node_ptr &t, size_t lx, size_t rx, size_t r, const F &f, S &product) const
    {
        if (!t || r <= lx)
            return 0;
        if (f(op(t->product, product)))
        {
            product = op(t->product, product);
            return 0;
        }
        size_t m = (lx + rx) >> 1;
        size_t res = min_left(t->right, m, rx, r, f, product);
        if (res != 0)
            return res;
        if (t->idx < r)
        {
            product = op(t->value, product);
            if (!f(product))
                return t->idx + 1;
        }
        return min_left(t->left, lx, m, r, f, product);
    }
};
using S = i64;
S op(S l, S r)
{
    return l + r;
}
S e()
{
    return 0;
}
void solve()
{
    int q;
    std::cin >> q;
    dynamic_segtree<S, op, e> seg(1e9 + 1);
    i64 ans = 0;
    while (q--)
    {
        int o, x, y, l, r;
        std::cin >> o;
        if (o == 0)
        {
            std::cin >> x >> y;
            seg.set(x, seg.get(x) + y);
        }
        else
        {
            std::cin >> l >> r;
            ans += seg.prod(l, r + 1);
        }
    }
    std::cout << ans << '\n';
}
int main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    solve();
    return 0;
}