#394455 (C++17) No.399 動的な領主

提出ソース

結果

問題	No.399 動的な領主
ユーザー	xuzijian629
提出日時	2019-10-28 15:02:14
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	993 ms / 2,000 ms
コード長	11,259 bytes
コンパイル時間	3,004 ms
コンパイル使用メモリ	219,812 KB
実行使用メモリ	10,220 KB
最終ジャッジ日時	2024-09-14 21:13:21
合計ジャッジ時間	13,082 ms
ジャッジサーバーID （参考情報）	judge1 / judge6

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	7 ms 5,376 KB
testcase_05	AC	64 ms 5,376 KB
testcase_06	AC	993 ms 10,216 KB
testcase_07	AC	967 ms 10,216 KB
testcase_08	AC	930 ms 10,220 KB
testcase_09	AC	925 ms 10,216 KB
testcase_10	AC	7 ms 5,376 KB
testcase_11	AC	40 ms 5,376 KB
testcase_12	AC	542 ms 10,092 KB
testcase_13	AC	499 ms 10,216 KB
testcase_14	AC	543 ms 10,220 KB
testcase_15	AC	799 ms 10,088 KB
testcase_16	AC	798 ms 10,088 KB
testcase_17	AC	895 ms 10,220 KB
testcase_18	AC	919 ms 10,216 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

// T0: 元の配列のモノイド
// T1: T0に対する作用素モノイド
template <class T0, class T1>
class BaseLinkCutTree {
    // T0上の演算、単位元
    virtual T0 f0(T0, T0) = 0;
    const T0 u0;
    // T1上の演算、単位元
    virtual T1 f1(T1, T1) = 0;
    const T1 u1;
    // T0に対するT1の作用
    virtual T0 g(T0, T1) = 0;
    // 多数のt1(T1)に対するf1の合成
    virtual T1 p(T1, int) = 0;

    struct Node {
        int idx, cnt;
        T0 val, acc;
        T1 lazy;
        Node *left, *right, *par;
        Node(int idx, T0 val, T0 u0, T1 u1)
            : idx(idx), cnt(1), val(val), lazy(u1), acc(u0), left(nullptr), right(nullptr), par(nullptr) {}
        bool is_root() { return (!par) || (par->left != this && par->right != this); }
    };

    void push(Node* t) {
        if (t->cnt < 0) {
            swap(t->left, t->right);
            if (t->left) t->left->cnt = -(t->left->cnt);
            if (t->right) t->right->cnt = -(t->right->cnt);
            t->cnt = -t->cnt;
        }
        if (t->lazy != u1) {
            t->val = g(t->val, p(t->lazy, 1));
            t->acc = g(t->acc, p(t->lazy, t->cnt));
            if (t->left) t->left->lazy = g(t->left->lazy, p(t->lazy, 1));
            if (t->right) t->right->lazy = g(t->right->lazy, p(t->lazy, 1));
            t->lazy = u1;
        }
    }

    void eval(Node* t) {
        bool flag = (t->cnt < 0);
        t->cnt = 1, t->acc = t->val;
        if (t->left) push(t->left), t->cnt += _abs(t->left->cnt), t->acc = f1(t->left->acc, t->acc);
        if (t->right) push(t->right), t->cnt += _abs(t->right->cnt), t->acc = f1(t->acc, t->right->acc);
        if (flag) t->cnt = -t->cnt;
    }

    vector<Node*> nodes;

