Create an array B
of the same size as A
and a map C
. For each j
in B[j]
keep track of the number of occurrences of A[j]
before j
. In C
keep track of the last occurrence of given element. Then you answer queries in constant time and it requires just O(n) memory.
Sorry for my pseudo-C++.
map<int,int> C;
int B[n]; // zeros
for(int i=0;i<n;++i)
{
cin >> A[i];
int prev = C[A[i]]; // let me assume it gives -1 if no element
if (pref == -1) // this is the fist occurrence of B[i]
B[i] = 1;
else // if not the first, then add previous occurrences
B[i] = B[prev] + 1
C[A[i]] = i; // keep track where the last info about A[j] is
}