#358606 (C++14) No.399 動的な領主

提出ソース

結果

問題	No.399 動的な領主
ユーザー	kcvlex
提出日時	2019-07-10 14:27:44
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,124 ms / 2,000 ms
コード長	9,385 bytes
コンパイル時間	2,423 ms
コンパイル使用メモリ	194,468 KB
実行使用メモリ	41,088 KB
最終ジャッジ日時	2024-10-15 12:52:58
合計ジャッジ時間	13,583 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	5 ms 5,248 KB
testcase_05	AC	65 ms 5,248 KB
testcase_06	AC	1,090 ms 18,944 KB
testcase_07	AC	1,074 ms 19,072 KB
testcase_08	AC	1,069 ms 19,072 KB
testcase_09	AC	1,081 ms 19,072 KB
testcase_10	AC	8 ms 5,248 KB
testcase_11	AC	49 ms 5,248 KB
testcase_12	AC	740 ms 19,456 KB
testcase_13	AC	698 ms 19,328 KB
testcase_14	AC	207 ms 41,088 KB
testcase_15	AC	385 ms 40,960 KB
testcase_16	AC	520 ms 30,464 KB
testcase_17	AC	1,124 ms 19,072 KB
testcase_18	AC	1,115 ms 19,072 KB

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

ソースコード

raw source code

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

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = int64_t;

template <typename Graph>
struct HeavyLightDecomposition {
    ll root;
    const Graph &graph;
    V<ll> subtree_size, head, parent_node_idx, decomposed_id, component_id, heavy_edge_to;

    HeavyLightDecomposition(const Graph &graph)
        : root(0),
          graph(graph),
          subtree_size(graph.size()),
          head(graph.size()),
          parent_node_idx(graph.size()),
          decomposed_id(graph.size()),
          component_id(graph.size()),
          heavy_edge_to(graph.size())
    {
    }

    ll count_size(ll cur, ll pre) {
        ll ret = 1;
        parent_node_idx[cur] = pre;
        ll max_size = 0, max_size_to = -1;
        for(ll nxt : graph[cur]) {
            if(nxt == pre) continue;
            ll res = count_size(nxt, cur);
            if(max_size < res) {
                max_size = res;
                max_size_to = nxt;
            }
            ret += res;
        }
        heavy_edge_to[cur] = max_size_to;
        return subtree_size[cur] = ret;
    }

    ll get_decomposed_id(ll node) { return node == -1 ? -1 : decomposed_id[node]; }

    void build_component(ll cur, ll pre, ll &decomposed_id_counter, ll &total_hl) {
        decomposed_id[cur] = decomposed_id_counter++;
        component_id[cur] = total_hl;
        head[cur] = (get_decomposed_id(pre) == -1 ? cur :
                     component_id[cur] == component_id[pre] ? head[pre] : cur);

        if(heavy_edge_to[cur] != -1) build_component(heavy_edge_to[cur], cur, decomposed_id_counter, total_hl);

        for(ll nxt : graph[cur]) {
            if(nxt == pre || nxt == heavy_edge_to[cur]) continue;
            build_component(nxt, cur, decomposed_id_counter, ++total_hl);
        }
    }

    void decompose() {
        count_size(root, -1);
        ll decomposed_id_counter = 0;
        ll total_hl = 0;
        build_component(root, -1, decomposed_id_counter, total_hl);
    }

    // careful : when query handle edges
    template <typename T>
    T query(ll n1, ll n2, const function<T(ll, ll)> &calc_component, T identity, const function<T(T, T)> &merge) {
        T lval = identity, rval = identity;
        T result = identity;
        while(true) {
            if(component_id[n1] != component_id[n2]) {
                if(decomposed_id[n1] < decomposed_id[n2]) {
                    T tmp = calc_component(decomposed_id[head[n2]], decomposed_id[n2] + 1);
                    rval = merge(tmp, rval);
                    n2 = parent_node_idx[head[n2]];
                } else {
                    T tmp = calc_component(decomposed_id[head[n1]], decomposed_id[n1] + 1);
                    lval = merge(lval, tmp);
                    n1 = parent_node_idx[head[n1]];
                }
            } else {
                ll id1 = decomposed_id[n1];
                ll id2 = decomposed_id[n2];
                result = calc_component(min(id1, id2), max(id1, id2) + 1);
                result = merge(lval, result);
                result = merge(result, rval);
                break;
            }
        }
        return result;
    }

    void query(ll n1, ll n2, const function<void(ll, ll)> &calc_component) {
        ll identity = 0;
        auto merge = [&](ll a, ll b) { return 0; };
        auto wrapper_calc = [&](ll a, ll b) { calc_component(a, b); return 0; };
        query<ll>(n1, n2, wrapper_calc, identity, merge);
    }
};

// solution for https://yukicoder.me/problems/no/399

