Общее число с частотой k в заданном диапазоне

Question

Как найти общее число с частотой = k в определенном диапазоне (l, r) в заданном массиве. Всего существует 10 ^ 5 запросов в формате l,r, и каждый запрос строится на основе ответа предыдущего запроса. В частности, после каждого запроса мы увеличиваем l по результату запроса, меняя местами l и r, если l> r. Обратите внимание, что 0<=a[i]<=10^9. Всего элементов в массиве составляет n=10^5.

Моя попытка:

n,k,q = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
for _ in range(q):
    l,r = map(int,input().split())
    l+=ans
    l%=n
    r+=ans
    r%=n
    if l>r:
        l,r = r,l
    d = {}
    for i in a[l:r+1]:
        try:
            d[i]+=1
        except:
            d[i] = 1
    curr_ans = 0
    for i in d.keys():
        if d[i]==k:
            curr_ans+=1
    ans = curr_ans
    print(ans)

Пример ввода:
5 2 3
7 6 6 5 5
0 4
3 0
4 1

Пример вывода:
2
1
1

Answer 1

Скажем, входной массив 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 различен.

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

Answer 2

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

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 ² ).