You can answer all the queries offline in $$$O(n + q + m \log m)$$$ ($$$m$$$ is the length of the array).

• Visit the nodes in order of tin.
• Maintain a list of ancestors of the current node. Each node is added and removed from the list of ancestors exactly once. (Note: in the final implementation you don't need to store this list explicitly)
• Maintain a set which contains the $$$i$$$ such that $$$a_i$$$ is an ancestor of the current node. Then, you can answer queries using lower_bound.
• Every time you add / remove a node from the list of ancestors, insert / erase the corresponding $$$i$$$ in the set.

Online $$$O((n + q + m) \log^2{n})$$$ solution:

The key idea is the same as TheScrasse's solution: We query on ancestors and check if some ancestor lies within given range, instead of querying on the range in the original array and checking if some ancestor lies in that range.

Firstly, let us solve the following subproblem: Given an array $$$a$$$ of length $$$n$$$, answer queries "does there lie some element having value in range $$$[L, R]$$$ in prefix of length $$$x$$$?"

The first thought that comes to your mind is probably merge sort tree, which can answer these queries in $$$O(\log^2{n})$$$, but we can do better than this by exploiting the fact that all the queried ranges of indices are prefixes of the form $$$[1, x]$$$.

So, let us build another array $$$b$$$, such that $$$b$$$ contains each number from $$$1$$$ to $$$n$$$ once, and $$$a_{b_i} \leq a_{b_{i + 1}}$$$ (ie. sort $$$a$$$ by $$$a_i$$$ and store original index at each position instead of storing the value $$$a_i$$$). Now build a segment tree upon this array $$$b$$$, and now each query $$$(L, R, x)$$$ can be answered in the following way:

• Find the first position $$$P$$$ in $$$b$$$ where $$$a_{b_P} \geq L$$$, and last position $$$Q$$$ where $$$a_{b_Q} \leq R$$$. This can be done easily in $$$O(\log{n})$$$ using binary search.
• Simply query segment tree in range $$$[P, Q]$$$ for minimum and check if this minimum is $$$\leq x$$$. If yes, then their exists a value satisfying query constraints, otherwise there does not (because the minimum value is the position of the first element in $$$a$$$ whose value lies in the range $$$[L, R]$$$).

So we have learnt how to solve this subproblem in $$$O(\log{n})$$$ time per query.

Now let's think about how we can solve the original problem using hld. For each heavy path we will build the above described segment tree (the array $$$a$$$ is basically the indices in original array for nodes in the path, ordered by depth).

How to answer some query $$$(L, R, v)$$$?

The path $$$[root, v]$$$ gets divided into $$$O(\log{n})$$$ heavy and light paths.

1. There are only $$$O(\log{n})$$$ light paths, so we can manually check in $$$O(1)$$$ for each of them.
2. For all heavy paths which lie completely within path $$$[root, v]$$$, simply query the corresponding segment tree for this path for value in range $$$[L, R]$$$, with prefix $$$x$$$ being the total length of the segment tree.
3. Lastly, there might be at most one heavy path which partially lies within path $$$[root, v]$$$, query this segment tree for value in range $$$[L, R]$$$, with prefix $$$x$$$ corresponding to the total number of elements in the segment tree associated with the prefix of the path which lies within $$$[root, v]$$$ (get this in $$$O(\log{n})$$$) using a set.

Therefore, each query is answered in $$$O(\log{n} + \log^2{n})$$$ time, and taking precomputation into account, we achieve a total time complexity of $$$O((n + q + m) \log^2{n})$$$.