#956429 (C++23) No.399 動的な領主

提出ソース

結果

問題	No.399 動的な領主
ユーザー	Astral__
提出日時	2024-02-29 21:27:36
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	641 ms / 2,000 ms
コード長	8,634 bytes
コンパイル時間	3,780 ms
コンパイル使用メモリ	273,592 KB
実行使用メモリ	26,624 KB
最終ジャッジ日時	2024-09-29 12:58:28
合計ジャッジ時間	10,220 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	4 ms 6,820 KB
testcase_05	AC	39 ms 6,816 KB
testcase_06	AC	641 ms 15,232 KB
testcase_07	AC	620 ms 15,104 KB
testcase_08	AC	621 ms 15,360 KB
testcase_09	AC	627 ms 15,488 KB
testcase_10	AC	5 ms 6,816 KB
testcase_11	AC	28 ms 6,816 KB
testcase_12	AC	450 ms 15,616 KB
testcase_13	AC	426 ms 15,640 KB
testcase_14	AC	169 ms 26,624 KB
testcase_15	AC	215 ms 26,624 KB
testcase_16	AC	294 ms 20,864 KB
testcase_17	AC	638 ms 15,232 KB
testcase_18	AC	606 ms 15,360 KB

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

ソースコード

raw source code

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

template<typename X, typename E>
struct LazySegTree {
    using FX = function<X(X, E, long long)>;//Xに作用素Mを作用させる
    
    int n;
    int siz;
    FX fx; 
    vector<X> dat;
    vector<E> lazy;
    LazySegTree(){}
    LazySegTree(int _siz, FX _fx) : siz(_siz),  fx(_fx) {
        n = 1;
        while(n < siz) n <<= 1;
        dat.assign(n * 2, X::ide());
        lazy.assign(n * 2, E::ide());
    }

    private:
        void eval(int k, int len) {
            if(lazy[k] == E::ide()) return;
            if(k < n) {
              lazy[k<<1] = op(lazy[k<<1], lazy[k]);
              lazy[k<<1|1] = op(lazy[k<<1|1], lazy[k]);
            }
            dat[k] = fx(dat[k], lazy[k], len);
            lazy[k] = E::ide();
        }    

        X query(int a, int b, int l, int r, int k) {
            eval(k,r-l);
            if(r <= a || b <= l) return X::ide();
            if(a <= l && r <= b) return dat[k];
            int mid = (l + r)>>1;
            X L = query(a, b, l, mid, k<<1);
            X R = query(a, b, mid, r, k<<1|1);
            return op(L, R);
        }  

        void update(int a, int b, E m, int l, int r,  int k) {//[a, b) := クエリ区間  [l, r) := 今見ている区間
            eval(k, r-l);
            if(r <= a || b <= l) return;
            if(a <= l && r <= b) {
                lazy[k] = op(lazy[k], m);
                eval(k, r-l);
            }
            else {
                int mid = (l + r)>>1;
                update(a, b, m, l, mid, k<<1);
                update(a, b, m, mid, r, k<<1|1);
                dat[k] = op(dat[k<<1], dat[k<<1|1]);
            }
        }   
    
    public:

        void set(int i, X x) {
            dat[i + n - 1] =  x;
        }    

        void init() {
            for(int i = n-1; i >= 1; i--) {
                dat[i] = op(dat[i*2], dat[i * 2 + 1]);
            }
        }    
    
        void change(int l, int r, E m) {
            update(l, r + 1, m, 1, n + 1, 1);
        }

        X get(int l, int r) {
          return query(l, r + 1, 1, n + 1, 1);
        }

        void dump() {
            for(int i = 1; i <= siz; i++) {
                cout << get(i, i) << " ";//適宜直す。
            }
            cout << endl;
        }
};    






template <typename X, typename E>
struct HLD {
    vector<int> siz;//[元の頂点番号] = サイズ
    vector<int> num;//[元の頂点番号] = 振り直した頂点番号
    vector<int> numrev;
    vector<int> out;//[元の頂点番号] = new  半開区間で、その頂点を出た時の値 + 1
    vector<int> par;//[振られた] = 振られた 自分の親
    vector<int> head;//[振られた番号] = 振られた番号 自分の連結成分の頭
    LazySegTree<X, E> seg;
    using FX = function<X(X, E, long long)>;
    FX fx;
    int N;
    int size = 1;
    
  
    HLD(int _N, vector<vector<int>>& G, FX _fx) : N(_N), fx(_fx) {
        par.resize(N+1);
        iota(par.begin(), par.end(), 0);
        siz.resize(N+1, 1);
        num.assign(N+1, -1);
        numrev.resize(N+1, -1);
        out.resize(N+1, -1);
        head.resize(N+1);
        seg = LazySegTree<X, E>(N, fx);
    
        auto dfs_siz = [&](auto f, int now, int prev) -> void {
            int sum = 1;
            for(int to : G[now]) {
                if(to == prev) continue;
                f(f, to, now);
                sum += siz[to];
            }
            siz[now] = sum;
            return;
        };
        dfs_siz(dfs_siz, 1, -1);
        for(int i = 1; i <= N; i++) {
            sort(G[i].begin(), G[i].end(), [&](int a, int b) {
              return siz[a] > siz[b];
            });
        }
    
        int idx = 1;
        auto dfs_bunkai = [&](auto f, int now, int prev, int hed) -> void {
            num[now] = idx;//番号付
            numrev[idx] = now;
            idx++;
            par[num[now]] = prev;//親の頂点   //1だけは直前も自分も1
            if(hed == -1)hed = num[now];
            head[num[now]] = hed;
      
            bool flag = true;
            
            for(int i = 0; i <= int(G[now].size()) - 1; i++) {
                if(num[G[now][i]] != -1) continue;
                if(flag) f(f, G[now][i], num[now], hed), flag = false;
                else f(f, G[now][i], num[now], -1);
            }
            out[now] = idx;
            return;
        };
        dfs_bunkai(dfs_bunkai, 1, 1, -1);
    }


