結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
 suisen
|
| 提出日時 | 2022-08-06 00:14:18 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 9,687 bytes |
| コンパイル時間 | 1,169 ms |
| コンパイル使用メモリ | 114,088 KB |
| 最終ジャッジ日時 | 2024-11-15 02:26:47 |
| 合計ジャッジ時間 | 2,446 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In member function 'suisen::PointGetRangeContourOperate<T, F, mapping, composition, id>::value_type suisen::PointGetRangeContourOperate<T, F, mapping, composition, id>::get(int) const':
main.cpp:155:95: error: 'exchange' is not a member of 'std'
155 | for (auto it = _info[u].begin(); it != it_end; ++it) res = mapping(_subtrees[std::exchange(v, _par[v])][it->child_index].get(it->dep), res);
| ^~~~~~~~
main.cpp: In member function 'void suisen::PointGetRangeContourOperate<T, F, mapping, composition, id>::apply(int, int, int, const operator_type&)':
main.cpp:174:32: error: 'exchange' is not a member of 'std'
174 | _subtrees[std::exchange(v, _par[v])][it->child_index ^ 1].apply(ql - 1, qr - 1, f);
| ^~~~~~~~
main.cpp: In instantiation of 'struct suisen::PointGetRangeContourOperate<long long int, long long int, mapping, composition, id>::TreeNode':
main.cpp:54:23: required from 'void suisen::PointGetRangeContourOperate<T, F, mapping, composition, id>::add_edge(int, int) [with T = long long int; F = long long int; T (* mapping)(F, T) = mapping; F (* composition)(F, F) = composition; F (* id)() = id]'
main.cpp:233:19: required from here
main.cpp:47:56: error: invalid use of incomplete type 'struct std::array<suisen::PointGetRangeContourOperate<long long int, long long int, mapping, composition, id>::AuxInfo, 30>'
47 | typename std::array<AuxInfo, 30>::iterator info_it;
| ^~~~~~~
In file included from main.cpp:11:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/tuple:1595:45: note: declaration of 'struct std::array<suisen::PointGetRangeContourOperate<long long int, long long int, mapping, composition, id>::AuxInfo, 30>'
1595 | template<typename _Tp, size_t _Nm> struct array;
|
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/1038"
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <deque>
#include <queue>
#include <random>
#include <tuple>
namespace suisen {
template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
struct PointGetRangeContourOperate {
using value_type = T;
using operator_type = F;
private:
struct InternalCommutativeDualSegmentTree {
InternalCommutativeDualSegmentTree(int n = 0) : _n(n), _laz(2 * _n, id()) {}
void apply(int l, int r, const operator_type& f) {
l = std::max(0, l), r = std::min(r, _n);
for (l += _n, r += _n; l < r; l >>= 1, r >>= 1) {
if (l & 1) _laz[l] = composition(f, _laz[l]), ++l;
if (r & 1) --r, _laz[r] = composition(f, _laz[r]);
}
}
operator_type get(int i) const {
operator_type res = id();
for (i += _n; i; i >>= 1) res = composition(res, _laz[i]);
return res;
}
private:
int _n;
std::vector<operator_type> _laz;
};
using sequence_type = InternalCommutativeDualSegmentTree;
struct AuxInfo {
int8_t child_index;
int dep;
};
struct TreeNode {
std::vector<int> adj;
typename std::array<AuxInfo, 30>::iterator info_it;
};
public:
PointGetRangeContourOperate(int n = 0, const value_type& fill_v = {}) : PointGetRangeContourOperate(std::vector<value_type>(n, fill_v)) {}
PointGetRangeContourOperate(const std::vector<value_type>& a) : _n(a.size()), _dat(a), _nodes(_n), _par(2 * _n, -1), _info(_n), _subtrees(2 * _n), _ord(_n, -1) {}
void add_edge(int u, int v) {
_nodes[u].adj.push_back(v);
_nodes[v].adj.push_back(u);
}
// O(NlogN)
void build() {
std::mt19937 rng{ std::random_device{}() };
reorder(std::uniform_int_distribution<int>{ 0, _n - 1 }(rng));
int new_node = _n;
std::vector<int> sub_size(2 * _n, 0);
std::vector<int> ctr(2 * _n, -1);
std::vector<int> head(2 * _n), tail(2 * _n), link(2 * _n);
for (int i = 0; i < _n; ++i) head[i] = tail[i] = i;
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 : _nodes[u].adj) if (v != p) {
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);
for (int v : _nodes[c].adj) {
const int comp_size = sub_size[v];
_nodes[v].adj.erase(std::find(_nodes[v].adj.begin(), _nodes[v].adj.end(), c));
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 : _nodes[c].adj) {
link[v] = -1;
pq.push(v);
}
auto build_sequence = [&, this](const int root_head, const bool child_index) {
std::deque<std::pair<int, int>> dq;
for (int root = root_head; root >= 0; root = link[root]) dq.emplace_back(root, -1);
int dep = 0, nxt = -1;
while (dq.size()) {
const auto [u, pu] = dq.front();
dq.pop_front();
if (u == nxt) ++dep, nxt = -1;
auto& node = _nodes[u];
*node.info_it++ = { child_index, dep };
for (int v : node.adj) if (v != pu) {
dq.emplace_back(v, u);
if (nxt < 0) nxt = v;
}
}
return sequence_type(++dep);
};
while (pq.size() >= 2) {
const int u = pq.top(); pq.pop();
const int v = pq.top(); pq.pop();
if (pq.empty()) {
_par[ctr[u]] = _par[ctr[v]] = c;
_subtrees[c][0] = build_sequence(head[u], 0);
_subtrees[c][1] = build_sequence(head[v], 1);
break;
}
sub_size[new_node] = sub_size[u] + sub_size[v];
ctr[new_node] = new_node;
_par[ctr[u]] = _par[ctr[v]] = new_node;
_subtrees[new_node][0] = build_sequence(head[u], 0);
_subtrees[new_node][1] = build_sequence(head[v], 1);
head[new_node] = head[u], tail[new_node] = tail[v], link[tail[u]] = head[v];
pq.push(new_node);
++new_node;
}
if (pq.size()) {
int u = pq.top(); pq.pop();
_par[ctr[u]] = c;
_subtrees[c][0] = build_sequence(head[u], 0);
}
for (int v : _nodes[c].adj) _nodes[v].adj.push_back(c);
return c;
};
rec(rec, 0, _n);
_par.resize(new_node), _par.shrink_to_fit();
_subtrees.resize(new_node), _subtrees.shrink_to_fit();
}
// O((logN)^2)
value_type get(int u) const {
u = _ord[u];
value_type res = _dat[u];
int v = _par[u];
const auto it_end = _nodes[u].info_it;
for (auto it = _info[u].begin(); it != it_end; ++it) res = mapping(_subtrees[std::exchange(v, _par[v])][it->child_index].get(it->dep), res);
return res;
}
// O(1)
void apply(int u, const operator_type& f) {
u = _ord[u];
_dat[u] = mapping(f, _dat[u]);
}
// O((logN)^2)
void apply(int u, int dl, int dr, const operator_type& f) {
u = _ord[u];
if (dl <= 0 and 0 < dr) _dat[u] = mapping(f, _dat[u]);
_subtrees[u][0].apply(dl - 1, dr - 1, f);
_subtrees[u][1].apply(dl - 1, dr - 1, f);
int v = _par[u];
const auto it_end = _nodes[u].info_it;
for (auto it = _info[u].begin(); it != it_end; ++it) {
int ql = dl - it->dep - 1, qr = dr - it->dep - 1;
if (v < _n and ql <= 0 and 0 < qr) _dat[v] = mapping(f, _dat[v]);
_subtrees[std::exchange(v, _par[v])][it->child_index ^ 1].apply(ql - 1, qr - 1, f);
}
}
private:
int _n;
std::vector<value_type> _dat;
std::vector<TreeNode> _nodes;
std::vector<int> _par;
std::vector<std::array<AuxInfo, 30>> _info;
std::vector<std::array<sequence_type, 2>> _subtrees;
std::vector<int> _ord;
void reorder(int s) {
_ord.assign(_n, -1);
int t = 0;
std::deque<int> dq{ s };
while (dq.size()) {
int u = dq.front(); dq.pop_front();
_ord[u] = t++;
for (int v : _nodes[u].adj) if (_ord[v] < 0) dq.push_back(v);
}
assert(t == _n);
std::vector<TreeNode> tmp(_n);
for (int i = 0; i < _n; ++i) {
for (int& e : _nodes[i].adj) e = _ord[e];
_nodes[i].info_it = _info[_ord[i]].begin();
tmp[_ord[i]] = std::move(_nodes[i]);
}
_nodes.swap(tmp);
}
};
} // 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::PointGetRangeContourOperate<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;
}