P12861 [NERC 2020 Online] Lookup Performance

A $\emph{binary search tree}$ is a rooted binary tree whose nodes store keys so that each node's key is greater than all the keys in the node's left subtree and less than those in its right subtree. A binary search tree can be used to maintain sorted sets and allows to perform different types of queries on the set. A query that we are considering in this problem is finding the number of values in the range $[L, R]$ within the set. Let $S$ be the set of all keys in the binary search tree. You are given two values $L$ and $R$. The query is to find the number of such $x \in S$ so that $L \le x \le R$. The following recursive function computes this value when called with the parameters $\verb|lookup(root, L, R)|$, where $\verb|root|$ is the root of the binary search tree. ``` function lookup(v, L, R): if v == null: return 0 if L

The first line contains an integer $n$ ($1 \le n \le 200\,000$) --- the number of nodes in the binary search tree. The next $n$ lines describe the nodes of the tree. The $i$-th of these lines contains three integers $l_i$, $r_i$, and $k_i$ denoting the left child, the right child and the key of the $i$-th node. If the node does not have the left or/and the right child, the corresponding value is 0 ($l_i = 0$ or $i < l_i \le n$; $r_i = 0$ or $i < r_i \le n$; $-10^9 \le k_i \le 10^9$). The root of the tree is at node 1 and it is guaranteed to be a well-formed binary search tree. Note that the values $\verb|v.min|, \verb|v.max|$ and $\verb|v.count|$ are not given in the input explicitly, since they can be deduced from $l_i$, $r_i$ and $k_i$. The next line contains an integer $q$ ($1 \le q \le 200\,000$) --- the number of the queries. Each of the next $q$ lines contains two integers $L$ and $R$ ($-10^9 \le L \le R \le 10^9$) --- the parameters given to the $\verb|lookup|$ function.

Output $q$ lines, the $i$-th line containing a single integer --- the number of calls of the $\verb|lookup|$ function that are made for the $i$-th query.