Programming Problems and Competitions :: HackerRank
問題は登録しないと見れなかったりするのかな?
問題概要
N頂点のツリーが与えられる、頂点はそれぞれf(x) = ax+bという形で表せる関数を持っている
二種類のクエリが飛んでくる
クエリ1.変更
u, v, a, bが与えられるので、u-vパス間の(両端含む)頂点の持つ関数をすべてf(x) = ax+bに変更する
クエリ2.取得
u, v, xが与えられるので、u-vパス間の(両端含む)頂点をp1, p2, p3, ..., pkとして
f_k( f_k-1( f_k-2( ... f2( f1(x)) ...)))
を求める、ただしf1,f2...fkはp1,p2, ...pkの持つ関数
値は大きくなるのでMod1e9+7で求める
解法
これは木のパスに関する問題ですね。
木のパス…?これはもしかしてLC Tree待ったなしじゃない…?
頂点の値の設定取得遅延評価,evert, linkを実装すると解ける
212行で思ったほどは多くならなかった
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <queue> #include <set> #include <tuple> #include <cassert> using namespace std; typedef long long ll; typedef pair<ll, ll> P; const ll MD = 1e9+7; static const P e = P(1, 0); static const P DEF = P(-1, 0); P mulp(P l, P r) { P res; res.first = (l.first*r.first) % MD; res.second = ((l.first*r.second)+l.second) % MD; return res; } P powp(P p, int k) { P r = e; while (k) { if (k & 1) { r = mulp(r, p); } p = mulp(p, p); k >>= 1; } return r; } typedef pair<ll, ll> P; struct LCTree { typedef P D; struct Node; typedef Node* NP; static Node last_d; static NP last; struct Node { NP p, l, r; int sz; bool rev; D v, fsm, bsm, lz; Node(D v) :p(NULL), l(last), r(last), sz(1), rev(false), v(v), fsm(v), bsm(v), lz(DEF) {} Node(NP l, NP r) : l(l), r(r), sz(0), v(e), fsm(e), bsm(e), lz(DEF) {} inline int pos() { if (p && p->l == this) return -1; if (p && p->r == this) return 1; return 0; } void rot() { NP q = p, qq = q->p; int qp = q->pos(); if (q->l == this) { q->l = r; r->p = q; r = q; q->p = this; } else { q->r = l; l->p = q; l = q; q->p = this; } q->update(); update(); p = qq; if (!qp) return; if (qp == -1) { qq->l = this; } else { qq->r = this; } qq->update(); } void splay() { supush(); while (pos()) { int u = pos()*p->pos(); if (!u) { rot(); } else if (u == 1) { p->rot(); rot(); } else { rot(); rot(); } } } void expose() { assert(this != last); NP u = this; do { u->splay(); } while ((u = u->p)); u = last; u->p = this; do { u->p->r = u; u->p->update(); u = u->p; } while (u->p); splay(); } void push() { assert(this != last); if (rev) { swap(l, r); if (l->sz) { l->revdata(); } if (r->sz) { r->revdata(); } rev = false; } if (lz != DEF) { if (l->sz) { l->lzdata(lz); } if (r->sz) { r->lzdata(lz); } lz = DEF; } } void supush() { if (pos()) { p->supush(); } push(); } void revdata() { rev ^= true; swap(fsm, bsm); } void lzdata(D d) { v = d; fsm = bsm = powp(d, sz); lz = d; } NP update() { if (this == last) return this; sz = 1+l->sz+r->sz; fsm = mulp(l->fsm, mulp(v, r->fsm)); bsm = mulp(r->bsm, mulp(v, l->bsm)); return this; } } *n; LCTree() : n(last) {} LCTree(NP n) : n(n) {} LCTree(D d) : n(new Node(d)) {} int sz() { return n->sz; } void evert() { n->expose(); n->revdata(); } void link(LCTree r) { n->expose(); r.n->expose(); assert(n->l == last); n->p = r.n; } void set(D x) { n->expose(); n->lzdata(x); } D get() { n->expose(); return n->fsm; } }; LCTree::Node LCTree::last_d = LCTree::Node((NP)NULL, NULL); LCTree::NP LCTree::last = &last_d; const int MN = 50200; ll a[MN]; LCTree tr[MN]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { int a, b; scanf("%d %d", &a, &b); tr[i] = LCTree(P(a, b)); } for (int i = 0; i < n-1; i++) { int a, b; scanf("%d %d", &a, &b); a--; b--; tr[a].evert(); tr[a].link(tr[b]); } int q; cin >> q; for (int i = 0; i < q; i++) { int t, u, v; scanf("%d %d %d", &t, &u, &v); u--; v--; if (t == 1) { int a, b; scanf("%d %d", &a, &b); tr[u].evert(); tr[v].set(P(a, b)); } else { ll x; scanf("%lld", &x); tr[v].evert(); P p = tr[u].get(); printf("%lld\n", (x*p.first % MD + p.second) % MD); } } return 0; }