#303938 (C++17) No.772 Dynamic Distance Sum

• 問題: No.772 Dynamic Distance Sum
• ユーザー: yosupot
• 提出日時: 2018-12-14 19:53:47
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 8,787 bytes
• コンパイル時間: 2,672 ms
• コンパイル使用メモリ: 219,232 KB
• 実行使用メモリ: 814,592 KB
• 最終ジャッジ日時: 2024-09-25 08:12:21
• 合計ジャッジ時間: 5,626 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	MLE	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-

ソースコード

#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

struct TTNode {
    using NP = TTNode*;

    bool rev = false;
    array<array<NP, 2>, 2> ch = {}; //tree, light-tree
    NP p = nullptr, lt = nullptr;

    struct D {
        ll cnt = 0, pd = 0, upd = 0, dwd = 0;
        // l is parent of r
        static D merge_h(const D& l, const D& r) {
            return {l.cnt + r.cnt, l.pd + r.pd, l.upd + r.upd + l.pd * r.cnt, l.dwd + r.dwd + r.pd * l.cnt};
        }
        // l and r is parallel
        static D merge_w(const D& l, const D& r) {
            // TODO: tukai nikui...
            return {l.cnt + r.cnt, 0, l.upd + r.upd, 0};
        }
        // add parent for r(subtrees)
        static D join(const D& l, const D& r) {
            assert(l.upd == l.dwd);
            return {l.cnt + r.cnt, l.pd, l.upd + r.upd + l.pd * r.cnt, l.dwd + r.upd + l.pd * r.cnt};
        }
        static D rev(const D& l) {
            return D{l.cnt, l.pd, l.dwd, l.upd};
        }
    };
    D single = D(), subtree = D(), subtrees = D();

    NP search(ll nw, ll f) {
        //search heavy
        assert(subtree.cnt >= nw);
        push();
        if (ch[0][1] && ch[0][1]->subtree.cnt >= nw) return ch[0][1]->search(nw, f);
        if (ch[0][1]) nw -= ch[0][1]->subtree.cnt;
        if (single.cnt + (lt ? lt->subtrees.cnt : 0) >= nw) {
            if (!lt || lt->subtrees.cnt < f) return this;
            auto q = lt->search_light(f);
            if (!q) return this;
            return q;
        }
        nw -= single.cnt;
        if (lt) nw -= lt->subtrees.cnt;
        assert(ch[0][0]);
        return ch[0][0]->search(nw, f);
    }
    NP search_light(ll f) {
        assert(subtrees.cnt >= f);
        if (subtree.cnt >= f) {
            return search(f, f);
        }
        push();
        if (ch[1][0] && ch[1][0]->subtrees.cnt >= f) return ch[1][0]->search_light(f);
        if (ch[1][1] && ch[1][1]->subtrees.cnt >= f) return ch[1][1]->search_light(f);
        expose();
        return nullptr;
    }
    void init_node(ll cnt, ll d) {
        //node init
        single.cnt = cnt;
        single.pd = d;
        single.upd = single.dwd = cnt * d;
        update();
    }
    void update() {
        assert(!rev);
        subtree = single;
        if (lt) subtree = D::join(single, lt->subtrees);
        if (ch[0][0]) subtree = D::merge_h(ch[0][0]->subtree, subtree);
        if (ch[0][1]) subtree = D::merge_h(subtree, ch[0][1]->subtree);
        subtrees = subtree;
        if (ch[1][0]) subtrees = D::merge_w(ch[1][0]->subtrees, subtrees);
        if (ch[1][1]) subtrees = D::merge_w(subtrees, ch[1][1]->subtrees);
    }
    void revdata() {
        rev ^= true; swap(ch[0][0], ch[0][1]); // Important
        subtree = D::rev(subtree);
        subtrees = subtree;
        if (ch[1][0]) subtrees = D::merge_w(ch[1][0]->subtrees, subtrees);
        if (ch[1][1]) subtrees = D::merge_w(subtrees, ch[1][1]->subtrees);
    }
    void push() {
        if (rev) {
            if (ch[0][0]) ch[0][0]->revdata();
            if (ch[0][1]) ch[0][1]->revdata();
            rev = false;
        }
    }

