結果
問題 | No.1038 TreeAddQuery |
ユーザー |
|
提出日時 | 2022-04-01 16:58:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 9,107 bytes |
コンパイル時間 | 662 ms |
コンパイル使用メモリ | 77,988 KB |
最終ジャッジ日時 | 2025-01-28 13:36:48 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In member function ‘T suisen::RangeContourOperationQueryOnTree<T, F, mapping, composition, id>::get(int)’: main.cpp:188:50: error: ‘exchange’ is not a member of ‘std’ 188 | res = composition(res, _sub[std::exchange(v, _par[v])][_idx[u][i]].get(_pos[u][i])); | ^~~~~~~~ main.cpp:9:1: note: ‘std::exchange’ is defined in header ‘<utility>’; did you forget to ‘#include <utility>’? 8 | #include <queue> +++ |+#include <utility> 9 | #include <tuple> main.cpp: In member function ‘void suisen::RangeContourOperationQueryOnTree<T, F, mapping, composition, id>::apply(int, int, int, const F&)’: main.cpp:200:27: error: ‘exchange’ is not a member of ‘std’ 200 | _sub[std::exchange(v, _par[v])][_idx[u][i] ^ 1].apply(ql, qr, val); | ^~~~~~~~ main.cpp:200:27: note: ‘std::exchange’ is defined in header ‘<utility>’; did you forget to ‘#include <utility>’? main.cpp: In instantiation of ‘void suisen::RangeContourOperationQueryOnTree<T, F, mapping, composition, id>::build() [with T = long long int; F = long long int; T (* mapping)(F, T) = mapping; F (* composition)(F, F) = composition; F (* id)() = id]’: main.cpp:241:12: required from here main.cpp:157:32: error: no match for ‘operator[]’ (operand types are ‘__gnu_cxx::__alloc_traits<std::allocator<std::array<suisen::RangeContourOperationQueryOnTree<long long int, long long int, mapping, composition, id>::SubTree, 2> >, std::array<suisen::RangeContourOperationQueryOnTree<long long int, long long int, mapping, composition, id>::SubTree, 2> >::value_type’ {aka ‘std::array<suisen::RangeContourOperationQueryOnTree<long long int, long long int, mapping, composition, id>::SubTree, 2>’} and ‘int’) 157 | _sub[c][0] = SubTree{ _g, _removed, ch[u], 0, _idx, _pos, _dist }; | ~~~~~~~^ mai
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/1038"#include <iostream>#include <cstdint>#include <deque>#include <map>#include <queue>#include <tuple>namespace suisen {template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>struct RangeContourOperationQueryOnTree {RangeContourOperationQueryOnTree() {}RangeContourOperationQueryOnTree(int n, const T &fill_value) : RangeContourOperationQueryOnTree(std::vector<T>(n, fill_value)) {}RangeContourOperationQueryOnTree(const std::vector<T> &dat) : _n(dat.size()), _g(_n), _par(_n, -1), _removed(_n, false), _pos(_n), _idx(_n),_dist(_n), _sub(_n), _dat(dat) {_par.reserve(2 * _n);for (int i = 0; i < _n; ++i) {_pos[i].reserve(30);_idx[i].reserve(30);_dist[i].reserve(30);}}struct CommutativeDualSegmentTree {CommutativeDualSegmentTree() {}CommutativeDualSegmentTree(int n) : _n(n), _laz(2 * _n, id()) {}void apply(int l, int r, const F& f) {for (l += _n, r += _n; l < r; l >>= 1, r >>= 1) {if (l & 1) _laz[l] = composition(_laz[l], f), ++l;if (r & 1) --r, _laz[r] = composition(_laz[r], f);}}F get(int i) {F res = id();for (i += _n; i; i >>= 1) res = composition(res, _laz[i]);return res;}private:int _n;std::vector<F> _laz;};using segtree_type = CommutativeDualSegmentTree;struct SubTree {std::vector<int> _sep;segtree_type _seq;SubTree() {}SubTree(const std::vector<std::vector<int>>& g,const std::vector<int8_t>& removed,const std::vector<int> &roots,const bool is_right_child,std::vector<std::vector<int8_t>>& idx,std::vector<std::vector<int>>& pos,std::vector<std::vector<int>>& dist) {_sep.push_back(0);std::deque<std::tuple<int, int, int>> dq;for (int r : roots) dq.emplace_back(r, -1, 0);int pre_dist = 0, cnt = 0;while (dq.size()) {const auto [u, pu, du] = dq.front();dq.pop_front();if (du == pre_dist + 1) {_sep.push_back(cnt);pre_dist = du;}pos[u].push_back(cnt++);idx[u].push_back(is_right_child);dist[u].push_back(du);for (int v : g[u]) {if (v == pu or removed[v]) continue;dq.emplace_back(v, u, du + 1);}}_sep.push_back(cnt);_seq = segtree_type(cnt);}F get(int i) {return _seq.get(i);}void apply(int dl, int dr, const F& val) {dl = std::max(dl, 0);dr = std::min(dr, int(_sep.size()) - 1);if (dl < dr) _seq.apply(_sep[dl], _sep[dr], val);}};void add_edge(int u, int v) {_g[u].push_back(v);_g[v].push_back(u);}void build() {std::vector<int> sub_size(_n, 0);std::vector<int> ctr(_n, -1);sub_size.reserve(2 * _n);ctr.reserve(2 * _n);std::vector<std::vector<int>> ch(_n);ch.reserve(2 * _n);auto merge = [&](std::vector<int> &&l, std::vector<int> &&r) -> std::vector<int>&& {if (l.size() < r.size()) {for (int e : l) r.push_back(e);return std::move(r);} else {for (int e : r) l.push_back(e);return std::move(l);}};auto rec = [&](auto rec, int r, int siz) -> int {int c = -1;auto get_centroid = [&](auto get_centroid, int u, int p) -> void {sub_size[u] = 1;for (int v : _g[u]) {if (v == p or _removed[v]) continue;get_centroid(get_centroid, v, u);if (v == c) {sub_size[u] = siz - sub_size[c];break;}sub_size[u] += sub_size[v];}if (c < 0 and sub_size[u] * 2 > siz) c = u;};get_centroid(get_centroid, r, -1);_removed[c] = true;for (int v : _g[c]) {if (_removed[v]) continue;const int comp_size = sub_size[v];ctr[v] = rec(rec, v, comp_size);sub_size[v] = comp_size;}auto comp = [&](int i, int j) { return sub_size[i] > sub_size[j]; };std::priority_queue<int, std::vector<int>, decltype(comp)> pq{ comp };for (int v : _g[c]) {if (_removed[v]) continue;ch[v] = { v };pq.push(v);}while (pq.size() >= 2) {int u = pq.top();pq.pop();int v = pq.top();pq.pop();if (pq.empty()) {_par[ctr[u]] = _par[ctr[v]] = c;_sub[c][0] = SubTree{ _g, _removed, ch[u], 0, _idx, _pos, _dist };_sub[c][1] = SubTree{ _g, _removed, ch[v], 1, _idx, _pos, _dist };} else {int new_node = sub_size.size();sub_size.push_back(sub_size[u] + sub_size[v]);ctr.push_back(new_node);_par.push_back(-1);_par[ctr[u]] = _par[ctr[v]] = new_node;_sub.emplace_back();_sub[new_node][0] = SubTree{ _g, _removed, ch[u], 0, _idx, _pos, _dist };_sub[new_node][1] = SubTree{ _g, _removed, ch[v], 1, _idx, _pos, _dist };ch.push_back(merge(std::move(ch[u]), std::move(ch[v])));pq.push(new_node);}}if (pq.size()) {int u = pq.top();pq.pop();_par[ctr[u]] = c;_sub[c][0] = SubTree{ _g, _removed, ch[u], 0, _idx, _pos, _dist };}_removed[c] = false;return c;};rec(rec, 0, _n);}T get(int u) {F res = id();int h = _pos[u].size();for (int i = 0, v = _par[u]; i < h; ++i) {res = composition(res, _sub[std::exchange(v, _par[v])][_idx[u][i]].get(_pos[u][i]));}return mapping(res, _dat[u]);}void apply(int u, int dl, int dr, const F& val) {if (dl <= 0 and 0 < dr) _dat[u] = mapping(val, _dat[u]);_sub[u][0].apply(dl - 1, dr - 1, val);_sub[u][1].apply(dl - 1, dr - 1, val);int h = _pos[u].size();for (int i = 0, v = _par[u]; i < h; ++i) {int ql = dl - _dist[u][i] - 2, qr = dr - _dist[u][i] - 2;if (v < _n and ql <= -1 and -1 < qr) _dat[v] = mapping(val, _dat[v]);_sub[std::exchange(v, _par[v])][_idx[u][i] ^ 1].apply(ql, qr, val);}}private:int _n;std::vector<std::vector<int>> _g;std::vector<int> _par;std::vector<int8_t> _removed;std::vector<std::vector<int>> _pos;std::vector<std::vector<int8_t>> _idx;std::vector<std::vector<int>> _dist;std::vector<std::array<SubTree, 2>> _sub;std::vector<T> _dat;};} // namespace suisenlong long mapping(long long f, long long x) {return f + x;}long long composition(long long x, long long y) {return x + y;}long long id() {return 0;}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, q;std::cin >> n >> q;suisen::RangeContourOperationQueryOnTree<long long, long long, mapping, composition, id> g(n, 0LL);for (int i = 0; i < n - 1; ++i) {int u, v;std::cin >> u >> v;--u, --v;g.add_edge(u, v);}g.build();for (int i = 0; i < q; ++i) {int x, y, z;std::cin >> x >> y >> z;--x, ++y;std::cout << g.get(x) << '\n';g.apply(x, 0, y, z);}return 0;}