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

提出ソース

結果

問題	No.650 行列木クエリ
ユーザー	tossy
提出日時	2018-03-11 18:55:06
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	134 ms / 2,000 ms
コード長	6,654 bytes
コンパイル時間	2,011 ms
コンパイル使用メモリ	187,188 KB
実行使用メモリ	17,108 KB
最終ジャッジ日時	2024-10-15 00:21:11
合計ジャッジ時間	3,042 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 7,936 KB
testcase_01	AC	59 ms 9,116 KB
testcase_02	AC	134 ms 16,316 KB
testcase_03	AC	3 ms 7,492 KB
testcase_04	AC	58 ms 9,676 KB
testcase_05	AC	131 ms 16,428 KB
testcase_06	AC	4 ms 7,216 KB
testcase_07	AC	4 ms 7,376 KB
testcase_08	AC	57 ms 8,956 KB
testcase_09	AC	116 ms 17,108 KB
testcase_10	AC	4 ms 6,980 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp make_pair
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

template<int mod=1000000007>
class ModInt {
  int x;
public:
  ModInt() : x(0) {}
  ModInt(const ModInt &y): x(y.x) {}
  ModInt(int64_t y){ x = y % mod; if(x < 0) x += mod; }
  ModInt &operator += (const ModInt &p){ x += p.x; if(x >= mod) x -= mod; return *this; }
  ModInt &operator -= (const ModInt &p){ x -= p.x; if(x < 0) x += mod; return *this; }
  ModInt &operator *= (const ModInt &p){ x = (int) (1LL * x * p.x % mod); return *this; }
  ModInt &operator /= (const ModInt &p){ *this *= p.inverse(); return *this; }
  ModInt operator -() const { return ModInt(-x); }
  ModInt operator + (const ModInt &p) const { return ModInt(*this) += p; }
  ModInt operator - (const ModInt &p) const { return ModInt(*this) -= p; }
  ModInt operator * (const ModInt &p) const { return ModInt(*this) *= p; }
  ModInt operator / (const ModInt &p) const { return ModInt(*this) /= p; }
  bool operator == (const ModInt &p) const { return x == p.x; }
  bool operator != (const ModInt &p) const { return x != p.x; }
  ModInt operator = (const int64_t y) { return *this = ModInt(y); }
  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0){
      t = a/b; a -= t*b; swap(a, b);
      u -= t*v; swap(u, v);
    }
    return ModInt(u);
  }
  ModInt pow(int64_t y) const {
    if(x==0) return ModInt(0);
    int64_t r = 1, t = x;
    while(y > 0){
      if(y&1) r = r*t%mod;
      t = t*t%mod; y >>= 1;
    }
    return ModInt(r);
  }
  friend ostream &operator << (ostream &os, const ModInt<mod> &p) { return os<<p.x; }
  friend istream &operator >> (istream &is, ModInt<mod> &a) { int64_t x; is>>x; a = ModInt<mod>(x); return is; }
};
using Int = ModInt<>;

struct mat {
  Int a,b,c,d;
  mat() : a(1), b(0), c(0), d(1) {}
  mat(Int a0, Int a1, Int a2, Int a3) : a(a0), b(a1), c(a2), d(a3) {}
  mat &operator *= (const mat &p){
    Int n0 = a*p.a + b*p.c;
    Int n1 = a*p.b + b*p.d;
    Int n2 = c*p.a + d*p.c;
    Int n3 = c*p.b + d*p.d;
    a = n0;
    b = n1;
    c = n2;
    d = n3;
    return *this;
  }
  mat operator * (const mat &p) const {
    return mat(*this) *= p;
  }
  friend ostream &operator << (ostream &os, const mat &p) {
    os << p.a << " " << p.b << " " << p.c << " " << p.d;
    return os;
  }
};

