A logarithmic solution instead of sqrt decomposition

Revision en2, by sliviu, 2020-09-07 19:39:53

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English sliviu 2020-09-07 19:45:43 8
en3 English sliviu 2020-09-07 19:40:39 12
en2 English sliviu 2020-09-07 19:39:53 4
en1 English sliviu 2020-09-07 19:39:37 1048 Initial revision (published)