    inline static int _abs(int val) { return val & 0x7fffffff; }
    // 回転
    void rotate(Node* u, bool right) {
        Node *p = u->par, *g = p->par;
        if (right) {
            if ((p->left = u->right)) u->right->par = p;
            u->right = p, p->par = u;
        } else {
            if ((p->right = u->left)) u->left->par = p;
            u->left = p, p->par = u;
        }
        eval(p), eval(u), u->par = g;
        if (!g) return;
        if (g->left == p) g->left = u;
        if (g->right == p) g->right = u;
        eval(g);
    }
    // uをsplay木の根にする
    void splay(Node* u) {
        while (!(u->is_root())) {
            Node *p = u->par, *gp = p->par;
            if (p->is_root()) {  // zig
                push(p), push(u);
                rotate(u, (u == p->left));
            } else {
                push(gp), push(p), push(u);
                bool flag = (u == p->left);
                if ((u == p->left) == (p == gp->left)) {  // zig-zig
                    rotate(p, flag), rotate(u, flag);
                } else {  // zig-zag
                    rotate(u, flag), rotate(u, !flag);
                }
            }
        }
        push(u);
    }
    Node* expose(Node* u) {
        Node* last = nullptr;
        for (Node* v = u; v; v = v->par) {
            splay(v);
            v->right = last;
            eval(v);
            last = v;
        }
        splay(u);
        return last;
    }
    bool connected(Node* u, Node* v) {
        expose(u), expose(v);
        return u->par;
    }
    // u(child)とv(parent)を結ぶ
    void link(Node* u, Node* v) {
        assert(!connected(u, v));
        evert(u), u->par = v;
    }
    // uと親を切り離す
    void cut(Node* u) {
        expose(u);
        assert(u->left);
        u->left->par = nullptr, u->left = nullptr, eval(u);
    }
    Node* lca(Node* u, Node* v) {
        // assert(connected(u, v));
        expose(u);
        return expose(v);
    }
    Node* get_kth(Node* v, int k) {
        expose(v);
        while (v) {
            eval(v);
            if (v->right && v->right->cnt > k) {
                v = v->right;
            } else {
                if (v->right) k -= v->right->cnt;
                if (k == 0) return v;
                k--;
                v = v->left;
            }
        }
        return nullptr;
    }
    Node* get_root(Node* v) {
        expose(v);
        while (v->left) {
            eval(v);
            v = v->left;
        }
        return v;
    }
    void evert(Node* u) { expose(u), u->cnt = -(u->cnt); }
    int depth(Node* u) {
        expose(u);
        return _abs(u->cnt) - 1;
    }
    void update(Node* u, Node* v, const T1 x) {
        evert(u), expose(v);
        v->lazy = f1(v->lazy, x), push(v);
    }
    T0 query(Node* u, Node* v) {
        evert(u), expose(v);
        return v->acc;
    }

public:
    BaseLinkCutTree(T0 u0, T1 u1) : u0(u0), u1(u1) {}
    int make_new_node(T0 v) {
        int idx = nodes.size();
        nodes.push_back(new Node(idx, v, u0, u1));
        return idx;
    }
    bool connected(int a, int b) { return connected(nodes[a], nodes[b]); }
    // uとvをつなぐ(evertせずに使える)
    void link(int u, int v) { return link(nodes[u], nodes[v]); }
    // vを親と切り離す
    void cut(int v) { return cut(nodes[v]); }
    int lca(int u, int v) { return lca(nodes[u], nodes[v])->idx; }
    // vから根にk個たどった頂点を返す。とくにget_kth(v, 0)はv
    int get_kth(int v, int k) { return get_kth(nodes[v], k)->idx; }
    int get_root(int v) { return get_root(nodes[v])->idx; }
    // vを根にもってくる
    void evert(int v) { return evert(nodes[v]); }
    int depth(int v) { return depth(nodes[v]); }
    // uvパスに現れるすべての頂点にxを作用させる
    void update(int u, int v, T1 x) { return update(nodes[u], nodes[v], x); }
    void update(int v, T1 x) { update(v, v, x); }
    // uvパスに現れるすべての頂点の累積を求める
    T0 query(int u, int v) { return query(nodes[u], nodes[v]); }
    T0 query(int v) { return query(v, v); }
};

template <class T0, class T1>
struct MinUpdateQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    MinUpdateQuery() : MinUpdateQuery(numeric_limits<T0>::max(), numeric_limits<T1>::min()) {}
    T0 f0(T0 x, T0 y) override { return min(x, y); }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T1 p(T1 x, int len) override { return x; }
};

template <class T0, class T1>
struct SumAddQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    SumAddQuery() : SumAddQuery(0, 0) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return x + y; }
    T0 g(T0 x, T1 y) override { return x + y; }
    T1 p(T1 x, int len) override { return x * len; }
};