template<typename T>
class SegTree {
public:
  int n;
  T e;
  T (*op)(const T&, const T&);
  vector<T> data;
  SegTree(int m, T _e, T (*_op)(const T&, const T&)) : e(_e), op(_op){
    n=1;
    while(n<m) n*=2;
    data.resize(2*n, e);
  }
  SegTree(const vector<T> &v, T _e, T (*_op)(const T&, const T&)) : e(_e), op(_op){
    n=1;
    while(n<(int)v.size()) n*=2;
    data.resize(2*n, e);
    rep(i,v.size()) data[i+n] = v[i];
    for(int i=n-1; i>0; i--) data[i] = op(data[i*2], data[i*2+1]);
  }
  T query(int l, int r) const {
    T vl = e, vr = e;
    for(l+=n, r+=n; l<r; l/=2, r/=2){
      if(l&1) vl = op(vl, data[l++]);
      if(r&1) vr = op(data[--r], vr);
    }
    return op(vl,vr);
  }
  void update(int k, T a){
    k+=n;
    data[k]=a;
    while(k>0){
      k = k/2;
      data[k] = op(data[k*2], data[k*2+1]);
    }
  }
  inline T operator[](int idx) const { return data[idx+n]; }
};

template<int SZ>
class HLDecomp {
private:
  int n;
  void dfs(const int root){
    stack<pair<int,bool> > st;
    par[root] = -1;
    dep[root] = 0;
    st.push({root,false});
    while(!st.empty()){
      int v = st.top().first;
      bool &b = st.top().second;
      if(!b){
        // initial visit of v
        b = true;
        for(int u : tree[v]) if(u != par[v]){
          par[u] = v;
          dep[u] = dep[v] + 1;
          // st.push({u, false});
          st.push(mp(u, false));
        }
      }
      else {
        // second visit
        st.pop();
        int cur_max = 0;
        for(int u : tree[v]) if(u != par[v]){
          sub_sz[v] += sub_sz[u];
          if(sub_sz[u] > cur_max){
            cur_max = sub_sz[u];
            heavy_child[v] = u;
          }
        }
      }
    }
  }
  void bfs(const int root){
    int cnt = 0;
    queue<int> q;
    q.push(root);
    while(!q.empty()){
      int h = q.front(); q.pop();
      for(int i=h; i!=-1; i = heavy_child[i]){
        vid[i] = cnt++;
        vid2idx[vid[i]] = i;
        chain_head[i] = h;
        for(int to : tree[i]) if(to!=par[i] && to!=heavy_child[i]) q.push(to);
      }
    }
  }
public:
  vector<int> tree[SZ];
  int par[SZ], dep[SZ], sub_sz[SZ], heavy_child[SZ], vid[SZ], vid2idx[SZ], chain_head[SZ];
  HLDecomp(const int _n) : n(_n) {
    assert(n<=SZ);
    fill(sub_sz, sub_sz+n, 1);
    fill(heavy_child, heavy_child+n, -1);
  }
  void add_edge(const int u, const int v){
    tree[u].push_back(v);
    tree[v].push_back(u);
  }
  void build(const int root = 0){
    dfs(root);
    bfs(root);
  }

  // 辺は子側の頂点で管理する!
  void for_each_edge(int u, int v, const function<void(int,int)> &f) const {
    while(true){
      if(vid[u] > vid[v]) swap(u,v);
      if(chain_head[u] != chain_head[v]){
        f(vid[chain_head[v]], vid[v]);
        v = par[chain_head[v]];
      }
      else {
        if(u!=v) f(vid[u]+1, vid[v]);
        break;
      }
    }
  }
};

int main(){
  int n;
  cin>>n;
  HLDecomp<100005> hl(n);
  vector<int> a(n-1), b(n-1);
  rep(i,n-1){
    cin>>a[i]>>b[i];
    hl.add_edge(a[i], b[i]);
  }

  hl.build();

  SegTree<mat> st(n, mat(), [](auto l, auto r){return l*r;});

  int q;
  cin>>q;
  rep(_,q){
    string s;
    cin>>s;
    if(s[0]=='g'){
      int l,r;
      cin>>l>>r;
      mat ans;
      hl.for_each_edge(l, r, [&](auto vl, auto vr){//dbg(ans,vl,vr,st.query(vl,vl+1));
        ans = st.query(vl, vr+1) * ans;
      });
      cout << ans << "\n";
    } else {
      int p,aa,bb,c,d;
      cin>>p>>aa>>bb>>c>>d;
      st.update(max(hl.vid[a[p]], hl.vid[b[p]]), mat(aa,bb,c,d));
    }
  }

  return 0;
}

yukicoder

結果

テストケース

ソースコード