Background

Square root decomposition/Mo's algorithm is a known method 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:

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 (N log^2 N) solution for this problem?