### sliviu's blog

By sliviu, history, 5 months ago,

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

• +5

By sliviu, history, 14 months ago,

# Background

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.

# The problem

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].

Input:

11 3
1 2 4 3 2 5 6 4 5 2 1
1 6 2
2 7 3
4 11 1


Output:

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?

• +4