A logarithmic solution instead of sqrt decomposition

Правка en4, от sliviu, 2020-09-07 19:45:43

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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский sliviu 2020-09-07 19:45:43 8
en3 Английский sliviu 2020-09-07 19:40:39 12
en2 Английский sliviu 2020-09-07 19:39:53 4
en1 Английский sliviu 2020-09-07 19:39:37 1048 Initial revision (published)