    private:

        X get__(int u, int v) {
            int w = num[getLCA(u, v)];//lcaで左右に分ける
            u = num[u];
            v = num[v];
            X L = X::ide(), R = X::ide();
            while(u != w) {
                int hed = max<int>(head[u], w+1);//wまで登ると、wを左右で2回カウントしてしまう。
                L = op(seg.get(hed, u), L); //根から上の方へ
                if(hed != w)  u = par[hed];
                else u = w;
            }   
            L = op(seg.get(w, w), L);//根から上の方へ
            while(v != w) {
                int hed = max<int>(head[v], w+1);
                R = op(seg.get(hed, v), R); //根から上の方へ
                if(hed != w)  v = par[hed];
                else v = w;
            }
            return op(L, R);//交換則を要する時はこの行を変更する必要があるかもしれない : 無いと思うがr
        }

        void change__(int u, int v, E e) {
            int w = num[getLCA(u, v)];//lcaで左右に分ける
            u = num[u];
            v = num[v];
            while(u != w) {
                int hed = max<int>(head[u], w+1);//wまで登ると、wを左右で2回カウントしてしまう。
                seg.change(hed, u, e); //根から上の方へ
                if(hed != w)  u = par[hed];
                else u = w;
            }   
            seg.change(w, w, e);
            while(v != w) {
                int hed = max<int>(head[v], w+1);
                seg.change(hed, v, e);
                if(hed != w)  v = par[hed];
                else v = w;
            }

        }
    
    public:

        void set(int pos, X x) {
            pos = num[pos];
            seg.set(pos, x);
        }

        void init() {
            seg.init();
        }

        void change(int u, int v,  E e) {
            change__(u, v, e);
        }

        X get(int u, int v) {
            return get__(u, v);
        }

        X subtree(int v) {
            int l = num[v];
            int r = out[v] - 1;
            return seg.get(l, r);
        }
  
        int getLCA(int a, int b) {//入 : 元番号  出 : 元番号
            a = num[a];
            b = num[b];
            while(true) {
                if(a > b) swap(a, b);
                if(head[a] == head[b]) return numrev[a];
                b = par[head[b]];
            }
        }
      
        int parent(int a) {//入 : 元番号
            return numrev[par[num[a]]];
        }

        /*
        Brief hld。
        HLD<Monoid> hld(N, G)  N...max_n G ... graph

        パスに対するクエリがlog^2
        部分木に対するクエリがlog
        
        */
};  



struct Monoid {
    ll a;
   
    Monoid(){}
      
    Monoid(ll _a) : a(_a) {
      
    }

    friend Monoid op(const Monoid& l, const Monoid& r) {
      return l.a + r.a;
    }

    static Monoid ide() {
       return 0LL;
    }
    
    bool operator==(const Monoid& x) const {return a == x.a;}
    bool operator!=(const Monoid& x) const {return !(*this == x);}
};


struct E {    
    ll a;
   
    E(){}
      
    E(ll _a) : a(_a) {}

    friend E op(const E& l, const E& r) {//rのが新しい。(affine)
        return l.a + r.a;
      
    }
    static E ide() {
       return 0LL;
    }
   
    bool operator==(const E& x) const {return (a == x.a);}
    bool operator!=(const E& x) const {return !(*this == x);}

};

Monoid fx(const Monoid& l, const E& r, long long len) {
     return l.a + r.a * len;
}


int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int N;
    cin >> N;
    vector<vector<int>> G(N+1);
    for(int i = 1; i < N; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    HLD<Monoid, E> hld(N, G, fx);
    for(int i = 1; i <= N; i++) hld.set(i, 1);
    hld.init();
    int Q;
    cin >> Q;

    long long ans = 0;

    while(Q--) {
        int a, b;
        cin >> a >> b;
        ans += hld.get(a, b).a;
        hld.change(a, b, 1);

    }

    cout << ans << endl;

  
}

yukicoder

結果

テストケース

ソースコード