The solution to the first problem hinges on a capacity threshold observation regarding subtrees relative to a target node. If the aggregate capacity of all subtrees excluding the target exceeds a specific bound, the second player can guarantee allocating at least half of the operations outside the target subtree. This lower bound is tight when the first player restricts actions to positive-valued updates.
Implementing this requires a data structure capable of handling subtree queries alongside two distinct update types: doubling individual values and applying an additive constant to ranges. While heavy-haul merge sort trees or HLD-based approaches yield $O(n \log^2 n)$ performance, they introduce significant implementation overhead. A more efficient strategy exploits the fact that each element undergoes at most $O(\log \sum c_i)$ doubling operations. We maintain a priority-heap structure where elements below a threshold $a$ are extracted individually, while larger elements recieve a global addition tag. Using a leftist or skew heap allows us to pop all nodes $\leq a$, apply the doubling transformation, reinsert them, and attach the additive tag to the remaining forest roots. The monotonicity of the transformation $f(x) = x + \min(x, a)$ ensures that relative ordering remains unchanged, preserving the heap topology during traversal. By isolating affected nodes and lazily propagating tags across the extracted forest, we achieve an overall complexity of $O(n \log \sum c_i)$.
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1000005;
int n, tree_root;
ll add_tag[MAXN], val[MAXN];
ll base_cap[MAXN];
int left_son[MAXN], right_son[MAXN];
int heap_root[MAXN];
int node_height[MAXN];
inline void push_add(int idx, ll inc) {
add_tag[idx] += inc;
val[idx] += inc;
}
inline void lazy_propagate(int idx) {
if (add_tag[idx]) {
if (left_son[idx]) push_add(left_son[idx], add_tag[idx]);
if (right_son[idx]) push_add(right_son[idx], add_tag[idx]);
add_tag[idx] = 0;
}
}
int heap_merge(int u, int v) {
if (!u || !v) return u | v;
if (val[u] > val[v]) swap(u, v);
lazy_propagate(u);
right_son[u] = heap_merge(right_son[u], v);
if (node_height[left_son[u]] < node_height[right_son[u]])
swap(left_son[u], right_son[u]);
node_height[u] = node_height[right_son[u]] + 1;
return u;
}
void apply_transform(int idx, ll limit) {
if (val[idx] < limit) val[idx] <<= 1;
else return push_add(idx, limit);
lazy_propagate(idx);
if (left_son[idx]) apply_transform(left_son[idx], limit);
if (right_son[idx]) apply_transform(right_son[idx], limit);
}
void build_subtrees(int u) {
ll cap_sum = base_cap[u];
cap_sum += (left_son[u] ? base_cap[left_son[u]] : 0);
cap_sum += (right_son[u] ? base_cap[right_son[u]] : 0);
val[u] = cap_sum;
heap_root[u] = u;
if (left_son[u]) {
build_subtrees(left_son[u]);
apply_transform(heap_root[left_son[u]], base_cap[right_son[u]]);
heap_root[u] = heap_merge(heap_root[u], heap_root[left_son[u]]);
}
if (right_son[u]) {
build_subtrees(right_son[u]);
apply_transform(heap_root[right_son[u]], base_cap[left_son[u]]);
heap_root[u] = heap_merge(heap_root[u], heap_root[right_son[u]]);
}
}
void propagate_all(int u) {
lazy_propagate(u);
if (left_son[u]) propagate_all(left_son[u]);
if (right_son[u]) propagate_all(right_son[u]);
}
// Standard fast I/O assumed
inline int read() { /* implementation omitted for brevity */ }
int main() {
n = read();
for (int i = 2; i <= n; ++i) {
int p = read();
if (left_son[p]) right_son[p] = i;
else left_son[p] = i;
}
for (int i = 1; i <= n; ++i) base_cap[i] = read<ll>();
build_subtrees(1);
propagate_all(heap_root[1]);
for (int i = 1; i <= n; ++i) printf("%lld ", val[i]);
putchar('\n');
return 0;
}
The second challenge involves range updates combining bitwise population count operations with standard addition. The critical insight is that popcount(x) maps inputs into a compressed domain bounded by $O(\log V)$. When restricted solely to the population count operation, contiguous segments sharing identical transformed values can be merged efficiently, similar to the Old Driver Tree paradigm. Each update introduces at most two new boundaries, causing the potential function (segment count) to decrease by one per step, resulting in $O((n+q)\log V \alpha(n))$ time complexity. Composing multiple popcount calls corresponds to applying a fixed permutation over the compressed domain, which can be tracked using disjoint set union or array composition.
Introducing additive range updates complicates pure segment merging due to tag distribution overhead. Switching to a segment tree framework alows artificial partitioning of ranges, enabling efficient lazy propagation while preserving the small-value-domain property. We mark specific nodes as terminal segments, compute the composite permutation for their domains, and apply amortized potential accounting. Pushdown operations generate at most two new terminal markers, bounding total potential at $O(q \log n)$. Merging operations cost $O(\log V)$, yielding amortized $O(\log n \log V)$ per update. Point queries resolve in $O(\log n)$ via tag permanentization.
#include <cstdio>
using namespace std;
typedef long long ll;
const int MAXN = 300005;
const int LgV = 50;
int n, q;
int initial_vals[MAXN];
int perm_matrix[MAXN << 2][LgV];
ll lazy_add[MAXN << 2];
bool is_segment_end[MAXN << 2];
inline void apply_popcount(int p) {
for (int i = 0; i < LgV; ++i)
perm_matrix[p][i] = __builtin_popcountll(perm_matrix[p][i] + lazy_add[p]);
lazy_add[p] = 0;
}
void push_tags(int p, int l, int r) {
if (is_segment_end[p]) {
int mid = (l + r) >> 1;
for (int i = 0; i < LgV; ++i)
perm_matrix[p << 1][i] = perm_matrix[p][perm_matrix[p << 1][i]];
for (int i = 0; i < LgV; ++i)
perm_matrix[p << 1 | 1][i] = perm_matrix[p][perm_matrix[p << 1 | 1][i]];
for (int i = 0; i < LgV; ++i) perm_matrix[p][i] = i;
is_segment_end[p << 1] = true;
is_segment_end[p << 1 | 1] = true;
is_segment_end[p] = false;
}
if (lazy_add[p]) {
lazy_add[p << 1] += lazy_add[p];
lazy_add[p << 1 | 1] += lazy_add[p];
lazy_add[p] = 0;
}
}
void build_tree(int p, int l, int r) {
for (int i = 0; i < LgV; ++i) perm_matrix[p][i] = i;
if (l == r) { is_segment_end[p] = true; lazy_add[p] = initial_vals[l]; return; }
is_segment_end[p] = false; lazy_add[p] = 0;
int mid = (l + r) >> 1;
build_tree(p << 1, l, mid);
build_tree(p << 1 | 1, mid + 1, r);
}
void ensure_terminal(int p, int l, int r) {
if (is_segment_end[p]) { apply_popcount(p); return; }
push_tags(p, l, r);
int mid = (l + r) >> 1;
ensure_terminal(p << 1, l, mid);
ensure_terminal(p << 1 | 1, mid + 1, r);
}
void update_range(int ql, int qr, int p, int l, int r) {
if (ql <= l && r <= qr) {
ensure_terminal(p, l, r);
is_segment_end[p] = true;
return;
}
push_tags(p, l, r);
int mid = (l + r) >> 1;
if (ql <= mid) update_range(ql, qr, p << 1, l, mid);
if (qr > mid) update_range(ql, qr, p << 1 | 1, mid + 1, r);
}
void add_value(int ql, int qr, ll v, int p, int l, int r) {
if (ql <= l && r <= qr) { lazy_add[p] += v; return; }
push_tags(p, l, r);
int mid = (l + r) >> 1;
if (ql <= mid) add_value(ql, qr, v, p << 1, l, mid);
if (qr > mid) add_value(ql, qr, v, p << 1 | 1, mid + 1, r);
}
ll query_single(int idx, int p, int l, int r) {
if (l == r) return perm_matrix[p][0] + lazy_add[p];
push_tags(p, l, r);
int mid = (l + r) >> 1;
if (idx <= mid) return query_single(idx, p << 1, l, mid) + lazy_add[p];
else return query_single(idx, p << 1 | 1, mid + 1, r) + lazy_add[p];
}
// Standard fast I/O assumed
inline int read() { /* implementation omitted for brevity */ }
int main() {
n = read(); q = read();
for (int i = 1; i <= n; ++i) initial_vals[i] = read();
build_tree(1, 1, n);
char op[4]; int l, r, v;
while (q--) {
scanf("%s", op);
if (op[0] == 'A') {
l = read(); r = read(); v = read();
add_value(l, r, v, 1, 1, n);
} else if (op[0] == 'P') {
l = read(); r = read();
update_range(l, r, 1, 1, n);
} else if (op[0] == 'J') {
printf("%lld\n", query_single(read(), 1, 1, n));
}
}
return 0;
}