Количество появлений числа во всех запросах?

Question

Возьмите несортированный массив, например:

4,5,1,2,3,7,8,3

, а запросы будут такими:

[1 2] [5 5] [2 6] [6 6] [1 6] [1 5]

, где каждый запрос представляет интервал индексов.

Длина массива и общее количество запросов может быть до 100000 .

Я хочу рассчитать количество вхождений каждого индекса в каждом из запросов, как показано ниже:

вхождения 1: 3

вхождения 3: 3

вхождения 5: 4, et c

Любой оптимальный способ выполнить это? Я пытался наивно, но мне нужно несколько советов для оптимального решения.

Answer 1

Вы можете решить это с помощью BIT (дерево двоичных индексов) или Дерево сегментов ..

Я прикрепил две ссылки там, чтобы узнать об этих алгоритмах .. .

BIT решение:

Для каждого запроса можно указать диапазон: [l r]:

• Теперь вам нужно обновить в BIT l to n со значением 1.
• Теперь вам нужно исключить обновление r+1 to n ... поэтому обновите r+1 to n со значением -1 в BIT ..

Каждое обновление log операции (n) в битах ...

Рассчитать количество вхождений для каждого индекса:

Call sum(index) in BIT to get count

Эта операция принимает log (n) времени ..

Сложность:

сложность этого решения: Q*(log(n)+log(n)) + N *(log(n)) ..

Код:

#include <bits/stdc++.h>
using namespace std;
int tree[100005], A[100005];

void update(int idx, int n, int v) {
    while (idx <= n) {
        tree[idx] += v;
        idx += (idx & -idx);
    }
}

int sum(int idx) {
    int res = 0;
    while (idx) {
        res += tree[idx];
        idx -= (idx & -idx);
    }
    return res;
}

int main() {
    int n, q, i, l, r;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d", &q);
    memset(tree, 0, sizeof(tree));
    while (q--) {
        scanf("%d%d", &l, &r);
        update(l,n,1);
        update(r+1,n,-1);
    }
    for (i = 1; i <= n; i++) {
        printf("%d\n", sum(i));
    }
    return 0;
}