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

提出ソース

結果

問題	No.399 動的な領主
ユーザー	t98slider
提出日時	2023-01-28 16:39:27
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	571 ms / 2,000 ms
コード長	10,117 bytes
コンパイル時間	2,172 ms
コンパイル使用メモリ	181,828 KB
実行使用メモリ	26,884 KB
最終ジャッジ日時	2023-09-11 05:27:05
合計ジャッジ時間	9,373 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	2 ms 4,376 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	4 ms 4,376 KB
testcase_05	AC	34 ms 5,124 KB
testcase_06	AC	567 ms 22,212 KB
testcase_07	AC	547 ms 22,156 KB
testcase_08	AC	551 ms 22,292 KB
testcase_09	AC	547 ms 22,216 KB
testcase_10	AC	4 ms 4,380 KB
testcase_11	AC	26 ms 5,124 KB
testcase_12	AC	390 ms 23,008 KB
testcase_13	AC	376 ms 23,252 KB
testcase_14	AC	91 ms 26,708 KB
testcase_15	AC	129 ms 26,884 KB
testcase_16	AC	211 ms 24,520 KB
testcase_17	AC	571 ms 22,292 KB
testcase_18	AC	559 ms 22,032 KB

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

ソースコード

raw source code

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

template <class S,
            S (*op)(S, S),
            S (*e)(),
            class F,
            S (*mapping)(F, S),
            F (*composition)(F, F),
            F (*id)()>
struct lazy_segtree {
    public:
        lazy_segtree() : lazy_segtree(0) {}
        lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
        lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
                update(i);
            }
        }
        void set(int p, S x) {
            assert(0 <= p && p < _n);
            p += size;
            for (int i = log; i >= 1; i--) push(p >> i);
            d[p] = x;
            for (int i = 1; i <= log; i++) update(p >> i);
        }
        S get(int p) {
            assert(0 <= p && p < _n);
            p += size;
            for (int i = log; i >= 1; i--) push(p >> i);
            return d[p];
        }
        S prod(int l, int r) {
            assert(0 <= l && l <= r && r <= _n);
            if (l == r) return e();
            l += size;
            r += size;
            for (int i = log; i >= 1; i--) {
                if (((l >> i) << i) != l) push(l >> i);
                if (((r >> i) << i) != r) push(r >> i);
            }
        S sml = e(), smr = e();
            while (l < r) {
                if (l & 1) sml = op(sml, d[l++]);
                if (r & 1) smr = op(d[--r], smr);
                l >>= 1;
                r >>= 1;
            }
            return op(sml, smr);
        }
        S all_prod() { return d[1]; }
        void apply(int p, F f) {
            assert(0 <= p && p < _n);
            p += size;
            for (int i = log; i >= 1; i--) push(p >> i);
            d[p] = mapping(f, d[p]);
            for (int i = 1; i <= log; i++) update(p >> i);
        }
        void apply(int l, int r, F f) {
            assert(0 <= l && l <= r && r <= _n);
            if (l == r) return;
            l += size;
            r += size;
            for (int i = log; i >= 1; i--) {
                if (((l >> i) << i) != l) push(l >> i);
                if (((r >> i) << i) != r) push((r - 1) >> i);
            }
            {
                int l2 = l, r2 = r;
                while (l < r) {
                    if (l & 1) all_apply(l++, f);
                    if (r & 1) all_apply(--r, f);
                    l >>= 1;
                    r >>= 1;
                }
                l = l2;
                r = r2;
            }
            for (int i = 1; i <= log; i++) {
                if (((l >> i) << i) != l) update(l >> i);
                if (((r >> i) << i) != r) update((r - 1) >> i);
            }
            }
        template <bool (*g)(S)> int max_right(int l) {
            return max_right(l, [](S x) { return g(x); });
        }
        template <class G> int max_right(int l, G g) {
            assert(0 <= l && l <= _n);
            assert(g(e()));
            if (l == _n) return _n;
            l += size;
            for (int i = log; i >= 1; i--) push(l >> i);
            S sm = e();
            do {
                while (l % 2 == 0) l >>= 1;
                if (!g(op(sm, d[l]))) {
                    while (l < size) {
                        push(l);
                        l = (2 * l);
                        if (g(op(sm, d[l]))) {
                            sm = op(sm, d[l]);
                            l++;
                        }
                    }
                    return l - size;
                }
                sm = op(sm, d[l]);
                l++;
            } while ((l & -l) != l);
            return _n;
        }
        template <bool (*g)(S)> int min_left(int r) {
            return min_left(r, [](S x) { return g(x); });
        }
        template <class G> int min_left(int r, G g) {
            assert(0 <= r && r <= _n);
            assert(g(e()));
            if (r == 0) return 0;
            r += size;
            for (int i = log; i >= 1; i--) push((r - 1) >> i);
            S sm = e();
            do {
                r--;
                while (r > 1 && (r % 2)) r >>= 1;
                if (!g(op(d[r], sm))) {
                    while (r < size) {
                        push(r);
                        r = (2 * r + 1);
                        if (g(op(d[r], sm))) {
                            sm = op(d[r], sm);
                            r--;
                        }
                    }
                    return r + 1 - size;
                }
                sm = op(d[r], sm);
            } while ((r & -r) != r);
            return 0;
        }
    private:
        int _n, size, log;
        std::vector<S> d;
        std::vector<F> lz;
        void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
        void all_apply(int k, F f) {
            d[k] = mapping(f, d[k]);
            if (k < size) lz[k] = composition(f, lz[k]);
        }
        void push(int k) {
            all_apply(2 * k, lz[k]);
            all_apply(2 * k + 1, lz[k]);
            lz[k] = id();
        }
        int ceil_pow2(int n) {
            int x = 0;
            while ((1U << x) < (unsigned int)(n)) x++;
            return x;
        }
};

