結果
問題 | No.1038 TreeAddQuery |
ユーザー |
|
提出日時 | 2022-03-31 22:05:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,561 bytes |
コンパイル時間 | 673 ms |
コンパイル使用メモリ | 76,804 KB |
最終ジャッジ日時 | 2025-01-28 13:32:25 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In member function ‘T RangeContourOperationQueryOnTree<T, op, e>::get(int)’: main.cpp:175:37: error: ‘exchange’ is not a member of ‘std’ 175 | res = op(res, _sub[std::exchange(v, _par[v])][_idx[u][i]].get(_pos[u][i])); | ^~~~~~~~ main.cpp:7:1: note: ‘std::exchange’ is defined in header ‘<utility>’; did you forget to ‘#include <utility>’? 6 | #include <queue> +++ |+#include <utility> 7 | #include <tuple> main.cpp: In member function ‘void RangeContourOperationQueryOnTree<T, op, e>::apply(int, int, int, const T&)’: main.cpp:187:23: error: ‘exchange’ is not a member of ‘std’ 187 | _sub[std::exchange(v, _par[v])][_idx[u][i] ^ 1].apply(ql, qr, val); | ^~~~~~~~ main.cpp:187:23: note: ‘std::exchange’ is defined in header ‘<utility>’; did you forget to ‘#include <utility>’? main.cpp: In instantiation of ‘void RangeContourOperationQueryOnTree<T, op, e>::build() [with T = long long int; T (* op)(T, T) = op; T (* e)() = e]’: main.cpp:224:12: required from here main.cpp:141:28: error: no match for ‘operator[]’ (operand types are ‘__gnu_cxx::__alloc_traits<std::allocator<std::array<RangeContourOperationQueryOnTree<long long int, op, e>::SubTree, 2> >, std::array<RangeContourOperationQueryOnTree<long long int, op, e>::SubTree, 2> >::value_type’ {aka ‘std::array<RangeContourOperationQueryOnTree<long long int, op, e>::SubTree, 2>’} and ‘int’) 141 | _sub[c][0] = SubTree{ _g, _removed, u, 0, _idx, _pos, _dist }; | ~~~~~~~^ main.cpp:142:28: error: no match for ‘operator[]’ (operand types are ‘__gnu_cxx::__alloc_traits<std::allocator<std::array<RangeContourOperationQueryOnTree<long long int, op, e>::SubTree, 2> >, std::array<RangeContourOperationQueryOnTree<long long int, op, e>::SubTree, 2> >::value_type’ {aka ‘std::array<RangeContourOperation
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/1038"#include <iostream>#include <deque>#include <map>#include <queue>#include <tuple>template <typename T, T(*op)(T, T), T(*e)()>struct CommutativeDualSegmentTree {CommutativeDualSegmentTree() {}CommutativeDualSegmentTree(int n) : _n(n) , _laz(2 * _n, e()) {}void apply(int l, int r, const T &f) {for (l += _n, r += _n; l < r; l >>= 1, r >>= 1) {if (l & 1) _laz[l] = op(_laz[l], f), ++l;if (r & 1) --r, _laz[r] = op(_laz[r], f);}}T get(int i) {T res = e();for (i += _n; i; i >>= 1) res = op(res, _laz[i]);return res;}private:int _n;std::vector<T> _laz;};template <typename T, T(*op)(T, T), T(*e)()>struct RangeContourOperationQueryOnTree {RangeContourOperationQueryOnTree() {}RangeContourOperationQueryOnTree(int n) : _n(n), _g(_n), _par(_n, -1), _removed(_n, false), _pos(_n), _idx(_n), _dist(_n), _sub(_n), _dat(_n, e()) {}using segtree_type = CommutativeDualSegmentTree<T, op, e>;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 int root,const bool is_right_child,std::vector<std::vector<int8_t>>& idx,std::vector<std::vector<int>>& pos,std::vector<std::vector<int>>& dist) {const int siz = dist.size();auto is_dummy_vertex = [&](int u) { return u >= siz; };_sep.push_back(0);std::deque<std::tuple<int, int, int>> dq{ { root, -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;}bool b = is_dummy_vertex(u);if (not b) {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;if (b) {dq.emplace_front(v, u, du);} else {dq.emplace_back(v, u, du + 1);}}}_sep.push_back(cnt);_seq = segtree_type(cnt);}T get(int i) {return _seq.get(i);}void apply(int dl, int dr, const T &val) {if (dl < 0) dl = 0;if (dr >= int(_sep.size())) dr = int(_sep.size()) - 1;if (dl >= dr) return;int ql = _sep[dl], qr = _sep[dr];_seq.apply(ql, qr, val);}};void add_edge(int u, int v) {_g[u].push_back(v);_g[v].push_back(u);}void build() {std::vector<int> sub(_n, 0);std::vector<int> ctr(_n, -1);auto rec = [&](auto rec, int r, int siz) -> int {int c = -1;auto get_centroid = [&](auto get_centroid, int u, int p) -> void {sub[u] = 1;for (int v : _g[u]) {if (v == p or _removed[v]) continue;get_centroid(get_centroid, v, u);if (v == c) {sub[u] = siz - sub[c];break;}sub[u] += sub[v];}if (c < 0 and sub[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[v];ctr[v] = rec(rec, v, comp_size);sub[v] = comp_size;}auto comp = [&](int i, int j) { return sub[i] > sub[j]; };std::priority_queue<int, std::vector<int>, decltype(comp)> pq{ comp };for (int v : _g[c]) {if (_removed[v]) continue;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, u, 0, _idx, _pos, _dist };_sub[c][1] = SubTree{ _g, _removed, v, 1, _idx, _pos, _dist };} else {int new_node = sub.size();sub.push_back(sub[u] + sub[v]);ctr.push_back(new_node);_par.push_back(-1);_par[ctr[u]] = _par[ctr[v]] = new_node;pq.push(new_node);_removed.push_back(false);_g.emplace_back();_g[new_node].push_back(u);_g[new_node].push_back(v);_sub.emplace_back();_sub[new_node][0] = SubTree{ _g, _removed, u, 0, _idx, _pos, _dist };_sub[new_node][1] = SubTree{ _g, _removed, v, 1, _idx, _pos, _dist };}}if (pq.size()) {int u = pq.top();pq.pop();_par[ctr[u]] = c;_sub[c][0] = SubTree{ _g, _removed, u, 0, _idx, _pos, _dist };}_removed[c] = false;return c;};rec(rec, 0, _n);}T get(int u) {T res = _dat[u];int h = _pos[u].size();for (int i = 0, v = _par[u]; i < h; ++i) {res = op(res, _sub[std::exchange(v, _par[v])][_idx[u][i]].get(_pos[u][i]));}return res;}void apply(int u, int dl, int dr, const T &val) {if (dl <= 0 and 0 < dr) _dat[u] = op(_dat[u], val);_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] = op(_dat[v], val);_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;};long long op(long long x, long long y) {return x + y;}long long e() {return 0;}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, q;std::cin >> n >> q;RangeContourOperationQueryOnTree<long long, op, e> g(n);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;}