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

• 問題: No.789 範囲の合計
• ユーザー: InTheBloom
• 提出日時: 2024-04-29 01:59:13
• 言語: D (dmd 2.109.1)
• 結果: AC
• 実行時間: 203 ms / 1,000 ms
• コード長: 5,091 bytes
• コンパイル時間: 6,745 ms
• コンパイル使用メモリ: 212,072 KB
• 実行使用メモリ: 17,868 KB
• 最終ジャッジ日時: 2024-11-18 00:14:49
• 合計ジャッジ時間: 10,039 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
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 () {
    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 ope, alias e) {
    // TODO: assertのメッセージを表示
    static assert(isCallable!(ope));
    static assert(isCallable!(e));
    static assert(is (ReturnType!(ope) == T));
    static assert(is (ReturnType!(e) == T));
    static assert(is (Parameters!(ope) == 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;
                    }
                }
            }

            root = new node(1, N + 1, e(), null, null);
        }

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

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

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

        void dump () {
            void dfs (const node *cur) {
                if (cur == null) {
                    return;
                }
                import std.stdio : writefln;
                writefln("range: [%s %s), value: %s", cur.left, cur.right, cur.value);

                dfs(cur.left_child);
                dfs(cur.right_child);
            }
            dfs(root);
        }

    private:
        struct node {
            long left, right;
            T value;
            node *left_child = null, right_child = null;
        }

        node *root;
        long N = 0;
        long length = 0;

        // [l, r) : 今いる場所の本来あるべき区間
        void internal_set (ref node *cur, long a, long b, T v, long l, long r) {
            // 途中までで切り上げる
            if (cur == null) {
                cur = new node(a, b, v, null, null);
                return;
            }
            if (a == l && b == r) {
                cur.value = v;
                return;
            }

            // 途中で打ち切られたノードを発見
            if (cur.left != l || cur.right != r) {
                T vv = cur.value;
                long ll = cur.left, rr = cur.right;

                // 区間修正 -> 先にあったノードを直す
                cur.left = l;
                cur.right = r;
                internal_set(cur, ll, rr, vv, l, r);
            }

            // 下に潜る
            long mid = (l + r) / 2;
            if (b <= mid) { internal_set(cur.left_child, a, b, v, l, mid); }
            else { internal_set(cur.right_child, a, b, v, mid, r); }

            // 自分の値を更新
            cur.value = ope(
                    (cur.left_child == null ? e() : cur.left_child.value),
                    (cur.right_child == null ? e() : cur.right_child.value));
        }

        T internal_prod (const node *cur, long a, long b) {
            // まだ作られていない = その区間は初期値
            if (cur == null) return e();

            long l = cur.left, r = cur.right;
            if (b <= l || r <= a) return e();

            // 包含
            if (a <= l && r <= b) return cur.value;

            // 部分包含は必要部分を縮めて渡す
            import std.algorithm : min, max;
            a = max(a, l);
            b = min(b, r);

            long mid = (l + r) / 2;
            if (b <= mid) return internal_prod(cur.left_child, a, b);
            if (mid <= a) return internal_prod(cur.right_child, a, b);

            return ope(
                    internal_prod(cur.left_child, a, mid),
                    internal_prod(cur.right_child, mid, b)
                    );
        }
}