結果

問題 No.650 行列木クエリ
コンテスト
ユーザー tossy
提出日時 2018-02-09 23:55:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,927 bytes
コンパイル時間 2,052 ms
コンパイル使用メモリ 178,620 KB
実行使用メモリ 24,696 KB
最終ジャッジ日時 2024-10-09 09:04:37
合計ジャッジ時間 3,323 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
  }
  mat inverse() const {
    Int id = (a*d - b*c).inverse();
    return mat(id*d, -id*b, -id*c, id*a);
  }
  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)(T, T);
  vector<T> data;
  SegTree(int m, T _e, T (*_op)(T, 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)(T, T)) : e(_e), op(_op){
    // not well verified yet
    n=1;
    while(n<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){
    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){ return data[idx+n]; }
};

vector<pair<int,int>> tree[100005];
// to,id

int bg[100005];
int ed[100005];
int id_in[100005];
int id_out[100005];
int tc = 0;

void build(int v, int from){
  bg[v] = tc++;
  for(auto to : tree[v]) if(to.fi != from){
    id_in[to.se] = tc;
    build(to.fi, v);
    id_out[to.se] = tc-1;
  }
  ed[v] = tc++;
}

int main(){
  int n;
  cin>>n;
  rep(i,n-1){
    int a,b;
    cin>>a>>b;
    tree[a].pb({b,i});
    tree[b].pb({a,i});
  }

  build(0, -1);

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

  int q;
  cin>>q;
  rep(_,q){
    string s;
    cin>>s;
    if(s[0]=='g'){
      int l,r;
      cin>>l>>r;
      cout << st.query(bg[l]+1, bg[r]+1) << "\n";
    } else {
      int p,a,b,c,d;
      cin>>p>>a>>b>>c>>d;
      st.update(id_in[p], mat(a,b,c,d));
      st.update(id_out[p], mat(a,b,c,d).inverse());
    }
  }

  return 0;
}
0