#869442 (C++14) No.650 行列木クエリ

提出ソース
結果

問題	No.650 行列木クエリ
ユーザー	t98slider
提出日時	2023-05-14 12:06:36
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	216 ms / 2,000 ms
コード長	12,245 bytes
コンパイル時間	2,409 ms
コンパイル使用メモリ	189,920 KB
実行使用メモリ	49,536 KB
最終ジャッジ日時	2024-11-30 01:30:04
合計ジャッジ時間	4,477 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	53 ms 11,008 KB
testcase_02	AC	216 ms 40,320 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	53 ms 11,008 KB
testcase_05	AC	204 ms 40,448 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	45 ms 12,800 KB
testcase_09	AC	119 ms 49,536 KB
testcase_10	AC	2 ms 5,248 KB
権限があれば一括ダウンロードができます
ソースコード

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

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);
    }
};

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
    public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        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;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }
    const S operator[](int p) const { return get(p); }
    S operator[](int p) { return get(p); }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        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]; }

    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(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 (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(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;
    int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

template <class T, size_t N> struct Matrix {
    std::array<std::array<T, N>, N> A{};
    Matrix() {}
    Matrix(const std::array<std::array<T, N>, N> &M) : A(M){}
    Matrix(const std::vector<std::vector<T>> &M)  {
        for(size_t i = 0; i < N; i++){
            for(size_t j = 0; j < N; j++){
                A[i][j] = M[i][j];
            }
        }
    }
    const std::array<T, N>& operator[](int i) const { return A[i]; }
    std::array<T, N>& operator[](int i) { return A[i]; }

    Matrix& operator+=(const Matrix& rhs) {
        for(size_t i = 0; i < N; i++){
            for(size_t j = 0; j < N; j++){
                A[i][j] += rhs[i][j];
            }
        }
        return *this;
    }
    Matrix& operator-=(const Matrix& rhs) {
        for(size_t i = 0; i < N; i++){
            for(size_t j = 0; j < N; j++){
                A[i][j] -= rhs[i][j];
            }
        }
        return *this;
    }
    Matrix& operator*=(const Matrix& rhs) {
        std::array<std::array<T, N>, N> res{};
        for(size_t i = 0; i < N; i++){
            for(size_t j = 0; j < N; j++){
                for(size_t k = 0; k < N; k++){
                    res[i][j] += A[i][k] * rhs[k][j];
                }
            }
        }
        swap(A, res);
        return *this;
    }
    Matrix& operator+() const { return *this; }
    Matrix& operator-() const { return Matrix() - *this; }
    friend Matrix operator+(const Matrix& lhs, const Matrix& rhs) {
        return Matrix(lhs) += rhs;
    }
    friend Matrix operator-(const Matrix& lhs, const Matrix& rhs) {
        return Matrix(lhs) -= rhs;
    }
    friend Matrix operator*(const Matrix& lhs, const Matrix& rhs) {
        return Matrix(lhs) *= rhs;
    }
    friend bool operator==(const Matrix& lhs, const Matrix& rhs) {
        return (lhs.A == rhs.A);
    }
    friend bool operator!=(const Matrix& lhs, const Matrix& rhs) {
        return (lhs.A != rhs.A);
    }
    Matrix pow(long long v){
        Matrix res, temp = A;
        for(size_t i = 0; i < N; i++)res[i][i] = 1;
        while(v){
            if(v & 1)res *= temp;
            temp *= temp;
            v >>= 1;
        }
        return res;
    }
    friend std::ostream& operator << (std::ostream &os, const Matrix& rhs) noexcept {
        for(size_t i = 0; i < N; i++){
            if(i) os << '\n';
            for(size_t j = 0; j < N; j++){
                os << (j ? " " : "") << rhs[i][j];
            }
        }
        return os;
    }
};

template<const unsigned int MOD> struct prime_modint {
    using mint = prime_modint;
    unsigned int v;
    prime_modint() : v(0) {}
    prime_modint(unsigned int a) { a %= MOD; v = a; }
    prime_modint(unsigned long long a) { a %= MOD; v = a; }
    prime_modint(int a) { a %= (int)(MOD); if(a < 0)a += MOD; v = a; }
    prime_modint(long long a) { a %= (int)(MOD); if(a < 0)a += MOD; v = a; }
    static constexpr int mod() { return MOD; }
    mint& operator++() {v++; if(v == MOD)v = 0; return *this;}
    mint& operator--() {if(v == 0)v = MOD; v--; return *this;}
    mint operator++(int) { mint result = *this; ++*this; return result; }
    mint operator--(int) { mint result = *this; --*this; return result; }
    mint& operator+=(const mint& rhs) { v += rhs.v; if(v >= MOD) v -= MOD; return *this; }
    mint& operator-=(const mint& rhs) { if(v < rhs.v) v += MOD; v -= rhs.v; return *this; }
    mint& operator*=(const mint& rhs) {
        v = (unsigned int)((unsigned long long)(v) * rhs.v % MOD);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }
    mint pow(long long n) const {
        assert(0 <= n);
        mint r = 1, x = *this;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const { assert(v); return pow(MOD - 2); }
    friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; }
    friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; }
    friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; }
    friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; }
    friend bool operator==(const mint& lhs, const mint& rhs) { return (lhs.v == rhs.v); }
    friend bool operator!=(const mint& lhs, const mint& rhs) { return (lhs.v != rhs.v); }
    friend std::ostream& operator << (std::ostream &os, const mint& rhs) noexcept { return os << rhs.v; }
};
using mint = prime_modint<1000000007>;
//using mint = prime_modint<998244353>;

using S = Matrix<mint, 2>;
S op(S lhs, S rhs){
    return lhs * rhs;
}

S e(){
    return S({{1, 0}, {0, 1}});
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q, u, v, id;
    char c;
    cin >> n;
    vector<vector<int>> g(n + n - 1);
    for(int i = 0; i + 1 < n; i++){
        cin >> u >> v;
        g[u].emplace_back(i + n);
        g[i + n].emplace_back(u);
        g[v].emplace_back(i + n);
        g[i + n].emplace_back(v);
    }
    Heavy_Light_Decomposition HLD(g);
    S Mt;
    segtree<S, op, e> seg(2 * n - 1);
    auto query = [&](int l, int r){
        return seg.prod(l, r);
    };
    auto merge = [&](S lhs, S rhs){
        return lhs * rhs;
    };
    cin >> q;
    while(q--){
        cin >> c;
        if(c == 'x'){
            cin >> id >> Mt[0][0].v >> Mt[0][1].v >> Mt[1][0].v >> Mt[1][1].v;
            seg.set(HLD[id + n], Mt);
        }else{
            cin >> u >> v;
            Mt = HLD.query(u, v, e(), query, merge);
            cout << Mt[0][0] << " " << Mt[0][1] << " " << Mt[1][0] << " " << Mt[1][1] << '\n';
        }
    }
}
yukicoder

結果

テストケース

ソースコード