template <typename T, typename L>
class LazySegmentTree{
private:
    ll N;
    T init_node;
    L init_lazy;
    vector<T> node;
    vector<L> lazy;
    vector<bool> lazy_flag;
    function<T(T, T)> merge_node;
    function<T(T, L)> apply_lazy_value;
    function<L(L, L)> update_lazy_value;
    function<L(ll, ll, L)> create_lazy_value;
    function<L(L)> prop_lazy_value;
    
public:
    LazySegmentTree(const vector<T> &v, 
                    const T &init_node,
                    const L &init_lazy, 
                    const decltype(merge_node)        &merge_node,
                    const decltype(apply_lazy_value)  &apply_lazy_value,
                    const decltype(update_lazy_value) &update_lazy_value,
                    const decltype(create_lazy_value) &create_lazy_value,
                    const decltype(prop_lazy_value)   &prop_lazy_value = [](L v) { return v; })
        : init_node(init_node),
          init_lazy(init_lazy),
          merge_node(merge_node),
          apply_lazy_value(apply_lazy_value),
          update_lazy_value(update_lazy_value),
          create_lazy_value(create_lazy_value),
          prop_lazy_value(prop_lazy_value)
    {
        ll tmp = 1;
        while(tmp < v.size()) tmp *= 2;
        N = tmp;
        node.resize(2 * N - 1, init_node);
        lazy.resize(2 * N - 1, init_lazy);
        lazy_flag.resize(2 * N - 1, false);
        for(ll i = 0; i < v.size(); i++) {
            node[i + N - 1] = v[i];
        }
        for(ll i = N - 2; 0 <= i; i--) {
            node[i] = merge_node(node[i * 2 + 1], node[i * 2 + 2]);
        }
    }

    /*
     * node[pos] -> [left, right)
     */
    void lazy_eval(ll pos, ll left, ll right) {
        if(!lazy_flag[pos]) {
            return;
        }

        node[pos] = apply_lazy_value(node[pos], lazy[pos]);
        lazy_flag[pos] = false;

        /* 
         * whether the node is the bottom of tree or not.
         */
        if(right - left > 1) {
            for(ll idx = 2 * pos + 1; idx <= 2 * pos + 2; idx++) {
                lazy[idx] = update_lazy_value(lazy[idx], prop_lazy_value(lazy[pos]));
                lazy_flag[idx] = true;
            }
        }

        lazy[pos] = init_lazy;
    }

    /*
     * If you want to call this func from out of class, in many cases you don't have to change the args pos, node_left, node_right.
     * Be careful that the range is half-open interval.
     * [left, right), [node_left, node_right)
     * @param left:         lower limit of interval of query
     * @param right:        upper limit of interval of query
     * @param val:          the value gave from query
     * @param node_left:    lower limit of interval of the node points.
     * @param node_right:   upper limit of interval of the node points.
     */
    void update_query(ll left, ll right, L val, ll pos = 0, ll node_left = 0, ll node_right = -1) {
        if(node_right < 0) {
            node_right = N;
        }

        /*
         * Execute lazy evaluation.
         */
        lazy_eval(pos, node_left, node_right);

        /*
         * If the node is out of inrerval, return.
         */
        if(right <= node_left || node_right <= left) {
            return;
        }


        /*
         * If the node cover the interval complety, update this->lazy and execute lazy_eval.
         * Else recursion.
         */
        if(left <= node_left && node_right <= right) {
            lazy[pos] = create_lazy_value(node_left, node_right, val);
            lazy_flag[pos] = true;
            lazy_eval(pos, node_left, node_right);
        } else {

            /*
             * recursion
             */
            update_query(left, right, val, 2 * pos + 1, node_left, (node_left + node_right) / 2);
            update_query(left, right, val, 2 * pos + 2, (node_left + node_right) / 2, node_right);

            node[pos] = merge_node(node[2 * pos + 1], node[2 * pos + 2]);
        }
    }

    T get_query(ll left, ll right, ll pos = 0, ll node_left = 0, ll node_right = -1) {
        if(node_right < 0) {
            node_right = N;
        }

        /*
         * Evaluate the node[pos]
         */
        lazy_eval(pos, node_left, node_right);

        if(node_right <= left || right <= node_left) {
            return init_node;
        }
        if(left <= node_left && node_right <= right) {
            return node[pos];
        }

        ll split = (node_left + node_right) / 2;
        return merge_node(get_query(left, right, 2 * pos + 1, node_left, split),
                          get_query(left, right, 2 * pos + 2, split, node_right));
    }
};

VV<ll> edges;

#define VERIFY
#ifdef VERIFY

int main() {
    ll N;
    cin >> N;
    edges.resize(N);
    for(ll i = 1; i < N; i++) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    HeavyLightDecomposition<VV<ll>> hld(edges);
    hld.decompose();
    LazySegmentTree<ll, ll> lst(V<ll>(N, 1), 0, 0,
                                [](ll a, ll b) { return a + b; },
                                [](ll a, ll b) { return a + b; },
                                [](ll a, ll b) { return a + b; },
                                [](ll l, ll r, ll v) { return (r - l) * v; },
                                [](ll v) { return v / 2; });

    auto update = [&](ll a, ll b) { lst.update_query(a, b, 1); };
    auto calc_tax = [&](ll a, ll b) { return lst.get_query(a, b); };
    auto merge = [&](ll a, ll b) { return a + b; };

    ll Q;
    cin >> Q;
    ll ans = 0;
    while(Q--) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        ll val = hld.query<ll>(a, b, calc_tax, 0, merge);
        ans += val;
        hld.query(a, b, update);
    }
    cout << ans << endl;
    return 0;
}

#endif