Background↵
------------------↵
↵
During Facebook Hacker Cup Round 2 today, Problem D caught my attention. It reminded me of a particular data structure called a **kinetic tournament**, which is not very well known in this community. However, it offers an extremely clean and slick solution to the problem, in my opinion.↵
↵
I first learned about this data structure from [user:dragonslayerintraining,2020-08-30], who described a variant of it in this [Codeforces blog comment](https://codeforces.net/blog/entry/68534#comment-530381). Since the data structure is so interesting, I feel like it deserves a longer explanation, some template code, and more examples. That's why I am writing this blog post.↵
↵
Kinetic Tournaments↵
------------------↵
↵
Briefly, the functionality of the data structure is a mix between a line container,↵
i.e., "convex hull trick", and a segment tree.↵
↵
Suppose that you have an array containing pairs of nonnegative integers,↵
$A[i]$ and $B[i]$. You also have a global parameter $T$, corresponding to the↵
"temperature" of the data structure. Your goal is to support the following↵
queries on this data:↵
↵
- **update**(i, a, b): set $A[i] = \text a$ and $B[i] = \text b$↵
- **query**(s, e): return $\displaystyle \min_{s \leq i \leq e} A[i] * T + B[i]$↵
- **heaten**(new_temp): set $T = \text{new_temp}$↵
- [precondition: new_temp >= current value of T]↵
↵
(For simplicity, we set A[i] = 0 and B[i] = LLONG_MAX for uninitialized↵
entries, which should not change the query results.)↵
↵
This allows you to essentially do arbitrary lower convex hull queries on a↵
collection of lines, as well as any contiguous subcollection of those lines.↵
This is more powerful than standard convex hull tricks and related data↵
structures (Li-Chao Segment Tree) for three reasons:↵
↵
- You can arbitrarily remove/edit lines, not just add them.↵
- Dynamic access to any subinterval of lines, which lets you avoid costly↵
merge small-to-large operations in some cases.↵
- Easy to reason about and implement from scratch, unlike dynamic CHT.↵
↵
The tradeoff is that you can only query sequential values (temperature is↵
only allowed to increase) for amortization reasons, but this happens to be↵
a fairly common case in many problems.↵
↵
Here's the kicker. If you implement the data structure correctly, you get↵
the following time complexities:↵
↵
- **query**: $O(\log n)$↵
- **update**: $O(\log n)$↵
- **heaten**: $O(\log^2 n)$ [amortized]↵
↵
(The runtime complexity might actually be $O(m \alpha(m) \log^2 n)$ instead of $O(m \log^2 n)$ if your updates include both adding and removing lines, and you're also very careful about constructing an example. See the discussion below from [user:Elegia,2020-08-30] about Davenport-Schinzel sequences.)↵
↵
Implementation↵
------------------↵
↵
How does it work? With [kinetic tournaments](https://en.wikipedia.org/wiki/Kinetic_tournament), you essentially build a min segtree as usual, but you add a global priority queue that stores whenever a "contract" breaks. We can put this in the analogy of increasing temperature. For every node, you store the temperatures at which that node "melts", meaning that the minimum value changes from one child to the other. Then, you can just keep popping events from this priority queue as your data structure heats up.↵
↵
↵
↵
However, this unfortunately can be slow if you're not careful, which isn't good enough, especially if you have many concurrent lines (might give you quadratic runtime, depending on implementation of priority queue). Luckily, there's a neat implementation trick that circumvents the priority queue and prevents this possible quadratic runtime. In every node of the segment tree, you store the minimum temperature at which _any part of its subtree could melt_. This fits in naturally with the segment tree definition.↵
↵
To optimize the data structure, you do not recompute at every certificate failure. Instead, whenever the user calls **heaten()**, you batch all of the recompute operations and recursively _rebuild only the parts of the segment tree that changed_, once.↵
↵
The runtime analysis follows from comparing the data structure to computing a convex hull by divide-and-conquer (thanks [user:dragonslayerintraining,2020-08-30]!). The number of times each node "melts" is bounded at most by the number of leaves in its subtree. This is because you can never have two lines, $A$ and $B$, such that $A(x_1) < B(x_1)$, $A(x_2) > B(x_2)$, and $A(x_3) < B(x_3)$, where $x_1 < x_2 < x_3$. In other words, as you increase temperature, the number of recalculations is at most $O(n \log n)$. Combining this with the fact that we have to walk down the segment tree, which has logarithmic depth, every time we do a recalculation, this yields a final amortized time complexity of $O(\log^2 n)$ for each "heaten" operation.↵
↵
Code↵
------------------↵
↵
You can find my implementation of a modified kinetic tournament here:↵
↵
https://ekzlib.herokuapp.com/view/kinetic_tournament.cpp↵
↵
It defines a single struct with template type (~100 LoC), which has a plug-and-play interface that you can use in your own solutions, and **no global variable pollution**. Example usage:↵
↵
~~~~~↵
int N = 2;↵
kinetic_tournament<long long> kt(N);↵
↵
kt.update(0, 2, 10); // 2t + 10↵
kt.update(1, 4, 1); // 4t + 1↵
↵
kt.heaten(1); // t = 1↵
kt.query(0, 0); // => 2*1 + 10 = 12↵
kt.query(1, 1); // => 4*1 + 1 = 5↵
kt.query(0, 1); // => min(2*1 + 10, 4*1 + 1) = 5↵
↵
kt.heaten(5); // t = 5↵
kt.query(0, 0); // => 2*5 + 10 = 20↵
kt.query(1, 1); // => 4*5 + 1 = 21↵
kt.query(0, 1); // => min(2*5 + 10, 4*5 + 1) = 20↵
~~~~~↵
↵
I've verified this implementation on Problem D from Facebook Hacker Cup Round 2, titled ["Log Drivin' Hirin'"](https://www.facebook.com/codingcompetitions/hacker-cup/2020/round-2/problems/D). In this problem, you can simply sort the queries and nodes in order of increasing "carelessness", and the kinetic tournament finishes the task. Full solution is available below. It runs in less than 5 seconds on the entire test input.↵
↵
<spoiler summary="Code">↵
↵
~~~~~#include <bits/stdc++.h>↵
using namespace std;↵
↵
typedef long long LL;↵
↵
#define MAXN 1000013↵
#define MAXM 1000013↵
#define MOD 1000000007↵
↵
int T;↵
int N, M, K;↵
int P[MAXN], L[MAXN], H[MAXN], X[MAXM], Y[MAXM];↵
vector<int> adj[MAXN];↵
int in[MAXN], out[MAXN], t = 0;↵
LL depth[MAXN];↵
↵
template <typename T = int64_t>↵
class kinetic_tournament {↵
const T INF = numeric_limits<T>::max();↵
typedef pair<T, T> line;↵
↵
size_t n; // size of the underlying array↵
T temp; // current temperature↵
vector<line> st; // tournament tree↵
vector<T> melt; // melting temperature of each subtree↵
↵
inline T eval(const line& ln, T t) {↵
return ln.first * t + ln.second;↵
}↵
↵
inline bool cmp(const line& line1, const line& line2) {↵
auto x = eval(line1, temp);↵
auto y = eval(line2, temp);↵
if (x != y) return x < y;↵
return line1.first < line2.first;↵
}↵
↵
T next_isect(const line& line1, const line& line2) {↵
if (line1.first > line2.first) {↵
T delta = eval(line2, temp) - eval(line1, temp);↵
T delta_slope = line1.first - line2.first;↵
assert(delta > 0);↵
T mint = temp + (delta - 1) / delta_slope + 1;↵
return mint > temp ? mint : INF; // prevent overflow↵
}↵
return INF;↵
}↵
↵
void recompute(size_t lo, size_t hi, size_t node) {↵
if (lo == hi || melt[node] > temp) return;↵
↵
size_t mid = (lo + hi) / 2;↵
recompute(lo, mid, 2 * node + 1);↵
recompute(mid + 1, hi, 2 * node + 2);↵
↵
auto line1 = st[2 * node + 1];↵
auto line2 = st[2 * node + 2];↵
if (!cmp(line1, line2))↵
swap(line1, line2);↵
st[node] = line1;↵
↵
melt[node] = min(melt[2 * node + 1], melt[2 * node + 2]);↵
if (line1 != line2) {↵
T t = next_isect(line1, line2);↵
assert(t > temp);↵
melt[node] = min(melt[node], t);↵
}↵
}↵
↵
void update(size_t i, T a, T b, size_t lo, size_t hi, size_t node) {↵
if (i < lo || i > hi) return;↵
if (lo == hi) {↵
st[node] = {a, b};↵
return;↵
}↵
size_t mid = (lo + hi) / 2;↵
update(i, a, b, lo, mid, 2 * node + 1);↵
update(i, a, b, mid + 1, hi, 2 * node + 2);↵
melt[node] = 0;↵
recompute(lo, hi, node);↵
}↵
↵
T query(size_t s, size_t e, size_t lo, size_t hi, size_t node) {↵
if (hi < s || lo > e) return INF;↵
if (s <= lo && hi <= e) return eval(st[node], temp);↵
size_t mid = (lo + hi) / 2;↵
return min(query(s, e, lo, mid, 2 * node + 1),↵
query(s, e, mid + 1, hi, 2 * node + 2));↵
}↵
↵
public:↵
// Constructor for a kinetic tournament, takes in the size n of the↵
// underlying arrays a[..], b[..] as input.↵
kinetic_tournament(size_t size) : n(size), temp(0) {↵
assert(size > 0);↵
size_t seg_size = ((size_t) 2) << (64 - __builtin_clzll(n - 1));↵
st.resize(seg_size, {0, INF});↵
melt.resize(seg_size, INF);↵
}↵
↵
// Sets A[i] = a, B[i] = b.↵
void update(size_t i, T a, T b) {↵
update(i, a, b, 0, n - 1, 0);↵
}↵
↵
// Returns min{s <= i <= e} A[i] * T + B[i].↵
T query(size_t s, size_t e) {↵
return query(s, e, 0, n - 1, 0);↵
}↵
↵
// Increases the internal temperature to new_temp.↵
void heaten(T new_temp) {↵
assert(new_temp >= temp);↵
temp = new_temp;↵
recompute(0, n - 1, 0);↵
}↵
};↵
↵
void read_p(int* X, int lim) {↵
for (int i = 0; i < K; i++)↵
cin >> X[i];↵
LL A, B, C;↵
cin >> A >> B >> C;↵
for (int i = K; i < lim; i++)↵
X[i] = ((A * X[i - 2] + B * X[i - 1] + C) % i) + 1;↵
}↵
↵
void read_input(int* X, int lim) {↵
for (int i = 0; i < K; i++)↵
cin >> X[i];↵
LL A, B, C, D;↵
cin >> A >> B >> C >> D;↵
for (int i = K; i < lim; i++)↵
X[i] = ((A * X[i - 2] + B * X[i - 1] + C) % D) + 1;↵
}↵
↵
void read_x(int* X, int lim, int mod) {↵
for (int i = 0; i < K; i++)↵
cin >> X[i];↵
LL A, B, C;↵
cin >> A >> B >> C;↵
for (int i = K; i < lim; i++)↵
X[i] = ((A * X[i - 2] + B * X[i - 1] + C) % mod) + 1;↵
}↵
↵
void dfs(int n, LL d) {↵
in[n] = t++;↵
depth[n] = d;↵
for (int v : adj[n]) {↵
dfs(v, d + L[v]);↵
}↵
out[n] = t;↵
}↵
↵
void solve() {↵
cin >> N >> M >> K;↵
read_p(P, N);↵
read_input(L, N);↵
read_input(H, N);↵
read_x(X, M, N);↵
read_input(Y, M);↵
↵
for (int i = 0; i < N; i++) {↵
// deallocate memory for adj↵
vector<int> temp;↵
swap(temp, adj[i]);↵
in[i] = out[i] = -1;↵
depth[i] = 0;↵
}↵
↵
for (int i = 1; i < N; i++) {↵
--P[i];↵
adj[P[i]].push_back(i);↵
}↵
↵
t = 0;↵
dfs(0, 0);↵
↵
kinetic_tournament<> kt(N);↵
vector<pair<int, pair<bool, int> > > events;↵
LL ans = 1;↵
for (int i = 0; i < M; i++) {↵
--X[i];↵
events.push_back({Y[i], {true, i}});↵
}↵
for (int i = 0; i < N; i++) {↵
if (adj[i].size()) { // not a leaf↵
events.push_back({H[i], {false, i}});↵
} else { // leaf↵
kt.update(in[i], depth[i], 0);↵
}↵
}↵
↵
sort(events.begin(), events.end());↵
for (auto p : events) {↵
int temp = p.first;↵
kt.heaten(temp);↵
if (p.second.first) { // query↵
int qi = p.second.second;↵
int n = X[qi];↵
LL val = kt.query(in[n], out[n] - 1) - temp * depth[n];↵
ans = (ans * ((val + 1) % MOD)) % MOD;↵
}↵
else { // update↵
int n = p.second.second;↵
LL val = kt.query(in[n], out[n] - 1) - temp * depth[n];↵
kt.update(in[n], depth[n], val);↵
}↵
}↵
↵
cout << ans << '\n';↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
↵
freopen("D.txt", "r", stdin);↵
freopen("D.out", "w", stdout);↵
↵
cin >> T;↵
for (int tc = 1; tc <= T; tc++) {↵
cerr << tc << endl;↵
cout << "Case #" << tc << ": ";↵
solve();↵
}↵
↵
cout.flush();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
Conclusion↵
------------------↵
↵
I hope to see more of this interesting data structure pop up in competitive programming! Hopefully this explanatory blog post is useful for you, and please let me know if you find any errors.
------------------↵
↵
During Facebook Hacker Cup Round 2 today, Problem D caught my attention. It reminded me of a particular data structure called a **kinetic tournament**, which is not very well known in this community. However, it offers an extremely clean and slick solution to the problem, in my opinion.↵
↵
I first learned about this data structure from [user:dragonslayerintraining,2020-08-30], who described a variant of it in this [Codeforces blog comment](https://codeforces.net/blog/entry/68534#comment-530381). Since the data structure is so interesting, I feel like it deserves a longer explanation, some template code, and more examples. That's why I am writing this blog post.↵
↵
Kinetic Tournaments↵
------------------↵
↵
Briefly, the functionality of the data structure is a mix between a line container,↵
i.e., "convex hull trick", and a segment tree.↵
↵
Suppose that you have an array containing pairs of nonnegative integers,↵
$A[i]$ and $B[i]$. You also have a global parameter $T$, corresponding to the↵
"temperature" of the data structure. Your goal is to support the following↵
queries on this data:↵
↵
- **update**(i, a, b): set $A[i] = \text a$ and $B[i] = \text b$↵
- **query**(s, e): return $\displaystyle \min_{s \leq i \leq e} A[i] * T + B[i]$↵
- **heaten**(new_temp): set $T = \text{new_temp}$↵
- [precondition: new_temp >= current value of T]↵
↵
(For simplicity, we set A[i] = 0 and B[i] = LLONG_MAX for uninitialized↵
entries, which should not change the query results.)↵
↵
This allows you to essentially do arbitrary lower convex hull queries on a↵
collection of lines, as well as any contiguous subcollection of those lines.↵
This is more powerful than standard convex hull tricks and related data↵
structures (Li-Chao Segment Tree) for three reasons:↵
↵
- You can arbitrarily remove/edit lines, not just add them.↵
- Dynamic access to any subinterval of lines, which lets you avoid costly↵
merge small-to-large operations in some cases.↵
- Easy to reason about and implement from scratch, unlike dynamic CHT.↵
↵
The tradeoff is that you can only query sequential values (temperature is↵
only allowed to increase) for amortization reasons, but this happens to be↵
a fairly common case in many problems.↵
↵
Here's the kicker. If you implement the data structure correctly, you get↵
the following time complexities:↵
↵
- **query**: $O(\log n)$↵
- **update**: $O(\log n)$↵
- **heaten**: $O(\log^2 n)$ [amortized]↵
↵
(The runtime complexity might actually be $O(m \alpha(m) \log^2 n)$ instead of $O(m \log^2 n)$ if your updates include both adding and removing lines, and you're also very careful about constructing an example. See the discussion below from [user:Elegia,2020-08-30] about Davenport-Schinzel sequences.)↵
↵
Implementation↵
------------------↵
↵
How does it work? With [kinetic tournaments](https://en.wikipedia.org/wiki/Kinetic_tournament), you essentially build a min segtree as usual, but you add a global priority queue that stores whenever a "contract" breaks. We can put this in the analogy of increasing temperature. For every node, you store the temperatures at which that node "melts", meaning that the minimum value changes from one child to the other. Then, you can just keep popping events from this priority queue as your data structure heats up.↵
↵
↵
↵
However, this unfortunately can be slow if you're not careful, which isn't good enough, especially if you have many concurrent lines (might give you quadratic runtime, depending on implementation of priority queue). Luckily, there's a neat implementation trick that circumvents the priority queue and prevents this possible quadratic runtime. In every node of the segment tree, you store the minimum temperature at which _any part of its subtree could melt_. This fits in naturally with the segment tree definition.↵
↵
To optimize the data structure, you do not recompute at every certificate failure. Instead, whenever the user calls **heaten()**, you batch all of the recompute operations and recursively _rebuild only the parts of the segment tree that changed_, once.↵
↵
The runtime analysis follows from comparing the data structure to computing a convex hull by divide-and-conquer (thanks [user:dragonslayerintraining,2020-08-30]!). The number of times each node "melts" is bounded at most by the number of leaves in its subtree. This is because you can never have two lines, $A$ and $B$, such that $A(x_1) < B(x_1)$, $A(x_2) > B(x_2)$, and $A(x_3) < B(x_3)$, where $x_1 < x_2 < x_3$. In other words, as you increase temperature, the number of recalculations is at most $O(n \log n)$. Combining this with the fact that we have to walk down the segment tree, which has logarithmic depth, every time we do a recalculation, this yields a final amortized time complexity of $O(\log^2 n)$ for each "heaten" operation.↵
↵
Code↵
------------------↵
↵
You can find my implementation of a modified kinetic tournament here:↵
↵
https://ekzlib.herokuapp.com/view/kinetic_tournament.cpp↵
↵
It defines a single struct with template type (~100 LoC), which has a plug-and-play interface that you can use in your own solutions, and **no global variable pollution**. Example usage:↵
↵
~~~~~↵
int N = 2;↵
kinetic_tournament<long long> kt(N);↵
↵
kt.update(0, 2, 10); // 2t + 10↵
kt.update(1, 4, 1); // 4t + 1↵
↵
kt.heaten(1); // t = 1↵
kt.query(0, 0); // => 2*1 + 10 = 12↵
kt.query(1, 1); // => 4*1 + 1 = 5↵
kt.query(0, 1); // => min(2*1 + 10, 4*1 + 1) = 5↵
↵
kt.heaten(5); // t = 5↵
kt.query(0, 0); // => 2*5 + 10 = 20↵
kt.query(1, 1); // => 4*5 + 1 = 21↵
kt.query(0, 1); // => min(2*5 + 10, 4*5 + 1) = 20↵
~~~~~↵
↵
I've verified this implementation on Problem D from Facebook Hacker Cup Round 2, titled ["Log Drivin' Hirin'"](https://www.facebook.com/codingcompetitions/hacker-cup/2020/round-2/problems/D). In this problem, you can simply sort the queries and nodes in order of increasing "carelessness", and the kinetic tournament finishes the task. Full solution is available below. It runs in less than 5 seconds on the entire test input.↵
↵
<spoiler summary="Code">↵
↵
~~~~~#include <bits/stdc++.h>↵
using namespace std;↵
↵
typedef long long LL;↵
↵
#define MAXN 1000013↵
#define MAXM 1000013↵
#define MOD 1000000007↵
↵
int T;↵
int N, M, K;↵
int P[MAXN], L[MAXN], H[MAXN], X[MAXM], Y[MAXM];↵
vector<int> adj[MAXN];↵
int in[MAXN], out[MAXN], t = 0;↵
LL depth[MAXN];↵
↵
template <typename T = int64_t>↵
class kinetic_tournament {↵
const T INF = numeric_limits<T>::max();↵
typedef pair<T, T> line;↵
↵
size_t n; // size of the underlying array↵
T temp; // current temperature↵
vector<line> st; // tournament tree↵
vector<T> melt; // melting temperature of each subtree↵
↵
inline T eval(const line& ln, T t) {↵
return ln.first * t + ln.second;↵
}↵
↵
inline bool cmp(const line& line1, const line& line2) {↵
auto x = eval(line1, temp);↵
auto y = eval(line2, temp);↵
if (x != y) return x < y;↵
return line1.first < line2.first;↵
}↵
↵
T next_isect(const line& line1, const line& line2) {↵
if (line1.first > line2.first) {↵
T delta = eval(line2, temp) - eval(line1, temp);↵
T delta_slope = line1.first - line2.first;↵
assert(delta > 0);↵
T mint = temp + (delta - 1) / delta_slope + 1;↵
return mint > temp ? mint : INF; // prevent overflow↵
}↵
return INF;↵
}↵
↵
void recompute(size_t lo, size_t hi, size_t node) {↵
if (lo == hi || melt[node] > temp) return;↵
↵
size_t mid = (lo + hi) / 2;↵
recompute(lo, mid, 2 * node + 1);↵
recompute(mid + 1, hi, 2 * node + 2);↵
↵
auto line1 = st[2 * node + 1];↵
auto line2 = st[2 * node + 2];↵
if (!cmp(line1, line2))↵
swap(line1, line2);↵
st[node] = line1;↵
↵
melt[node] = min(melt[2 * node + 1], melt[2 * node + 2]);↵
if (line1 != line2) {↵
T t = next_isect(line1, line2);↵
assert(t > temp);↵
melt[node] = min(melt[node], t);↵
}↵
}↵
↵
void update(size_t i, T a, T b, size_t lo, size_t hi, size_t node) {↵
if (i < lo || i > hi) return;↵
if (lo == hi) {↵
st[node] = {a, b};↵
return;↵
}↵
size_t mid = (lo + hi) / 2;↵
update(i, a, b, lo, mid, 2 * node + 1);↵
update(i, a, b, mid + 1, hi, 2 * node + 2);↵
melt[node] = 0;↵
recompute(lo, hi, node);↵
}↵
↵
T query(size_t s, size_t e, size_t lo, size_t hi, size_t node) {↵
if (hi < s || lo > e) return INF;↵
if (s <= lo && hi <= e) return eval(st[node], temp);↵
size_t mid = (lo + hi) / 2;↵
return min(query(s, e, lo, mid, 2 * node + 1),↵
query(s, e, mid + 1, hi, 2 * node + 2));↵
}↵
↵
public:↵
// Constructor for a kinetic tournament, takes in the size n of the↵
// underlying arrays a[..], b[..] as input.↵
kinetic_tournament(size_t size) : n(size), temp(0) {↵
assert(size > 0);↵
size_t seg_size = ((size_t) 2) << (64 - __builtin_clzll(n - 1));↵
st.resize(seg_size, {0, INF});↵
melt.resize(seg_size, INF);↵
}↵
↵
// Sets A[i] = a, B[i] = b.↵
void update(size_t i, T a, T b) {↵
update(i, a, b, 0, n - 1, 0);↵
}↵
↵
// Returns min{s <= i <= e} A[i] * T + B[i].↵
T query(size_t s, size_t e) {↵
return query(s, e, 0, n - 1, 0);↵
}↵
↵
// Increases the internal temperature to new_temp.↵
void heaten(T new_temp) {↵
assert(new_temp >= temp);↵
temp = new_temp;↵
recompute(0, n - 1, 0);↵
}↵
};↵
↵
void read_p(int* X, int lim) {↵
for (int i = 0; i < K; i++)↵
cin >> X[i];↵
LL A, B, C;↵
cin >> A >> B >> C;↵
for (int i = K; i < lim; i++)↵
X[i] = ((A * X[i - 2] + B * X[i - 1] + C) % i) + 1;↵
}↵
↵
void read_input(int* X, int lim) {↵
for (int i = 0; i < K; i++)↵
cin >> X[i];↵
LL A, B, C, D;↵
cin >> A >> B >> C >> D;↵
for (int i = K; i < lim; i++)↵
X[i] = ((A * X[i - 2] + B * X[i - 1] + C) % D) + 1;↵
}↵
↵
void read_x(int* X, int lim, int mod) {↵
for (int i = 0; i < K; i++)↵
cin >> X[i];↵
LL A, B, C;↵
cin >> A >> B >> C;↵
for (int i = K; i < lim; i++)↵
X[i] = ((A * X[i - 2] + B * X[i - 1] + C) % mod) + 1;↵
}↵
↵
void dfs(int n, LL d) {↵
in[n] = t++;↵
depth[n] = d;↵
for (int v : adj[n]) {↵
dfs(v, d + L[v]);↵
}↵
out[n] = t;↵
}↵
↵
void solve() {↵
cin >> N >> M >> K;↵
read_p(P, N);↵
read_input(L, N);↵
read_input(H, N);↵
read_x(X, M, N);↵
read_input(Y, M);↵
↵
for (int i = 0; i < N; i++) {↵
// deallocate memory for adj↵
vector<int> temp;↵
swap(temp, adj[i]);↵
in[i] = out[i] = -1;↵
depth[i] = 0;↵
}↵
↵
for (int i = 1; i < N; i++) {↵
--P[i];↵
adj[P[i]].push_back(i);↵
}↵
↵
t = 0;↵
dfs(0, 0);↵
↵
kinetic_tournament<> kt(N);↵
vector<pair<int, pair<bool, int> > > events;↵
LL ans = 1;↵
for (int i = 0; i < M; i++) {↵
--X[i];↵
events.push_back({Y[i], {true, i}});↵
}↵
for (int i = 0; i < N; i++) {↵
if (adj[i].size()) { // not a leaf↵
events.push_back({H[i], {false, i}});↵
} else { // leaf↵
kt.update(in[i], depth[i], 0);↵
}↵
}↵
↵
sort(events.begin(), events.end());↵
for (auto p : events) {↵
int temp = p.first;↵
kt.heaten(temp);↵
if (p.second.first) { // query↵
int qi = p.second.second;↵
int n = X[qi];↵
LL val = kt.query(in[n], out[n] - 1) - temp * depth[n];↵
ans = (ans * ((val + 1) % MOD)) % MOD;↵
}↵
else { // update↵
int n = p.second.second;↵
LL val = kt.query(in[n], out[n] - 1) - temp * depth[n];↵
kt.update(in[n], depth[n], val);↵
}↵
}↵
↵
cout << ans << '\n';↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
↵
freopen("D.txt", "r", stdin);↵
freopen("D.out", "w", stdout);↵
↵
cin >> T;↵
for (int tc = 1; tc <= T; tc++) {↵
cerr << tc << endl;↵
cout << "Case #" << tc << ": ";↵
solve();↵
}↵
↵
cout.flush();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
Conclusion↵
------------------↵
↵
I hope to see more of this interesting data structure pop up in competitive programming! Hopefully this explanatory blog post is useful for you, and please let me know if you find any errors.