template <class T0, class T1>
struct MinAddQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    MinAddQuery() : MinAddQuery(numeric_limits<T0>::max(), 0) {}
    T0 f0(T0 x, T0 y) override { return min(x, y); }
    T1 f1(T1 x, T1 y) override { return x + y; }
    T0 g(T0 x, T1 y) override { return x + y; }
    T1 p(T1 x, int len) override { return x; }
};

template <class T0, class T1>
struct SumUpdateQuery : public BaseLinkCutTree<T0, T1> {
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    SumUpdateQuery() : SumUpdateQuery(0, numeric_limits<T1>::min()) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T1 p(T1 x, int len) override { return x == numeric_limits<T1>::min() ? numeric_limits<T1>::min() : x * len; }
};

template <class T0>
struct SumAffineQuery : public BaseLinkCutTree<T0, pair<T0, T0>> {
    using T1 = pair<T0, T0>;  // first * x + second
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    SumAffineQuery() : SumAffineQuery(0, {1, 0}) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; }
    T0 g(T0 x, T1 y) override { return y.first * x + y.second; }
    T1 p(T1 x, int len) override { return {x.first, x.second * len}; }
    // update(i, j, {a, b}); // [i, j)にax + bを作用
    // update(i, j, {0, a}); // update
    // update(i, j, {1, a}); // 加算
    // update(i, j, {a, 0}); // 倍
};

template <class T>
struct MinmaxAffineQuery : public BaseLinkCutTree<pair<T, T>, pair<T, T>> {
    using T0 = pair<T, T>;  // {min, max}
    using T1 = pair<T, T>;  // first * x + second
    using BaseLinkCutTree<T0, T1>::BaseLinkCutTree;
    MinmaxAffineQuery()
        : MinmaxAffineQuery({numeric_limits<T>::max(), -numeric_limits<T>::max()}, {1, 0}) {
    }  // TODO: _u1を使うとコンパイル通らない原因不明
    T0 f0(T0 x, T0 y) override { return {min(x.first, y.first), max(x.second, y.second)}; }
    T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; }
    T0 g(T0 x, T1 y) override {
        T0 ret = {x.first * y.first + y.second, x.second * y.first + y.second};
        if (y.first < 0) swap(ret.first, ret.second);
        return ret;
    }
    T1 p(T1 x, int len) override { return x; }
    // update(i, j, {a, b}); // [i, j)にax + bを作用
    // update(i, j, {0, a}); // update
    // update(i, j, {1, a}); // 加算
    // update(i, j, {a, 0}); // 倍
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    SumAddQuery<int, int> lct;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) lct.make_new_node(0);

    random_device rnd;

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        lct.link(a, b);

        if (rnd() % 3 == 0) {
            // 適当に回転させて遊んでみる
            int sz = i + 1;
            int v = rnd() % sz;
            lct.evert(v);
        }
        if (i > 0 && rnd() % 5 == 0) {
            // 適当に切り離して遊んでみる
            int sz = i + 1;
            int v = rnd() % sz;
            int depth = lct.depth(v);
            if (depth > 0) {
                int u = lct.get_kth(v, 1);
                lct.cut(v);
                lct.link(u, v);
            }
        }
    }

    int q;
    cin >> q;
    long long ans = 0;
    while (q--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        lct.update(a, b, 1);

        if (rnd() % 3 == 0) {
            // 適当に回転させて遊んでみる
            int v = rnd() % n;
            lct.evert(v);
        }
        if (rnd() % 5 == 0) {
            // 適当に切り離して遊んでみる
            int v = rnd() % n;
            int depth = lct.depth(v);
            if (depth > 0) {
                int u = lct.get_kth(v, 1);
                lct.cut(v);
                int w = rnd() % n;
                if (w != v && w != u) {
                    // さらに回転させて遊ぶ
                    lct.evert(w);
                }
                lct.link(u, v);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        int k = lct.query(i, i);
        ans += 1LL * k * (k + 1) / 2;
    }

    cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード