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

• 問題: No.772 Dynamic Distance Sum
• ユーザー: yosupot
• 提出日時: 2018-12-19 23:26:32
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,109 ms / 5,000 ms
• コード長: 8,171 bytes
• コンパイル時間: 4,114 ms
• コンパイル使用メモリ: 243,804 KB
• 実行使用メモリ: 81,668 KB
• 最終ジャッジ日時: 2024-09-25 08:16:39
• 合計ジャッジ時間: 23,216 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	8 ms; 6,944 KB
testcase_05	AC	4 ms; 6,944 KB
testcase_06	AC	6 ms; 6,944 KB
testcase_07	AC	3 ms; 6,944 KB
testcase_08	AC	6 ms; 6,944 KB
testcase_09	AC	8 ms; 6,940 KB
testcase_10	AC	9 ms; 6,940 KB
testcase_11	AC	3 ms; 6,944 KB
testcase_12	AC	967 ms; 78,704 KB
testcase_13	AC	920 ms; 77,792 KB
testcase_14	AC	889 ms; 77,680 KB
testcase_15	AC	805 ms; 70,116 KB
testcase_16	AC	1,101 ms; 78,572 KB
testcase_17	AC	945 ms; 78,172 KB
testcase_18	AC	891 ms; 78,860 KB
testcase_19	AC	915 ms; 77,984 KB
testcase_20	AC	771 ms; 78,960 KB
testcase_21	AC	952 ms; 81,140 KB
testcase_22	AC	842 ms; 81,144 KB
testcase_23	AC	910 ms; 81,240 KB
testcase_24	AC	781 ms; 72,416 KB
testcase_25	AC	1,052 ms; 81,220 KB
testcase_26	AC	863 ms; 81,124 KB
testcase_27	AC	1,109 ms; 81,144 KB
testcase_28	AC	863 ms; 81,208 KB
testcase_29	AC	860 ms; 81,668 KB

ソースコード

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

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) {
            assert(!l.pd && !r.pd && !l.dwd && !r.dwd);
            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};
        }
        D rev() { return D{cnt, pd, dwd, upd}; }
        D to_subs() { return D{cnt, 0, upd, 0}; }
    };
    D single = D(), sub = D(), subs = D();

    NP search(ll nw, ll f) {
        //search heavy
        assert(sub.cnt >= nw);
        push();
        if (ch[0][1] && ch[0][1]->sub.cnt >= nw) return ch[0][1]->search(nw, f);
        if (ch[0][1]) nw -= ch[0][1]->sub.cnt;
        if (single.cnt + (lt ? lt->subs.cnt : 0) >= nw) {
            if (!lt || lt->subs.cnt < f) return this;
            auto q = lt->search_light(f);
            if (!q) return this;
            return q;
        }
        nw -= single.cnt;
        if (lt) nw -= lt->subs.cnt;
        assert(ch[0][0]);
        return ch[0][0]->search(nw, f);
    }
    NP search_light(ll f) {
        assert(subs.cnt >= f);
        if (sub.cnt >= f) {
            return search(f, f);
        }
        push();
        if (ch[1][0] && ch[1][0]->subs.cnt >= f) return ch[1][0]->search_light(f);
        if (ch[1][1] && ch[1][1]->subs.cnt >= f) return ch[1][1]->search_light(f);
        expose();
        return nullptr;
    }
    void init_node(ll cnt, ll d) {
        single.cnt = cnt;
        single.pd = d;
        single.upd = single.dwd = cnt * d;
        update();
    }
    void update_subs() {
        subs = sub.to_subs();
        if (ch[1][0]) subs = D::merge_w(ch[1][0]->subs, subs);
        if (ch[1][1]) subs = D::merge_w(subs, ch[1][1]->subs);
    }
    void update() {
        assert(!rev);
        sub = single;
        if (lt) sub = D::join(single, lt->subs);
        if (ch[0][0]) sub = D::merge_h(ch[0][0]->sub, sub);
        if (ch[0][1]) sub = D::merge_h(sub, ch[0][1]->sub);
        update_subs();
    }
    void revdata() {
        rev ^= true; swap(ch[0][0], ch[0][1]); // Important
        sub = sub.rev();
        update_subs();
    }
    void push() {
        if (rev) {
            if (ch[0][0]) ch[0][0]->revdata();
            if (ch[0][1]) ch[0][1]->revdata();
            rev = false;
        }
    }
    //optimize? : template<int ty>
    int pos(int ty) {
        if (p) {
            if (p->ch[ty][0] == this) return 0;
            if (p->ch[ty][1] == this) return 1;
        }
        return -1;
    }
    static void con(NP p, NP& cp, NP ch) { cp = ch; if (ch) ch->p = p; }
    void rot(int ty) {
        int ps = pos(ty);
        NP _p = p, q = p->p;
        if (ty == 0) {
            ch[1] = _p->ch[1]; _p->ch[1].fill(nullptr);
            for (auto& x: ch[1]) if (x) x->p = this;
        }
        con(_p, _p->ch[ty][ps], ch[ty][1-ps]);
        con(this, ch[ty][1-ps], _p);
        _p->update(); update();
        p = q;
        if (!q) return;
        if (q->lt == _p) q->lt = this;
        for (auto& v: q->ch) for (auto& x: v) if (x == _p) x = this;
        q->update();
    }
    void splay(int ty) {
        int ps;
        while ((ps = pos(ty)) != -1) {
            int pps = p->pos(ty);
            if (pps == -1) {
                rot(ty);
            } else if (ps == pps) {
                p->rot(ty); rot(ty);
            } else {
                rot(ty); rot(ty);
            }
        }
    }
    void expose() {
        supush();
        splay(0); splay(1);
        if (NP z = ch[0][1]) {
            z->push();
            con(z, z->ch[1][1], lt);
            lt = z; ch[0][1] = nullptr;
            z->update(); update();
        }
        NP u = p;
        while (u) {
            u->splay(0); u->splay(1);
            NP ur = u->lt;
            if (auto r = u->ch[0][1]) {
                // swap ur, r
                r->push();
                r->ch[1] = ur->ch[1]; ur->ch[1].fill(nullptr);
                for (auto& x: r->ch[1]) if (x) x->p = r;
                r->update();
                u->lt = r;
            } else if (!ur->ch[1][0]) {
                // use ur->ch[1][1]
                con(u, u->lt, ur->ch[1][1]);
            } else {
                // use prev(ur) in light-tree
                NP q = ur->ch[1][0];
                con(u, u->lt, q);
                q->push();
                while (q->ch[1][1]) {
                    q = q->ch[1][1]; q->push();
                }
                q->splay(1);
                con(q, q->ch[1][1], ur->ch[1][1]); q->update();
            }
            ur->ch[1].fill(nullptr); ur->update();
            u->ch[0][1] = ur; u->update();
            u = u->p;
        }
        splay(0);
    }
    void supush() {
        if (p) p->supush();
        push();
    }
    void link(NP r) {
        evert(); r->expose();
        assert(!r->ch[0][1]);
        con(r, r->ch[0][1], this);
        r->update();
    }
    void cut() {
        expose();
        assert(ch[0][0]);
        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];

