Количество вхождений каждого отдельного целого в заданных диапазонах для массива - PullRequest
Новая
       40

Количество вхождений каждого отдельного целого в заданных диапазонах для массива

2 голосов
/ 14 июня 2019

Задан массив из n целых чисел (n <= 1e6) [a0, a1, a2, ... an-1] (a[i] <= 1e9) и нескольких запросов.В каждом запросе дано 2 целых чисел l и r (0 <= l <= r <= n-1), и нам необходимо вернуть количество каждого отдельного целого числа в этом диапазоне (l и r включительно).

Я могу предложить только грубое решение для перебора всего диапазона для каждого запроса. 

d={}
for i in range(l, r+1):
    if arr[i] not in d:
        d[arr[i]]=0
    d[arr[i]]+=1

Например: 

Array is [1, 1, 2, 3, 1, 2, 1]

Query 1: l=0, r=6, Output: 4, 2, 3 (4 for 4 1's, 2, for 2 2's and 1 for 1 3)
Query 2: l=3, r=5, Output: 1, 1, 1

Правка - я придумал что-то вроде этогоно все же его сложность довольно высока.Я думаю, что из-за этой операции вставки. 

const ll N = 1e6+5;
ll arr[N];
unordered_map< ll, ll > tree[4 * N];
int n, q;

void build (ll node = 1, ll start = 1, ll end = n) {
    if (start == end) {
        tree[node][arr[start]] = 1;
        return;
    }
    ll mid = (start + end) / 2;
    build (2 * node, start, mid);
    build (2 * node + 1, mid + 1, end);
    for (auto& p : tree[2 * node]) {
        ll x = p.ff;
        ll y = p.ss;
        tree[node][x] += y;
    }
    for (auto& p : tree[2 * node + 1]) {
        ll x = p.ff;
        ll y = p.ss;
        tree[node][x] += y;
    }
}

vector< ll > query (ll node, ll l, ll r, ll start = 1, ll end = n) {
    vector< ll > ans;
    if (end < l or start > r) return ans;
    if (start >= l and end <= r) {
        for (auto p : tree[node]) {
            ans.push_back (p.ss);
        }
        return ans;
    }
    ll mid = (start + end) / 2;
    vector< ll > b = query (2 * node, l, r, start, mid);
    ans.insert (ans.end (), b.begin (), b.end ());
    b = query (2 * node + 1, l, r, mid + 1, end);
    ans.insert (ans.end (), b.begin (), b.end ());
    return ans;
}

Ответы [ 3 ]

0 голосов
/ 15 июня 2019

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

Запросы q каждого сегмента будут иметь не более O(q * sqrt(n)) изменений из-за каждого движения в l и не более O(n) изменений из-за постепенного изменения в r (поскольку мы отсортировали каждый сегмент по r, эта сторона интервала только неуклонно увеличивается, когда мы обрабатываем ведро).

Обработка изменений в правой части всех интервалов в одном сегменте связана с O(n), и у нас есть sqrt(n) сегментов, так что для правой стороны это O(n * sqrt(n). А поскольку число всех q s равно O(n) (предполагается), и для каждого требуется максимум O(sqrt(n)) изменений на левой стороне, изменения для левой стороны также составляют O(n * sqrt(n)).

Таким образом, общая сложность времени составит O(n * sqrt(n) + k), где k - общее количество выводимых чисел. (Обновленная структура данных может быть хэш-картой, которая также позволяет выполнять итерации в текущем хранилище.)

0 голосов
/ 15 июня 2019

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

0 голосов
/ 15 июня 2019

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

Теперь запросите дерево с помощью ввода x, чтобы найти карту для представления частот встречаемости каждого элемента в соответствующем префиксе индекса [1..i]. Это потребует слияния O (log n) карт.

Теперь вы можете сделать два запроса: один для l-1, а другой для r. «Вычтите» первую карту результата из второй. Вычитание карты начальное. Я позволю вам разобраться в деталях.

Время для каждого запроса будет O (k log n), где k - размер карты. Это будет самое большее количество различных элементов во входном массиве.

...