結果
問題 | No.900 aδδitivee |
ユーザー |
|
提出日時 | 2019-10-04 23:08:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 296 ms / 2,000 ms |
コード長 | 4,502 bytes |
コンパイル時間 | 1,566 ms |
コンパイル使用メモリ | 181,192 KB |
実行使用メモリ | 28,240 KB |
最終ジャッジ日時 | 2024-10-03 08:33:24 |
合計ジャッジ時間 | 9,342 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;//SegmentTree(n, f, g, h, M1, OM0):= サイズ n の初期化。ここで f は2つの区間の要素をマージする二項演算, g は要素と作用素をマージする二項演算(第三引数は対応する区間の長さ), h は作用素同士をマージする二項演算, M1 はモノイドの単位元, OM0は 作用素の単位元である。//update(a, b, x) := 区間 [a,b) に作用素 xを適用する。template< typename Monoid, typename OperatorMonoid = Monoid >struct LazySegmentTree {using F = function< Monoid(Monoid, Monoid) >;using G = function< Monoid(Monoid, OperatorMonoid, int) >;using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;int sz;vector< Monoid > data;vector< OperatorMonoid > lazy;const F f;const G g;const H h;const Monoid M1;const OperatorMonoid OM0;LazySegmentTree(int n, const F f, const G g, const H h,const Monoid &M1, const OperatorMonoid OM0): f(f), g(g), h(h), M1(M1), OM0(OM0) {sz = 1;while(sz < n) sz <<= 1;data.assign(2 * sz, M1);lazy.assign(2 * sz, OM0);}void set(int k, const Monoid &x) {data[k + sz] = x;}void build() {for(int k = sz - 1; k > 0; k--) {data[k] = f(data[2 * k + 0], data[2 * k + 1]);}}void propagate(int k, int len) {if(lazy[k] != OM0) {if(k < sz) {lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);}data[k] = g(data[k], lazy[k], len);lazy[k] = OM0;}}Monoid update(int a, int b, const OperatorMonoid &x, int k, int l, int r) {propagate(k, r - l);if(r <= a || b <= l) {return data[k];} else if(a <= l && r <= b) {lazy[k] = h(lazy[k], x);propagate(k, r - l);return data[k];} else {return data[k] = f(update(a, b, x, 2 * k + 0, l, (l + r) >> 1),update(a, b, x, 2 * k + 1, (l + r) >> 1, r));}}Monoid update(int a, int b, const OperatorMonoid &x) {return update(a, b, x, 1, 0, sz);}Monoid query(int a, int b, int k, int l, int r) {propagate(k, r - l);if(r <= a || b <= l) {return M1;} else if(a <= l && r <= b) {return data[k];} else {return f(query(a, b, 2 * k + 0, l, (l + r) >> 1),query(a, b, 2 * k + 1, (l + r) >> 1, r));}}Monoid query(int a, int b) {return query(a, b, 1, 0, sz);}Monoid operator[](const int &k) {return query(k, k + 1);}};//SegmentTree(n, f, g, h, M1, OM0):= サイズ n の初期化。ここで f は2つの区間の要素をマージする二項演算, g は要素と作用素をマージする二項演算(第三引数は対応する区間の長さ), h は作用素同士をマージする二項演算, M1 はモノイドの単位元, OM0は 作用素の単位元である。#define N 200010#define int long longstruct LazySegmentTree<pair<int, int>, int> segtree(N,[](pair<int, int> a, pair<int, int> b){ return make_pair(a.first + b.first, a.second + b.second);},[](pair<int, int> a, int b, int z){ return make_pair(a.first + a.second * b, a.second);},[](int a, int b){ return a + b; },make_pair(0, 0), 0);int ds[N];int us[N];vector<pair<int, int>> graph[100010];void dfs(int v, int p, int &k){for(auto u : graph[v]){if(u.first == p) continue;ds[u.first] = k++;segtree.set(ds[u.first], {u.second, 1});dfs(u.first, v, k);us[u.first] = k++;segtree.set(us[u.first], {-u.second, -1});}}signed main(){int n;cin >> n;for(int i = 0;i < n-1;i++){int u, v, w;cin >> u >> v >> w;graph[u].push_back({v, w});}int num = 0;ds[0] = -1;dfs(0, -1, num);us[0] = num;segtree.build();int q; cin >> q;while(q--){int query, a, x;cin >> query;if(query == 1){cin >> a >> x;segtree.update(ds[a]+1, us[a], x);}else{cin >> a;cout << segtree.query(0, ds[a]+1).first << endl;}}return 0;};