오일러 투어(Euler Tour) 응용 feat. 2820 자동차 공장

오일러 투어(Euler Tour) 응용 feat. 2820 자동차 공장

#pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; using ll = long long; using pii = pair; int n, m; int num; int ar[500001]; int conv[500001]; int wage_conv[500001]; vector tree[500001]; pii tour[500001]; inline int mid(int s, int e) { return s + (e - s) / 2; } template class lazy_segtree { private: vector tree, lazy; public: lazy_segtree(int n): tree(n * 4), lazy(n * 4) { init(1, 1, n); } T init(int node, int start, int end) { if (start == end) return tree[node] = wage_conv[end]; int m = mid(start, end); return tree[node] = init(node * 2, start, m) + init(node * 2 + 1, m + 1, end); } void propa(int node, int start, int end) { if (!lazy[node]) return; tree[node] += (end - start + 1) * lazy[node]; if (start != end) { lazy[node * 2] += lazy[node]; lazy[node * 2 + 1] += lazy[node]; } lazy[node] = 0; } void add(int node, int start, int end, int l, int r, T val) { propa(node, start, end); if (start > r || end < l) return; if (l <= start && end <= r) { lazy[node] += val; propa(node, start, end); return; } int m = mid(start, end); add(node * 2, start, m, l, r, val); add(node * 2 + 1, m + 1, end, l, r, val); tree[node] = tree[node * 2] + tree[node * 2 + 1]; } T sum(int node, int start, int end, int l, int r) { propa(node, start, end); if (start > r || end < l) return 0; if (l <= start && end <= r) return tree[node]; int m = mid(start, end); return sum(node * 2, start, m, l, r) + sum(node * 2 + 1, m + 1, end, l, r); } }; void dfs(int node) { conv[node] = tour[node].first = ++num; for (int i: tree[node]) dfs(i); tour[node].second = num; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; ++i) { cin >> ar[i]; if (i == 1) continue; int par; cin >> par; tree[par].push_back(i); } dfs(1); for (int i = 1; i <= n; ++i) wage_conv[conv[i]] = ar[i]; lazy_segtree segt(n); while (m--) { char inst; cin >> inst; if (inst == 'u') { int x; cin >> x; cout << segt.sum(1, 1, n, conv[x], conv[x]) << '

'; } else { int x, y; cin >> x >> y; if (tour[x].first == tour[x].second) continue; segt.add(1, 1, n, tour[x].first + 1, tour[x].second, y); } } }

from http://nicotina04.tistory.com/161 by ccl(A) rewrite - 2021-08-29 03:00:36