static inline uint64_t mix(uint64_t h) {
    h ^= h >> 23;
    h *= 0x2127599bf4325c37ULL;
    h ^= h >> 47;
    return h;
}

ull hash_f(ull x) {
    const uint64_t    m = 0x880355f21e6d1965ULL;
    return mix((m ^ mix(x)) * m);
}

struct fasthash {
    ull operator()(ll x) const { return hash_f(x); }
};


template <class K, class D>
using hashmap = gp_hash_table<K, D, fasthash>;

int main() {
//    ios::sync_with_stdio(false); // Warning!!!!!
//    cin.tie(nullptr);
    int n, q;
    assert(scanf("%d %d", &n, &q) == 2);
    assert(1 <= n && n <= 100000);
    assert(1 <= q && q <= 300000);
    for (int i = 0; i < n; i++) {
        vtr[i].init_node(1, 0);
    }
    ll sm = 0;
    hashmap<ll, int> mp;
//    unordered_map<ll, int> mp;
    for (int ph = 0; ph < q; ph++) {
        int ty;
        assert(scanf("%d", &ty) == 1);
        if (ty == 1) {
            int a, b; ll c;
            assert(scanf("%d %d %lld", &a, &b, &c) == 3); a--; b--;
            a = (a + sm) % n;
            b = (b + sm) % n;
            assert(0 <= c && c <= TEN(8));
            if (a > b) swap(a, b);
            mp[(ll(a)<<32)|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;
            assert(scanf("%d %d", &a, &b) == 2); a--; b--;
            a = (a + sm) % n;
            b = (b + sm) % n;
            if (a > b) swap(a, b);
            int c = mp[(ll(a)<<32)|b];
            vtr[a].evert();
            vtr[n + c].cut();
            vtr[b].cut();
        } else if (ty == 3) {
            int a;
            assert(scanf("%d", &a) == 1); a--;
            a = (a + sm) % n;
            vtr[a].evert();
            vtr[a].init_node(1 - vtr[a].single.cnt, 0);
            int z = (vtr[a].sub.cnt + 1) / 2;
            auto p = vtr[a].search(z, z);
            p->evert();
            ll ans = p->sub.upd;
            printf("%lld\n", ans);
            sm = (sm + ans) % n;
        } else {
            assert(false);
        }
    }
    return 0;
}