Can someone explain how to solve SEAINVS ? This is what I did :
Given two subarrays in the array, we need to find the number of permutations of the first subarray such that every element in it is smaller than the corresponding element in the second one. I sorted both the subarrays first, because finding the number of permutations of the first array with respect to any permutation of the second one would give the same answer. Then starting from the first position I just found out the number of ways that I can fill each position, and multiplied those to get the answer. But this is not fast enough for the large subtask.
To pass all tests you need work with intervals of consecutive elements.
You have two sorted array, let it be A and B. Imagine that their consecutive elements are united in intervals. Now you have two array of non-intersecting intervals, let it be A_S and B_S.
You can processed A_S and B_S in similar way like A and B, each answer’s multiplier will be presents the product of consecutive integers.
Number of consecutive intervals for each range [l, r] is O(\sqrt{K}). Where K - is number of inversions. Use segment tree to fast calculate arrays of intervals.
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).
I understand that having a Merge Sort Tree will avoid sorting the ranges for each query,(correct me if I’m wrong) and you can quickly find how many numbers in range [L1,R1] are smaller than some number ‘k’ in [L2,R2]. But aren’t you doing that for every number in [L2,R2] (going from smallest to largest in the sorted order) ? wouldn’t that be too slow ?
No. That will not be slow. Reason being that finding k’th element costs me O(logN) per query. Finding the number of elements smaller than the k’th element is O((logN)^2). So that shouldn’t be a problem.
final solution:
for 30 point we know must sort two interval [l1,r1] , [l2,r2] then find ans easily… but for full point : in statement say "“original constraints plus additionally 0 ≤ number of pairs i, j (1 ≤ i < j ≤ N, Pi > Pj) over all test cases ≤ 3*10^6"” … this show our two interval have many consecutive element! so we can use segment tree and a simple merge for find all interval consecutive element for two give interval… then use vector contain interval [l2,r2] for calculate answers… https://www.codechef.com/viewsolution/15970708
