結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
 suisen
|
| 提出日時 | 2022-04-01 17:09:32 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 9,906 bytes |
| コンパイル時間 | 729 ms |
| コンパイル使用メモリ | 89,924 KB |
| 最終ジャッジ日時 | 2024-11-15 02:15:06 |
| 合計ジャッジ時間 | 1,711 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In member function 'T suisen::RangeContourOperationQueryOnTree<T, F, mapping, composition, id>::get(int)':
main.cpp:190:50: error: 'exchange' is not a member of 'std'
190 | res = composition(res, _sub[std::exchange(v, _par[v])][_idx[u][i]].get(_pos[u][i]));
| ^~~~~~~~
main.cpp: In member function 'void suisen::RangeContourOperationQueryOnTree<T, F, mapping, composition, id>::apply(int, int, int, const F&)':
main.cpp:202:27: error: 'exchange' is not a member of 'std'
202 | _sub[std::exchange(v, _par[v])][_idx[u][i] ^ 1].apply(ql, qr, val);
| ^~~~~~~~
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:254: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 };
| ~~~~~~~^
main.cpp:158: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'
ソースコード
#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])));
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;
_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 suisen
long 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;
}