#978105 (D) No.789 範囲の合計

• 問題: No.789 範囲の合計
• ユーザー: InTheBloom
• 提出日時: 2024-04-30 03:31:06
• 言語: D (dmd 2.109.1)
• 結果: AC
• 実行時間: 165 ms / 1,000 ms
• コード長: 6,058 bytes
• コンパイル時間: 4,461 ms
• コンパイル使用メモリ: 227,712 KB
• 実行使用メモリ: 15,132 KB
• 最終ジャッジ日時: 2024-11-19 15:37:15
• 合計ジャッジ時間: 6,879 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

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

ソースコード

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

void main () {
    // yosupojudge_Point_Add_Range_Sum();
    yukicoder_789();
}

void yosupojudge_Point_Add_Range_Sum () {
    import std;

    // yosupo judge: Point Add Range Sum (https://judge.yosupo.jp/problem/point_add_range_sum)

    long len = 10^^9;
    auto seg = new DynamicSegmentTree!(long, (long a, long b) => a + b, () => 0L)(len);
    int N, Q; readln.read(N, Q);
    auto a = readln.split.to!(int[]);
    foreach (i; 0..N) seg.set(i, a[i]);

    // seg.dump();
    // writeln();

    foreach (i; 0..Q) {
        int t, l, r; readln.read(t, l, r);
        if (t == 0) {
            seg.set(l, seg.get(l) + r);
            // seg.dump();
            // writeln();
        }
        if (t == 1) {
            writeln(seg.prod(l, r));
        }
    }
}

void yukicoder_789 () {
    import std;

    // yukicoder No.789 範囲の合計

    long len = 10^^9;
    auto seg = new DynamicSegmentTree!(long, (long a, long b) => a + b, () => 0L)(len);
    int N = readln.chomp.to!int;

    // seg.dump();
    // writeln();

    long ans = 0;
    foreach (i; 0..N) {
        int t, l, r; readln.read(t, l, r);
        if (t == 0) {
            seg.set(l, seg.get(l) + r);
        }
        if (t == 1) {
            ans += seg.prod(l, r + 1);
        }
    }

    writeln(ans);
}

import std.traits : ReturnType, isCallable, Parameters;
import std.meta : AliasSeq;

class DynamicSegmentTree (T, alias op, alias e) {
    // TODO: assertのメッセージを表示
    static assert(isCallable!(op));
    static assert(isCallable!(e));
    static assert(is (ReturnType!(op) == T));
    static assert(is (ReturnType!(e) == T));
    static assert(is (Parameters!(op) == AliasSeq!(T, T)));
    static assert(is (Parameters!(e) == AliasSeq!()));

    // 内部が1-indexedで動的な完全二分セグメント木
    import std.format : format;
    public:
        this (long N_)
        in {
            assert(1 <= N_, format("Dynamic SegmentTree: N = %s does not satisfy constraints. N must be in range of [1, %s]", 4 * 10L^^18));
        }
        do {
            length = N_;

            // N_以上の2冪に設定
            if ((N_ & (-N_)) == N_) {
                N = N_;
            }
            else {
                // msb+1 bitを立てる
                foreach_reverse (i; 0..63) {
                    if (0 < (N_ & (1L << i))) {
                        N = 1L << (i + 1);
                        break;
                    }
                }
            }
        }

        void set (long idx, T val) {
            idx++;
            internal_set(root, idx, val, 1, N + 1);
        }

        T get (long idx) {
            idx++;
            return internal_get(root, idx, 1, N + 1);
        }

        T prod (long l, long r) {
            l++, r++;
            return internal_prod(root, l, r, 1, N + 1);
        }

        void dump () {
            dfs(root);
        }

    private:
        struct node {
            long index;
            T value, product;
            int left = -1, right = -1;
        }

        void node_update (int cur) {
            auto n = pool[cur];
            n.product = op(
                    op((n.left == -1 ? e() : pool[n.left].product), n.value),
                    (n.right == -1 ? e() : pool[n.right].product)
                    );
        }

        import std.container : Array;

        auto pool = Array!(node *)();
        int root = -1;

        long N = 0;
        long length = 0;

        void dfs (const int cur) {
            if (cur == -1) return;
            import std.stdio;
            writeln("index: ", pool[cur].index - 1, " value: ", pool[cur].value, " product: ", pool[cur].product);

            dfs(pool[cur].left);
            dfs(pool[cur].right);
        }

        // [l, r) : 今見ている部分木が管理する範囲
        int internal_set (int cur, long idx, T val, long l, long r) {
            if (cur == -1) {
                pool ~= new node(idx, val, val, -1, -1);
                if (root == -1) return root = 0;
                return cast(int) pool.length - 1;
            }

            if (pool[cur].index == idx) {
                pool[cur].value = val;
                node_update(cur);
                return cur;
            }

            // 既に部分木管理ノードが存在するときの処理
            import std.algorithm : swap;

            long mid = (l + r) / 2;
            if (idx < mid) {
                // 今いる人を押しのける
                if (pool[cur].index < idx) { swap(pool[cur].value, val); swap(pool[cur].index, idx); }
                pool[cur].left = internal_set(pool[cur].left, idx, val, l, mid);
            }
            else {
                if (idx < pool[cur].index) { swap(pool[cur].value, val); swap(pool[cur].index, idx); }
                pool[cur].right = internal_set(pool[cur].right, idx, val, mid, r);
            }

            node_update(cur);
            return cur;
        }

        T internal_get (const int cur, long idx, long l, long r) {
            if (cur == -1) return e();
            if (pool[cur].index == idx) return pool[cur].value;

            long mid = (l + r) / 2;
            if (idx < mid) return internal_get(pool[cur].left, idx, l, mid);
            return internal_get(pool[cur].right, idx, mid, r);
        }

        // [a, b) = 要求区間
        T internal_prod (const int cur, long a, long b, long l, long r) {
            if (cur == -1 || b <= l || r <= a) return e();
            if (a <= l && r <= b) return pool[cur].product;

            long mid = (l + r) / 2;
            T res = internal_prod(pool[cur].left, a, b, l, mid);
            if (a <= pool[cur].index && pool[cur].index < b) res = op(res, pool[cur].value);
            res = op(res, internal_prod(pool[cur].right, a, b, mid, r));
            return res;
        }
}