Could someone please help me with this problem? I've been thinking about it for over a week but I still have no idea how to solve it. Thank you
Square root decomposition / Mo's algorithm is a known method used to solve a large variety of problems in O(N sqrt(N)). However, it is not used all that often by more experience programmers because we can use a BIT or segment tree instead and attain logarithmic time. However, I've recently stumbled upon problem which I only know how to solve using sqrt decomposition.
You are given an array A with N elements (indexing starts from 1). You need to answer M queries of the type: "Given three indices l r k, find the number of elements which appear exactly k times in the subarray A[l], A[l+1], ..., A[r].
11 3 1 2 4 3 2 5 6 4 5 2 1 1 6 2 2 7 3 4 11 1
1 0 4
I've tried implementing online/offline solutions using persistent segments and binary indexed trees, but to no avail. Is there a O(N logN) or O(N log^2 N) solution for this specific problem?