結果
問題 | No.1038 TreeAddQuery |
ユーザー |
|
提出日時 | 2022-04-01 17:55:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 9,316 bytes |
コンパイル時間 | 669 ms |
コンパイル使用メモリ | 86,000 KB |
最終ジャッジ日時 | 2025-01-28 13:37:41 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In member function ‘T suisen::RangeContourOperationQueryOnTree<T, F, mapping, composition, id>::get(int)’: main.cpp:176:52: error: ‘exchange’ is not a member of ‘std’ 176 | res = composition(res, _nodes[std::exchange(v, _par[v])][info.child_index].get(info.segtree_index)); | ^~~~~~~~ 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:188:29: error: ‘exchange’ is not a member of ‘std’ 188 | _nodes[std::exchange(v, _par[v])][info.child_index ^ 1].apply(ql, qr, val); | ^~~~~~~~ main.cpp:188:29: 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:238:12: required from here main.cpp:143:34: 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>::Node, 2> >, std::array<suisen::RangeContourOperationQueryOnTree<long long int, long long int, mapping, composition, id>::Node, 2> >::value_type’ {aka ‘std::array<suisen::RangeContourOperationQueryOnTree<long long int, long long int, mapping, composition, id>::Node, 2>’} and ‘int’) 143 | _nodes[c][0] = Node{ _g, _removed, ch[u], 0, _info }; | ~~~~~~
ソースコード
#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), _info(_n), _nodes(_n), _dat(dat) {_par.reserve(2 * _n);for (int i = 0; i < _n; ++i) _info[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 AuxData {int segtree_index;int8_t child_index;int dist;};struct Node {std::vector<int> _sep;segtree_type _seq;Node() {}Node(const std::vector<std::vector<int>>& g, const std::vector<int8_t>& removed, const std::vector<int> &roots, const bool child_index,std::vector<std::vector<AuxData>>& info) {_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;info[u].push_back({ cnt++, child_index, du });for (int v : g[u]) if (v != pu and not removed[v]) 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;_nodes[c][0] = Node{ _g, _removed, ch[u], 0, _info };_nodes[c][1] = Node{ _g, _removed, ch[v], 1, _info };} 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;_nodes.emplace_back();_nodes[new_node][0] = Node{ _g, _removed, ch[u], 0, _info };_nodes[new_node][1] = Node{ _g, _removed, ch[v], 1, _info };ch.push_back(merge(std::move(ch[u]), std::move(ch[v])));ch[u].clear(), ch[u].shrink_to_fit();ch[v].clear(), ch[v].shrink_to_fit();pq.push(new_node);}}if (pq.size()) {int u = pq.top();pq.pop();_par[ctr[u]] = c;_nodes[c][0] = Node{ _g, _removed, ch[u], 0, _info };}_removed[c] = false;return c;};rec(rec, 0, _n);}T get(int u) {F res = id();int v = _par[u];for (const auto &info : _info[u]) {res = composition(res, _nodes[std::exchange(v, _par[v])][info.child_index].get(info.segtree_index));}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]);_nodes[u][0].apply(dl - 1, dr - 1, val);_nodes[u][1].apply(dl - 1, dr - 1, val);int v = _par[u];for (const auto &info : _info[u]) {int ql = dl - info.dist - 2, qr = dr - info.dist - 2;if (v < _n and ql <= -1 and -1 < qr) _dat[v] = mapping(val, _dat[v]);_nodes[std::exchange(v, _par[v])][info.child_index ^ 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<AuxData>> _info;std::vector<std::array<Node, 2>> _nodes;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;}#include <chrono>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);}std::vector<std::tuple<int, int, int>> qs(q);for (auto &[x, y, z] : qs) {std::cin >> x >> y >> z;--x, ++y;}std::vector<long long> ans(q);auto t1 = std::chrono::system_clock::now();g.build();auto t2 = std::chrono::system_clock::now();for (int i = 0; i < q; ++i) {const auto &[x, y, z] = qs[i];ans[i] = g.get(x);g.apply(x, 0, y, z);}auto t3 = std::chrono::system_clock::now();for (auto &e : ans) std::cout << e << '\n';auto build_time_ms = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();auto query_time_ms = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count();std::cerr << "build : " << build_time_ms << " ms" << std::endl;std::cerr << "query : " << query_time_ms << " ms" << std::endl;return 0;}