We are given an array of size N with numbers 1 <= Ai <= N(not always distinct).
There are N queries (L, R, K). For each query we need to print amount of Ai <= K, L <= i <= R. N <= 2e5
I know how to solve this task using Mo's Algorithm and Segment Tree in O(N * sqrt(N) * log2(N)). Is there a faster solution?
This is the original task, I know, probably there is an easier solution to it, but I want to try to solve it this way.