Неповний колір#13095

Неповний колір (Розбір)

Ідея

Потрібно порахувати кількість підмасивів, у яких рівно один колір є неповним.

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

Найпростіше рішення — перебрати всі підмасиви та підтримувати кількість неповних кольорів. Проте таке рішення працюватиме за $O (n^{2})$ O(n^2), чого недостатньо.

Натомість будемо фіксувати праву межу $r$ та рахувати кількість підходящих лівих меж $l$ .

Ключове спостереження

Для фіксованої правої межі $r$ позначимо через $f (l)$ кількість неповних кольорів у підмасиві $[l, r]$ [l,r].

Нам потрібно порахувати кількість позицій $l$ , для яких

f (l) = 1.

f(l)=1.

Будемо підтримувати ці значення, поступово пересуваючи праву межу $r$ зліва направо.

Для кожного кольору $c$ попередньо знайдемо:

$f i r s t_{c}$ first_c — позицію першого входження кольору.
$l a s t_{c}$ last_c — позицію останнього входження кольору.
$p r e v_{c}$ prev_c — позицію останнього входження кольору перед поточною позицією, спочатку $0$ .

Нехай ми додаємо до поточного підмасиву елемент $a_{r} = c$ a_r=c.

Розглянемо всі ліві межі, для яких

p r e v_{c} < l \leq r .

prev_c<l\leq r.

Для таких підмасивів колір $c$ раніше був відсутній, а тепер з'явився.

Тому спочатку вважатимемо його неповним і збільшимо $f (l)$ на одиницю на відрізку

[p r e v_{c} + 1, r] .

[prev_c+1,r].

Однак, якщо $r = l a s t_{c}$ r=last_c, ми щойно додали останнє входження цього кольору.

Для кожного $l \leq f i r s t_{c}$ l\leq first_c підмасив тепер містить усі входження кольору $c$ , тому він більше не є неповним.

Отже, потрібно зменшити $f (l)$ на одиницю на відрізку

[1, f i r s t_{c}] .

[1,first_c].

Зауважимо, що ці дві операції правильно обробляють навіть кольори, які зустрічаються рівно один раз: у такому випадку їхні внески просто компенсуються.

Таким чином, для кожної позиції $r$ нам потрібно виконати не більше двох додавань на відрізку.

Розв'язок

Нам потрібна структура даних, яка підтримує дві операції:

Додавання $1$ або $- 1$ до всіх значень на відрізку.
Підрахунок кількості значень, що дорівнюють $1$ .

Для цього використаємо дерево відрізків із лінивим оновленням.

У кожній вершині будемо зберігати:

$mn$ — мінімальне значення на відрізку.
$c n t$ — кількість входжень цього мінімуму.
$c n t 1$ — кількість значень, що дорівнюють $mn + 1$ mn+1.
$l a z y$ — відкладене додавання.

Якщо ми додаємо одне й те саме число до всіх елементів відрізка, змінюються лише $mn$ та $l a z y$ . Значення $c n t$ і $c n t 1$ залишаються незмінними.

Також можемо об'єднувати інформацію двох дочірніх вершин за $O (1)$ .

Мінімум батьківської вершини дорівнює меншому з мінімумів її дітей.

Щоб порахувати $c n t$ , додаємо кількості мінімумів тих дітей, у яких мінімум дорівнює мінімуму батьківської вершини.

Для обчислення $c n t 1$ кожна дочірня вершина робить такий внесок:

Якщо її мінімум дорівнює мінімуму батьківської вершини, додаємо її $c n t 1$ .
Якщо її мінімум на одиницю більший за мінімум батьківської вершини, додаємо її $c n t$ .
В інших випадках нічого не додаємо.

Отже, кожне додавання на відрізку можна виконати за $O (lo g n)$ O(\log n).

Спочатку всі значення $f (l)$ дорівнюють нулю.

Після обробки позиції $r$ ми змінюємо лише значення для $l \leq r$ l\leq r. Усі інші позиції залишаються нульовими та не впливають на відповідь.

Крім того, після обробки всього масиву $f (1) = 0$ f(1)=0, оскільки весь масив містить усі входження кожного кольору.

Таким чином, глобальний мінімум завжди дорівнює нулю.

Отже, значення $c n t 1$ у корені дерева відрізків дорівнює кількості підмасивів із правою межею $r$ , які містять рівно один неповний колір.

Після обробки кожної позиції додаємо це значення до відповіді.

Асимптотика

Ми обробляємо всі $n$ позицій масиву, виконуючи не більше двох оновлень дерева відрізків для кожної позиції.

Кожне оновлення працює за $O (lo g n)$ O(\log n).

Отже, загальна часова складність становить $O (n lo g n)$ O(n\log n).

Дерево відрізків та допоміжні масиви потребують $O (n)$ додаткової пам'яті.

Оскільки відповідь може мати порядок $O (n^{2})$ O(n^2), необхідно використовувати 64-бітний цілочисельний тип.

Реалізація

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e5 + 7;

int a[N], fst[N], lst[N], prv[N];
int mn[4 * N], cnt[4 * N], cnt1[4 * N], lazy[4 * N];

void build(int v, int l, int r) {
    cnt[v] = r - l + 1;

    if (l == r) return;

    int mid = (l + r) / 2;
    build(v * 2, l, mid);
    build(v * 2 + 1, mid + 1, r);
}

void pull(int v) {
    int x = v * 2, y = v * 2 + 1;

    mn[v] = min(mn[x], mn[y]);
    cnt[v] = cnt1[v] = 0;

    if (mn[x] == mn[v]) {
        cnt[v] += cnt[x];
        cnt1[v] += cnt1[x];
    } else if (mn[x] == mn[v] + 1) {
        cnt1[v] += cnt[x];
    }

    if (mn[y] == mn[v]) {
        cnt[v] += cnt[y];
        cnt1[v] += cnt1[y];
    } else if (mn[y] == mn[v] + 1) {
        cnt1[v] += cnt[y];
    }
}

void push(int v) {
    if (!lazy[v]) return;

    int x = v * 2, y = v * 2 + 1;

    mn[x] += lazy[v];
    mn[y] += lazy[v];

    lazy[x] += lazy[v];
    lazy[y] += lazy[v];

    lazy[v] = 0;
}

void upd(int v, int l, int r, int ql, int qr, int val) {
    if (ql > qr) return;

    if (ql <= l && r <= qr) {
        mn[v] += val;
        lazy[v] += val;
        return;
    }

    push(v);

    int mid = (l + r) / 2;

    if (ql <= mid)
        upd(v * 2, l, mid, ql, qr, val);

    if (qr > mid)
        upd(v * 2 + 1, mid + 1, r, ql, qr, val);

    pull(v);
}

void solve() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];

        if (!fst[a[i]]) fst[a[i]] = i;
        lst[a[i]] = i;
    }

    build(1, 1, n);

    ll ans = 0;

    for (int r = 1; r <= n; r++) {
        int c = a[r];

        upd(1, 1, n, prv[c] + 1, r, 1);

        if (r == lst[c]) {
            upd(1, 1, n, 1, fst[c], -1);
        }

        prv[c] = r;

        ans += cnt1[1];
    }

    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}

C++