Сколько смежных подмассивов с макс.n уникальных номеров

Question

Я нашел в Интернете проблему программирования и подумал, есть ли более эффективное решение для этого.

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

Input В первой строке два числа n и x;количество чисел и максимальное количество уникальных чисел в подмассиве.

Пример:

5 2
1 2 3 1 1
ans = 10
explanation: ([1],[2],[3],[1],[1],[1,2],[2,3],[3,1],[1,1],[3,1,1])

Мой подход Перебрать все подмассивы списка с помощью двух циклови подсчитать количество уникальных чисел в соответствующем подмассиве (используя набор).Конечно, должен быть более эффективный способ рассчитать это?Извините, если этот вопрос здесь не относится, не стесняйтесь редактировать его.

РЕДАКТИРОВАТЬ: исправленный код nellex, который иногда дает неправильный ответ

int main() {
    int n, x;
    cin >> n >> x;

    vector<int> a;
    for (int i = 1; i <= n; i++) {
        int b;
        cin >> b;
        a.push_back(b);
    }

    int ans = 0, end = 1;
    set<int> uniq;
    map<int, int> freq;
    for (int start = 0; start < n; start++) {
        cout << start << " and end=" << end << endl;
        while (uniq.size() <= x && end < n) {
            if (uniq.size() == x && freq[a[end]] == 0) {
                break;
            }
            uniq.insert(a[end]);
            freq[a[end]]++;
            end++;
        }
        cout << "added " << end << " - " << start << " to ans" << endl;
        ans += end - start;
        freq[a[start]]--;
        if (freq[a[start]] == 0) {
            uniq.erase(a[start]);
        }
    }
    cout << ans;
}

РЕДАКТИРОВАТЬ: ограничения 1-го теста:

1≤k≤n≤100

1≤xi≤10

Наибольшие ограничения:

1≤k≤n≤5⋅10^5

1≤xi≤10^9

Answer 1

Мы можем решить эту проблему за O(n) время, сохранив два указателя, p_l и p_r, каждый из которых продвигает массив, одновременно обновляя счетчик частоты, h[e], для каждого элемента, с которым мы сталкиваемся.в качестве текущего числа уникальных элементов, k.

Например:

5 2
1 2 3 1 1

Давайте посмотрим на каждую итерацию

k = 0
h = {}
total = 0
p_r = -1
p_l = -1

1:   p_r = 0
     h = {1:1}
     k = 1
     total = 1

2:   p_r = 1
     h = {1:1, 2:1}
     k = 2
     total = 1 + 2 = 3

3:   p_r = 2
     h = {1:1, 2:1, 3:1}
     k = 3

  => move p_l until k equals X:
     p_l = 0
     h = {1:1-1=0, 2:1, 3:1}
     k = 3 - 1 = 2

     total = 3 + 2 = 5

1:   p_r = 3
     h = {1:1, 2:1, 3:1}
     k = 3

  => move p_l until k equals X:
     p_l = 1
     h = {1:1, 2:1-1=0, 3:1}
     k = 3 - 1 = 2

     total = 5 + 2 = 7

1:   p_r = 4
     h = {1:2, 2:0, 3:1}
     k = 2
     total = 7 + 3 = 10

Answer 2

Подход со скользящим окном подойдет как лучшее решение этой проблемы, которое позволит нам решить ее в O (n * log (n)) с использованием набора и карты: https://ideone.com/v2CdZO

int main() {
    int n, x;
    cin >> n >> x;

    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    int end = 0;
    long long ans = 0;

    set<int> uniq;
    map<int, int> freq;
    for(int start = 0; start < n; start++) {
        while(uniq.size() <= x && end < n) {
            if(uniq.size() == x && freq[a[end]] == 0) {
                break;
            }
            uniq.insert(a[end]);
            freq[a[end]]++;
            end++;
        }
        ans += end - start;
        freq[a[start]]--;
        if(freq[a[start]] == 0) {
            uniq.erase(a[start]);
        }
    }
    cout << ans;
}

Алгоритм работает таким образом, что для каждого элемента, определенного индексом start , то есть a[start], мы пытаемся найти самый большой подмассив, начинающийся с start таким, что уникальные элементы в подмассиве <= x </em>.Если размер идентифицированного подмассива равен S, то мы знаем, что элемент a[start] будет частью подмассивов S, начиная с индекса start.

Если мы выполним пробный прогон дляВ данном примере,

• при запуске = 1, мы сгенерируем подмассивы {[1], [1, 2]}
• , когда start = 2, мы 'сгенерируем подмассивы {[2], [2, 3]}
• , когда start = 3, мы сгенерируем подмассивы {[3], [3, 1], [3,1, 1]}
• , когда start = 4, мы сгенерируем подмассивы {[1], [1, 1]}
• , когда start = 5, мы сгенерируемподмассивы {[1]}