Permutation 1...N. Answer queries "How many numbers between [X,Y] position are in the interval [L,K]"?
I believe the problem lies in the initialization time. If I am not wrong it is like O(n^2 log n) which might be a problem for tests with large n and small sample size.

To fix it you'll have to redo the whole algo if I am not mistaken.

There is a method that doesn't have the same long initialization problem while retaining the same O(log n) (at least on average, O(log^2 n) at worst) time per iteration - simply build a two dimensional segment tree. Since we work with a permutation it will be rather sparse.