    int pos(int ty) {
        if (p) {
            if (p->ch[ty][0] == this) return 0;
            if (p->ch[ty][1] == this) return 1;
        }
        return -1;
    }
    void rot(int ty) {
        assert(!rev);
        assert(!p->rev);
        NP q = p->p;
        int pps = p->pos(ty);
        if (p->ch[ty][0] == this) {
            p->ch[ty][0] = ch[ty][1];
            if (ch[ty][1]) ch[ty][1]->p = p;
            ch[ty][1] = p;
        } else if (p->ch[ty][1] == this) {
            p->ch[ty][1] = ch[ty][0];
            if (ch[ty][0]) ch[ty][0]->p = p;
            ch[ty][0] = p;
        } else {
            assert(false);
        }
        p->p = this;
        if (ty == 0) swap(ch[1], p->ch[1]);
        p->update(); update();
        if (pps != -1) {
            q->ch[ty][pps] = this;
            q->update();
        } else if (q) {
            if (q->lt == p) q->lt = this;
            else if (q->ch[0][0] == p) q->ch[0][0] = this;
            else if (q->ch[0][1] == p) q->ch[0][1] = this;
            else if (q->ch[1][0] == p) q->ch[1][0] = this;
            else if (q->ch[1][1] == p) q->ch[1][1] = this;
            else assert(false);
            q->update();
        }
        p = q;
    }
    void splay(int ty) {
        int ps;
        while ((ps = pos(ty)) != -1) {
            int pps = p->pos(ty);
            if (pps == -1) {
//                if (p->p && p->p->lt == p) p->p->lt = this;
//                if (p->pos(1) != -1) p->p->ch[1][p->pos(1)] = this;
                rot(ty);
            } else if (ps == pps) {
                p->rot(ty); rot(ty);
            } else {
                rot(ty); // TODO : broken!(p->p->lt etc can't renew)
                rot(ty);
            }
        }
    }
    void expose() {
        supush();
        splay(0);
        splay(1);
        assert(!p || p->lt == this);
        if (NP z = ch[0][1]) {
            z->push(); // TODO: really need?
            assert(!z->ch[1][1]);
            z->ch[1][1] = lt;
            if (lt) lt->p = z;
            z->update();
            lt = z; ch[0][1] = nullptr;
            update();
        }
        NP u = p;
        assert(!u || u->lt == this);
        while (u) {
            u->splay(0); u->splay(1);
            // swap ur, lt?
            NP ur = u->lt, r = u->ch[0][1];
            assert(ur);
            if (r) {
                //swap u->ch[0][1], u->lt
                r->push();
                assert(!r->ch[1][0] && !r->ch[1][1]);
                r->ch[1] = ur->ch[1];
                if (r->ch[1][0]) r->ch[1][0]->p = r;
                if (r->ch[1][1]) r->ch[1][1]->p = r;
                r->update();
                u->lt = r;
            } else if (!ur->ch[1][0]) {
                NP urr = ur->ch[1][1];
                u->lt = urr; if (urr) urr->p = u;
            } else {
                //erase u->lt->rightmost
                //TODO: need push
                NP urr = ur->ch[1][0]; u->lt = urr; urr->p = u; urr->push();
                assert(urr);
                while (urr->ch[1][1]) {
                    urr = urr->ch[1][1];
                    urr->push();
                }
                urr->splay(1);
                assert(!urr->ch[1][1]);
                urr->ch[1][1] = ur->ch[1][1];
                if (ur->ch[1][1]) ur->ch[1][1]->p = urr;
                urr->update();
                assert(u->lt == urr && urr->p == u);
            }
            ur->ch[1].fill(nullptr); ur->update();
            assert(ur->p == u);
            u->ch[0][1] = ur; u->update();
            assert(!u->p || u->p->lt == u);
            u = u->p;
        }
        splay(0);
        assert(!ch[0][1]);
    }
    void supush() {
        if (p) p->supush();
        push();
    }
    void link(NP r) {
        evert(); r->expose();
        assert(!r->ch[0][1]);
        p = r; r->ch[0][1] = this;
        r->update();
    }
    void cut() {
        expose();
        ch[0][0]->p = nullptr;
        ch[0][0] = nullptr;
        update();
    }
    void evert() {
        expose();
        revdata();
        expose();
    }
};

const int MN = 100500;
const int MQ = 300500;
TTNode vtr[MN + MQ];

int main() {
    ios::sync_with_stdio(false); // Warning!!!!!
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        vtr[i].init_node(1, 0);
    }
    using P = pair<int, int>;
    map<P, int> mp;
    for (int ph = 0; ph < q; ph++) {
        int ty;
        cin >> ty;
        if (ty == 1) {
            int a, b; ll c;
            cin >> a >> b >> c; a--; b--;
            if (a > b) swap(a, b);
            mp[P(a, b)] = ph;
            vtr[n + ph].init_node(0, c);
            vtr[a].evert();
            vtr[a].link(vtr + n + ph);
            vtr[n + ph].link(vtr + b);
        } else if (ty == 2) {
            int a, b;
            cin >> a >> b; a--; b--;
            if (a > b) swap(a, b);
            int c = mp[P(a, b)];
            vtr[a].evert();
            vtr[n + c].cut();
            vtr[b].cut();
        } else if (ty == 3) {
            int a;
            cin >> a; a--;
            vtr[a].evert();
            vtr[a].init_node(1 - vtr[a].single.cnt, 0);
            int z = (vtr[a].subtree.cnt + 1) / 2;
            auto p = vtr[a].search(z, z);
            p->evert();
            cout << p->subtree.upd << "\n";
//            cout << p - vtr << " " << p->subtree.upd << "\n";
        } else {
            assert(false);
        }
    }
    return 0;
}