Всего чисел, имеющих частоту k в заданном диапазоне

Если количество различных значений в массиве не слишком велико, вы можете рассмотреть возможность хранения массивов такой же длины, как и входной массив, по одному на уникальное значение, подсчитывая количество вхождений значения до каждой точки. Затем вам просто нужно вычесть конечные значения из начальных значений, чтобы найти, сколько существует частотных совпадений:

def range_freq_queries(seq, k, queries):
    n = len(seq)
    c = freq_counts(seq)
    result = [0] * len(queries)
    offset = 0
    for i, (l, r) in enumerate(queries):
        result[i] = range_freq_matches(c, offset, l, r, k, n)
        offset = result[i]
    return result

def freq_counts(seq):
    s = {v: i for i, v in enumerate(set(seq))}
    counts = [None] * (len(seq) + 1)
    counts[0] = [0] * len(s)
    for i, v in enumerate(seq, 1):
        counts[i] = list(counts[i - 1])
        j = s[v]
        counts[i][j] += 1
    return counts

def range_freq_matches(counts, offset, start, end, k, n):
    start, end = sorted(((start + offset) % n, (end + offset) % n))
    num = 0
    return sum(1 for cs, ce in zip(counts[start], counts[end + 1]) if ce - cs == k)

seq = [7, 6, 6, 5, 5]
k = 2
queries = [(0, 4), (3, 0), (4, 1)]
print(range_freq_queries(seq, k, queries))
# [2, 1, 1]

Вы также можете сделать это быстрее с NumPy. Поскольку каждый результат зависит от предыдущего, вам в любом случае придется зацикливаться, но вы можете использовать Numba, чтобы действительно ускорить процесс:

import numpy as np
import numba as nb

def range_freq_queries_np(seq, k, queries):
    seq = np.asarray(seq)
    c = freq_counts_np(seq)
    return _range_freq_queries_np_nb(seq, k, queries, c)

@nb.njit  # This is not necessary but will make things faster
def _range_freq_queries_np_nb(seq, k, queries, c):
    n = len(seq)
    offset = np.int32(0)
    out = np.empty(len(queries), dtype=np.int32)
    for i, (l, r) in enumerate(queries):
        l = (l + offset) % n
        r = (r + offset) % n
        l, r = min(l, r), max(l, r)
        out[i] = np.sum(c[r + 1] - c[l] == k)
        offset = out[i]
    return out

def freq_counts_np(seq):
    uniq = np.unique(seq)
    seq_pad = np.concatenate([[uniq.max() + 1], seq])
    comp = seq_pad[:, np.newaxis] == uniq
    return np.cumsum(comp, axis=0)

seq = np.array([7, 6, 6, 5, 5])
k = 2
queries = [(0, 4), (3, 0), (4, 1)]
print(range_freq_queries_np(seq, k, queries))
# [2 1 2]

Давайте сравним его с исходным алгоритмом:

from collections import Counter

def range_freq_queries_orig(seq, k, queries):
    n = len(seq)
    ans = 0
    counter = Counter()
    out = [0] * len(queries)
    for i, (l, r) in enumerate(queries):
        l += ans
        l %= n
        r += ans
        r %= n
        if l > r:
            l, r = r, l
        counter.clear()
        counter.update(seq[l:r+1])
        ans = sum(1 for v in counter.values() if v == k)
        out[i] = ans
    return out

Вот быстрый тест и время:

import random
import numpy

# Make random input
random.seed(0)
seq = random.choices(range(1000), k=5000)
queries = [(random.choice(range(len(seq))), random.choice(range(len(seq))))
           for _ in range(20000)]
k = 20
# Input as array for NumPy version
seq_arr = np.asarray(seq)
# Check all functions return the same result
res1 = range_freq_queries_orig(seq, k, queries)
res2 = range_freq_queries(seq, k, queries)
print(all(r1 == r2 for r1, r2 in zip(res1, res2)))
# True
res3 = range_freq_queries_np(seq_arr, k, queries)
print(all(r1 == r3 for r1, r3 in zip(res1, res3)))
# True

# Timings
%timeit range_freq_queries_orig(seq, k, queries)
# 3.07 s ± 1.11 s per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit range_freq_queries(seq, k, queries)
# 1.1 s ± 307 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit range_freq_queries_np(seq_arr, k, queries)
# 265 ms ± 726 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

Очевидно, что эффективность этого зависит от характеристик данных. В частности, если повторяющихся значений меньше, затраты времени и памяти на создание таблицы счетчиков будут приближаться к O(n²).

Допустим, входной массив A, |A|=n. Я собираюсь предположить, что количество различных элементов в A намного меньше, чем n.

Мы можем разделить A на сегменты sqrt(n), каждый из которых имеет размер sqrt(n). Для каждого из этих сегментов мы можем рассчитать карту от элемента до счетчика. Построение этих карт занимает O(n) времени.

Выполнив эту предварительную обработку, мы можем ответить на каждый запрос, сложив вместе все карты, полностью содержащиеся в (l,r), которых не более sqrt(n), затем добавив любые дополнительные элементы (или перейдя на один сегмент и вычтя) , а также sqrt(n).

Если есть k различных элементов, это занимает O (sqrt (n) * k), поэтому в худшем случае O (n), если на самом деле каждый элемент A различен.

Вы можете отслеживать элементы, которые имеют желаемое количество, комбинируя хэши и дополнительные элементы.