using S = pair<ll, ll>;
using F = int;
//単位元
S e(){return make_pair(0, 0);}
//演算
S op(S l,S r){return make_pair(l.first + r.first, l.second + r.second);}
//xにfを作用させた時の値の変化
S mapping(F f,S x){return make_pair(x.first + x.second * f, x.second);}
//gを演算した後にfを演算させると演算子はどうなるか
F composition(F f, F g){return g + f;}
//作用させても変化させないもの
F id(){return 0;}

struct Heavy_Light_Decomposition{
    int N, tim = 0;
    std::vector<int> sz, ent, leader, order, par;
    std::vector<std::vector<int>> G;
    Heavy_Light_Decomposition(std::vector<std::vector<int>> &g) : 
            N(g.size()), G(g), sz(N), ent(N), leader(N), order(N), par(N) {
        dfs_size(0, -1);
        dfs_hld(0);
    }
    const int& operator[](int v) const {
        assert(0 <= v && v < N);
        return ent[v];
    }
    int& operator[](int v) { 
        assert(0 <= v && v < N);
        return ent[v];
    }
    void dfs_size(int v, int p){
        par[v] = p;
        sz[v] = 1;
        if(!G[v].empty() && G[v][0] == p) std::swap(G[v][0], G[v].back());
        for(auto &u : G[v]){
            if(u == p) continue;
            dfs_size(u, v);
            sz[v] += sz[u];
            if(sz[u] > sz[G[v][0]]) std::swap(G[v][0], u);
        }
    }
    void dfs_hld(int v){
        ent[v] = tim++;
        order[ent[v]] = v;
        for(auto &u : G[v]) {
            if(u == par[v]) continue;
            leader[u] = (G[v][0] == u ? leader[v] : u);
            dfs_hld(u);
        }
    }
    int la(int v, int k) {
        while(true) {
            int u = leader[v];
            if(ent[v] - k >= ent[u]) return order[ent[v] - k];
            k -= ent[v] - ent[u] + 1;
            v = par[u];
        }
    }
    int lca(int u, int v) {
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) return u;
            v = par[leader[v]];
        }while(true);
    }
    //(頂点u, 頂点v, 単位元, 列に対するクエリの収得, 列と列の結合, 辺か頂点か)
    template< typename T, typename Q, typename F >
    T query(int u, int v, const T &identity, const Q &qf, const F &f, bool edge = false) {
        T ans = identity;
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) break;
            ans = f( qf(ent[leader[v]], ent[v] + 1), ans);
            v = par[leader[v]];
        }while(true);
        return f( qf(ent[u] + edge, ent[v] + 1), ans);
    }
    //u -> lhs -> rhs -> vで演算を走らせる
    //セグ木を作る場合は
    //up_f(l, r) = op(lhs, rhs)
    //down_f(l, r) = op(rhs, lhs)
    //で定義する
    template< typename T, typename Q1, typename Q2, typename F >
    T query2(int u, int v, const T &identity, const Q1 &up_f, const Q2 &down_f, const F &f, bool edge = false) {
        T sml = identity, smr = identity;
        do{
            if(leader[u] == leader[v]) break;
            if(ent[u] < ent[v]){
                smr = f( up_f(ent[leader[v]], ent[v] + 1), smr);
                v = par[leader[v]];
            }else{
                sml = f( sml, down_f(ent[leader[u]], ent[u] + 1));
                u = par[leader[u]];
            }
        }while(true);
        if(ent[u] < ent[v]){
            return f(sml,  f( up_f(ent[u] + edge, ent[v] + 1), smr));
        }else{
            return f(f(sml, down_f(ent[v] + edge, ent[u] + 1)), smr);
        }
    }
    //(頂点u, 頂点v, 列に対するupdate関数, 辺か頂点か)
    template< typename Q >
    void update(int u, int v, const Q &q, bool edge = false) {
        do{
            if(ent[u] > ent[v]) std::swap(u, v);
            if(leader[u] == leader[v]) break;
            q(ent[leader[v]], ent[v] + 1);
            v = par[leader[v]];
        }while(true);
        q(ent[u] + edge, ent[v] + 1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, u, v, Q;
    ll ans = 0;
    cin >> N;
    vector<vector<int>> g(N);
    for(int i = 1; i < N; i++){
        cin >> u >> v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    Heavy_Light_Decomposition HLD(g);
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<S>(N, make_pair(1, 1)));
    auto f = [&](ll lhs, ll rhs){
        return lhs + rhs;
    };
    auto qf = [&](int l, int r){
        return seg.prod(l, r).first;
    };
    auto update = [&](int l, int r){
        seg.apply(l, r, 1);
    };
    cin >> Q;
    while(Q--){
        cin >> u >> v;
        u--, v--;
        ans += HLD.query(u, v, 0ll, qf, f);
        HLD.update(u, v, update);
    }
    cout << ans << '\n';
}

yukicoder

結果

テストケース

ソースコード