結果

問題 No.3298 K-th Slime
ユーザー InTheBloom
提出日時 2025-10-05 13:59:51
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 262 ms / 2,000 ms
コード長 9,848 bytes
コンパイル時間 2,298 ms
コンパイル使用メモリ 204,532 KB
実行使用メモリ 25,912 KB
最終ジャッジ日時 2025-10-05 14:00:06
合計ジャッジ時間 5,682 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    int N, K, Q;
    readln.read(N, K, Q);
    auto A = readln.split.to!(int[]);
    auto ans = new long[](0);

    alias Tr = AVLTree!(long, true);
    auto tree = new Tr();
    foreach (i; 0 .. N) {
        tree.insert(A[i]);
    }

    foreach (i; 0 .. Q) {
        auto query = readln.split.to!(int[]);
        int t = query[0];

        if (t == 1) {
            int x = query[1];
            tree.insert(x);
        }
        if (t == 2) {
            int y = query[1];
            auto sp = tree.splitByLength(K);
            long key = sp[0].back().value;
            tree = Tr.merge(sp[0], sp[1]);
            tree.remove(key);
            tree.insert(key + y);
        }
        if (t == 3) {
            auto sp = tree.splitByLength(K);
            ans ~= sp[0].back().value;
            tree = Tr.merge(sp[0], sp[1]);
        }
    }

    writefln("%(%s\n%)", ans);
}

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));
    }
}

class AVLTree (T, bool allowDuplicate = false) {
    alias TreeType = AVLTree!(T, allowDuplicate);
    alias NodeType = TreeType.AVLNode;
    struct AVLNode {
        T value;
        T acc;
        int h;
        int length;
        AVLNode*[2] ch;
    }
    struct AVLSearchResult {
        bool found;
        T value;
    }

    this () {
        root = null;
    }
    this (NodeType* node) {
        root = node;
    }

    AVLNode* root;
    static AVLNode* rotL (AVLNode* cur) {
        assert(cur !is null && cur.ch[1] !is null);
        auto rch = cur.ch[1];
        cur.ch[1] = rch.ch[0];
        rch.ch[0] = cur;
        fix(cur);
        fix(rch);
        return rch;
    }
    static AVLNode* rotR (AVLNode* cur) {
        assert(cur !is null && cur.ch[0] !is null);
        auto lch = cur.ch[0];
        cur.ch[0] = lch.ch[1];
        lch.ch[1] = cur;
        fix(cur);
        fix(lch);
        return lch;
    }
    // [AVLsubtree, 外されたノード]
    static AVLNode*[2] removeLeftMost (AVLNode* cur) {
        assert(cur !is null);
        if (cur.ch[0] is null) {
            return [cur.ch[1], cur];
        }
        auto ret = removeLeftMost(cur.ch[0]);
        cur.ch[0] = ret[0];
        return [balance(cur), ret[1]];
    }
    static void fix (AVLNode* cur) {
        import std.algorithm: max;
        assert(cur !is null);
        int lh = 0;
        int rh = 0;
        T la = T.init;
        T ra = T.init;
        int ll = 0;
        int rl = 0;

        if (cur.ch[0] !is null) {
            lh = cur.ch[0].h;
            la = cur.ch[0].acc;
            ll = cur.ch[0].length;
        }
        if (cur.ch[1] !is null) {
            rh = cur.ch[1].h;
            ra = cur.ch[1].acc;
            rl = cur.ch[1].length;
        }
        cur.h = max(lh, rh) + 1;
        cur.acc = la + cur.value + ra;
        cur.length = ll + 1 + rl;
    }
    static int diff (AVLNode* cur) {
        assert(cur !is null);
        int lh = cur.ch[0] is null ? 0 : cur.ch[0].h;
        int rh = cur.ch[1] is null ? 0 : cur.ch[1].h;
        return lh - rh;
    }

    static AVLNode* balance (AVLNode* cur) {
        import std.math: abs;
        assert(cur !is null);
        fix(cur);
        int s = diff(cur);
        assert(abs(s) <= 2);
        if (abs(s) <= 1) {
            return cur;
        }
        if (s == 2) {
            if (diff(cur.ch[0]) == -1) {
                cur.ch[0] = rotL(cur.ch[0]);
            }
            return rotR(cur);
        }
        if (diff(cur.ch[1]) == 1) {
            cur.ch[1] = rotR(cur.ch[1]);
        }
        return rotL(cur);
    }

    static NodeType* mergeWithRoot (NodeType* lt, NodeType* r, NodeType* rt) {
        assert(r !is null);
        int ls = lt is null ? 0 : lt.h;
        int rs = rt is null ? 0 : rt.h;

        if (abs(ls - rs) <= 1) {
            r.ch[0] = lt;
            r.ch[1] = rt;
            return balance(r);
        }
        if (ls < rs) {
            rt.ch[0] = mergeWithRoot(lt, r, rt.ch[0]);
            return balance(rt);
        }
        lt.ch[1] = mergeWithRoot(lt.ch[1], r, rt);
        return balance(lt);
    }

