Given N arrays of arbitrary length each, and M queries in form : a b. For each query output the number of arrays such that there exist Array[i] = a Array[j] = b and i < j (Basically, number of arrays such that a comes before b). Also, there can be any number of a's or b's in any array
N, M, a, b < = 105 Consider that length of all arrays is < = 105
Example: Arrays
1 2 3 4
2 4
2 3 1 4
and queries are (1, 3) , (2, 4) , (1, 4) , (4, 1) answers are 1 , 3 , 2 , 0
Constraints?
Updated
Let maxN = 105.
1) Number of array which exist that pair for a,b that is number of array such there first occurrence of element a more to the left than last occurrence of element b.
2) Before requests you can precalculate number of arrays, which length is smaller than
and they satisfy the condition for each pair (a,b) in map < pair < int, int > , int > . The size of this map will not be greater than 
.
3) Also you want to precalc for all posible value and array first and last occurrence of it.
For each request you will get appropriate value in map and consider all arrays with size not smaller than
(count of this arrays not bigger than 
). Using 1 and 3 its easy to consider them.
Сomplexity
.
Using Hash Tables complexity will be
.
I missed the part with arrays of smaller length, really stupid of me... Not hard problem at all. Thank you
For each array with size smaller than
we will use naive algo: brute positions i < j and if pair (Array[i], Array[j]) we don't see in this array before will update info in map like m[{Array[i], Array[j]}]++.
Oh, I meant when I was solving problem, thank you anyway