PROBLEM LINK:
Author: Misha Chorniy
Tester: Jingbo Shang
Editorialist: Pushkar Mishra
DIFFICULTY:
Hard
PREREQUISITES:
Heavy-Light Decomposition, Segment trees
PROBLEM:
Given is a tree of N nodes and two constants A and B. Each node in this tree has a value C_v assosciated with it. We are further given two types of queries. The first query asks us to add a postitive constant w to the all the nodes in the simple path from a node u to another node v. The second query asks us to tell how many nodes exist such that A*C_v + B \geq 0.
EXPLANATION:
The problem clearly hints towards Heavy-Light Decomposition. For those who don’t know what Heavy Light Decomposition is, we recommend you check out Anudeep’s Blog on it.
To make the required updates and queries on the appropriate chains of the heavy-light decomposition algorithm, we will keep a segment tree for each chain. Now, we need to know how to use the segment trees to perform the required range updates and range queries. For this, let us look at the constraints closely:
- A \geq 0, i.e., A is a non-negative number.
- 1 \leq w \leq 10^4.
Let us consider the following four cases:
- When A = 0 and B \geq 0: In this case, A*C_v + B \geq 0 for any value C_v.
- When A = 0 and B < 0: In this case, A*C_v + B \geq 0 for no value C_v.
- When A > 0 and B \geq 0: In this case, A*C_v + B \geq 0 when C_v \geq \lfloor\frac{-B}{A}\rfloor.
- When A > 0 and B < 0: In this case, A*C_v + B \geq 0 when C_v \geq \lceil\frac{-B}{A}\rceil.
Now, we can rephrase the problem.
Given a segment tree, support the following two operations:
- Add a value w to all the leaves in the index range i..j
- Report the number of leaves having value C_v greater than or equal to P where P \geq \lfloor\frac{-B}{A}\rfloor or \lceil\frac{-B}{A}\rceil depending on whether B is non-negative or negative respectively.
Now, we can formulate what all is required to be stored in the nodes of the segment tree in order to perform the updates and answer the queries. As our intuition tells us, the segment tree must process the updates using the lazy propagation technique. To achieve this, we need to store the following details per node:
- The number of alive leaves in the subtree of the node. Here, “alive” means all those nodes which have a value < P, where P is as described above. Let this be denoted by variable number\_alive.
- The maximum value amongst the values of the alive leaves. Let this be denoted by the variable max\_alive.
- Lazy propagation variable indicating the total w to be added to the leaves in the subtree of the node. Let this be denoted by the variable lazy\_update\_val.
A very crucial detail to be noted here is that w is always a positive number. This means that once a leave is “dead”, i.e., it has achieved a value of \geq P, it will remain dead for the rest of execution of the program. The query portion of the problem requires us to calculate the number of dead nodes on the path from u to v.
The last part of the algorithm is to see how to perform the lazy updates and how to efficiently count the number of dead leaves in the required range for the aforementioned segment tree.
We give the pseudocodes for the update and query operations on the segment tree.
For update, consider the pseudocode below:
fun update(cur_range_start, cur_range_end, node)
{
if(required_range_start <= cur_range_start and cur_range_end <= required_range_end)
{
node.max_alive += w; //update at this point
node.lazy_update_val += w; //mark the subtree for lazy update
return;
}
update left subtree; update right subtree;
merge left and right children;
}
For query, consider the pseudocode below:
fun query(cur_range_start, cur_range_end, node)
{
if(required_range_start <= cur_range_start and cur_range_end <= required_range_end)
{
modify subtree up till leaves;
//basically, propagate the lazy updates down to the leaves wherever required
return (cur_range_end - cur_range_start+1) - node.number_alive;
}
push the lazy value, i.e., node.lazy_update_val to the children;
query left subtree; query right subtree;
merge left and right children;
return the sum of the two queries;
}
An implementation detail to note in this question is that while updating/querying the path from node u to node v, the LCA of the two may get updated/queried twice. Care needs to be taken for the same.
Other implementation details for this method can be seen from Tester’s/Editorialist’s program. The proof of complexity is left to the reader as a simple yet interesting exercise.
COMPLEXITY:
\mathcal{O}(N \log^2 N) per test case.
ALTERNATE SOLUTION
Setter’s solution uses square-root bucketing of queries.
Key observation:
Consider i-th query and j-th query(i < j), a * c[i][v] + b <= a * c[j][v] + b, c[i][v] - value of label v after i operations.
So if a * c[i][v] + b = 0 then a * c[i + 1][v] + b = 0, a[i + 2][v] + b = 0 … a[n][v] + b = 0, so
function f(i, v) = (a * c[i][v] + b = 0) - monotonic.
f(v) = 0 ... 0 1 ... 1, we are interested in position of first 1 - let it be ind[v].
Let’s do queries in off-line, firstly read them, after process.
Divide queries by blocks of size K.
Q[1]..Q[k], Q[k+1]..Q[2*k], ..., Q[N / K * K]..Q[N]
After each block will memorize array of labels and recalc it. How to recalc? We know array for previous block, and some queries of first type in this block. In offline can do this queries with complexity O(N + K), add in offline and simple dfs. When we know array for previous block and current block,
we are interested only in those elements for which changed value of function f.
Let it be vector - V, for each element of vector V - v, go through this block of queries and find ind[v].
For each vertex we can find ind[v] in time O(K), so total complexity: \mathcal{O}(N \sqrt{N}).