    static TreeType merge (TreeType lt, TreeType rt) {
        if (lt.empty()) {
            return rt;
        }
        if (rt.empty()) {
            return lt;
        }
        static if (allowDuplicate) {
            enforce(lt.back().value <= rt.front().value);
        }
        else {
            enforce(lt.back().value < rt.front().value);
        }

        auto rtt = removeLeftMost(rt.root);
        return new TreeType(mergeWithRoot(lt.root, rtt[1], rtt[0]));
    }

    static NodeType*[2] internalSplitByValue (NodeType* node, T key) {
        if (node is null) {
            return [null, null];
        }
        if (node.value < key) {
            auto sp = internalSplitByValue(node.ch[1], key);
            auto lo = mergeWithRoot(node.ch[0], node, sp[0]);
            return [lo, sp[1]];
        }
        auto sp = internalSplitByValue(node.ch[0], key);
        auto hi = mergeWithRoot(sp[1], node, node.ch[1]);
        return [sp[0], hi];
    }
    TreeType[2] splitByValue (T key) {
        auto sp = internalSplitByValue(root, key);
        return [new TreeType(sp[0]), new TreeType(sp[1])];
    }
    static NodeType*[2] internalSplitByLength (NodeType* node, size_t len) {
        if (node is null) {
            return [null, null];
        }
        int ll = (node.ch[0] is null ? 0 : node.ch[0].length);
        if (ll + 1 <= len) {
            auto sp = internalSplitByLength(node.ch[1], len - ll - 1);
            auto lo = mergeWithRoot(node.ch[0], node, sp[0]);
            return [lo, sp[1]];
        }
        auto sp = internalSplitByLength(node.ch[0], len);
        auto hi = mergeWithRoot(sp[1], node, node.ch[1]);
        return [sp[0], hi];
    }
    TreeType[2] splitByLength (size_t len) {
        auto sp = internalSplitByLength(root, len);
        return [new TreeType(sp[0]), new TreeType(sp[1])];
    }

    bool empty () {
        return root is null;
    }
    AVLSearchResult front () {
        auto cur = root;
        if (cur is null) {
            return AVLSearchResult(false);
        }
        while (cur.ch[0] !is null) {
            cur = cur.ch[0];
        }
        return AVLSearchResult(true, cur.value);
    }
    AVLSearchResult back () {
        auto cur = root;
        if (cur is null) {
            return AVLSearchResult(false);
        }
        while (cur.ch[1] !is null) {
            cur = cur.ch[1];
        }
        return AVLSearchResult(true, cur.value);
    }

    bool find (T k) {
        auto cur = root;
        while (cur !is null) {
            if (cur.value == k) {
                return true;
            }
            cur = k < cur.value ? cur.ch[0] : cur.ch[1];
        }
        return false;
    }

    bool insert (T k) {
        bool ret = true;
        AVLNode* f (AVLNode* cur) {
            if (cur is null) {
                return new AVLNode(k, k, 1, 1);
            }
            static if (!allowDuplicate) {
                if (cur.value == k) {
                    ret = false;
                    return cur;
                }
            }
            int d = k < cur.value ? 0 : 1;
            cur.ch[d] = f(cur.ch[d]);
            return balance(cur);
        }
        root = f(root);
        return ret;
    }

    bool remove (T k) {
        bool del = true;
        AVLNode* f (AVLNode* cur) {
            if (cur is null) {
                del = false;
                return cur;
            }
            if (cur.value == k) {
                if (cur.ch[1] is null) {
                    return cur.ch[0];
                }
                auto ret = removeLeftMost(cur.ch[1]);
                ret[1].ch[0] = cur.ch[0];
                ret[1].ch[1] = ret[0];
                return balance(ret[1]);
            }
            int d = k < cur.value ? 0 : 1;
            cur.ch[d] = f(cur.ch[d]);
            return balance(cur);
        }
        root = f(root);
        return del;
    }

    AVLSearchResult predecessor (T k) {
        import std.algorithm: max;
        AVLSearchResult f (AVLNode* cur) {
            if (cur is null) {
                return AVLSearchResult(false);
            }
            if (cur.value == k) {
                return AVLSearchResult(true, cur.value);
            }
            if (cur.value < k) {
                auto nex = f(cur.ch[1]);
                if (!nex.found) {
                    return AVLSearchResult(true, cur.value);
                }
                nex.value = max(nex.value, cur.value);
                return nex;
            }
            return f(cur.ch[0]);
        }
        return f(root);
    }

    AVLSearchResult successor (T k) {
        import std.algorithm: min;
        AVLSearchResult f (AVLNode* cur) {
            if (cur is null) {
                return AVLSearchResult(false);
            }
            if (cur.value == k) {
                return AVLSearchResult(true, cur.value);
            }
            if (k < cur.value) {
                auto nex = f(cur.ch[0]);
                if (!nex.found) {
                    return AVLSearchResult(true, cur.value);
                }
                nex.value = min(nex.value, cur.value);
                return nex;
            }
            return f(cur.ch[1]);
        }
        return f(root);
    }

    override string toString () {
        import std.format;
        auto values = new T[](0);
        void f (AVLNode* cur) {
            if (cur is null) {
                return;
            }
            f(cur.ch[0]);
            values ~= cur.value;
            f(cur.ch[1]);
        }
        f(root);
        return format("[%(%s, %)]", values);
    }
}
0