As @skyfire said this was indeed the main idea.
In order to avoid the construction and sorting of the two subarrays over all queries, I constructed a segment tree, where [L,R] stores the sorted subarray between [L,R]. I think it is called a Merge Sort Tree.
So, I can obtain the subarrays [L1, R1] and [L2, R2] quite easily. Now to use the idea of PnC (which is mentioned by you), I have to find for the kth number in [L2, R2], how many numbers are less than that number in the interval [L1, R1]. The result will be used in the distribution of the numbers (thereby finding the number of permutations). Note that we need to take care of the distribution for the smaller number in [L2, R2] before the number larger than it. (You must have realized that as well).
Now to find the kth number in the range [L2, R2] in my tree. This is equivalent to finding the kth order statistic in sorted [L2, R2]. Refer to the problem “MKTHNUM” - http://www.spoj.com/problems/MKTHNUM/. https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/ provides a nice explanation to this problem. Rest all can be done using the lower_bound and the upper_bound functions (logarithmic time).
My implementation - https://www.codechef.com/viewsolution/12806490
However as you can see this fetched me only 70 points. I need help in figuring out why that happened.
To get the rest 30 points, I had to use brute force
100 points - https://www.codechef.com/viewsolution/12806668
P.s. This was the first ever hard level problem that I solved