О ні, сортування#12371

О ні, сортування (Розбір)

Автор задачі:	Андрій Холод (Connect)
Підготував:	Андрій Холод (Connect)
Розбір:	Андрій Холод (Connect)

Ідея

Для кожного запиту $[l, r, k]$ [l,r,k] ми застосовуємо прожекторне сортування до підвідрізка $a [l .. r]$ , а потім шукаємо $m e x (a [l .. k])$ mex(a[l..k]).

На перший погляд це виглядає як якась дивна симуляція сортувань усередині багатьох блоків. Але тут є дуже важливе спостереження:

у відповідь входять усі повністю покриті блоки як є, а з останнього блока — лише кілька найменших елементів.

1) Як виглядає префікс після прожекторного сортування

Нехай ми починаємо в позиції $l$ . Тоді підвідрізок $a [l .. r]$ розбивається на блоки довжин $1, 2, 3, \dots$ 1,2,3,\dots поки елементи не закінчаться.

Нехай позиція $k$ лежить у деякому блоці довжини $c$ .

Тоді всі попередні блоки цілком потрапляють у префікс $a [l .. k]$ . Після сортування кожен із них просто переставляється всередині себе, але множина елементів блока не змінюється. Отже для $m e x$ важлива лише наявність чисел, а не їхній порядок.

А от із блока, який містить $k$ , у префікс потрапляють лише перші $t + 1$ t+1 елементів, де $t$ — позиція $k$ всередині цього блока.

Після сортування блока ці перші $t + 1$ t+1 елементів — це просто $t + 1$ t+1 найменших елементів блока.

Отже відповідь на запит — це $m e x$ множини:

усіх елементів із повністю покритих блоків;
плюс $t + 1$ t+1 найменших елементів з поточного блока.

2) Як опрацьовувати запит

Для кожного запиту знаходимо блок, у якому лежить $k$ .

Нехай:

$L$ — початковий $l$ ,
$[L, l - 1]$ [L, l-1] — усі повністю покриті блоки,
$[l, r_{1}]$ [l, r_1] — блок, який містить $k$ ,
$k^{'}$ k' — позиція $k$ всередині цього блока.

Тобто:

[l, r] — це велика частина, яку можна обробляти офлайн;
[l1, r1] — маленький блок, з якого треба взяти лише кілька найменших;
k — скільки саме елементів беремо з цього блока.

3) Чому маленький блок справді маленький

Розміри блоків — це $1, 2, 3, \dots$ 1,2,3,\dots. Якщо позиція $k$ лежить у блоці довжини $c$ , то до нього вже покрито приблизно $1 + 2 + \dots + c = \frac{c ( c + 1 )}{2}$ 1 + 2 + \dots + c = \frac{c(c+1)}{2} елементів.

Звідси

$c = O (n) .$ c = O(\sqrt{n}).

При $n \leq 2 \cdot 1 0^{5}$ n \le 2 \cdot 10^5 маємо $c ≲ 650$ c \lesssim 650, тому блок дуже маленький.

Саме тому з останнім блоком можна працювати окремо напряму.

4) Що робимо з повністю покритою частиною

Для всіх запитів треба знати множину значень на підвідрізку $a [Q_{l}, ..., Q_{r}] .$ a[Q_l,...,Q_r].

Це класична офлайн-обробка через Mo's algorithm.

Запити сортуються за блоком лівої межі та правою межею. Далі ми підтримуємо поточний відрізок $[l, r]$ [l,r] і масив частот cnt[x]. Для $m e x$ треба знати, які значення присутні, а які ні.

5) Як швидко підтримується mex

Оскільки $m e x$ для масиву довжини не більше $n$ ніколи не перевищує $n$ , усі значення можна обрізати.

Це коректно, бо числа більші за $n$ ніколи не вплинуть на $m e x$ .

Далі значення $0, 1, \dots, n$ 0,1,\dots,n діляться на блоки довжини $C = 400$ C=400.

cnt[x] — скільки разів число $x$ входить у поточну множину;
block[b] — скільки чисел із цього блоку присутні хоча б раз.

Тоді, щоб знайти $m e x$ :

знаходимо перший блок, де не всі $C$ чисел присутні;
всередині нього лінійно шукаємо перше число з нульовою частотою.

6) Що робимо з останнім блоком

Останній блок малий, тому можна просто скопіювати його елементи. Потрібно взяти лише i.k + 1 найменших елементів цього блока. Після копіювання гарантується, що:

елемент на позиції i.k стоїть так, як у відсортованому масиві;
усі елементи лівіше не більші за нього.

Тобто перші i.k+1 елементів — це саме деякий порядок із i.k+1 найменших елементів блока. Для $m e x$ порядок неважливий, важлива лише множина, тому цього повністю достатньо.

8) Асимптотика

Нехай $B = O (n)$ B = O(\sqrt{n}) — максимальний розмір блока прожекторного сортування.

Mo's algorithm дає стандартну складність $O ((n + q) n)$ O((n+q)\sqrt{n}) на пересування меж.
Для кожного запиту ми ще обробляємо малий блок за $O (B)$ у середньому через nth_element та кілька add/del.

Тому загальна складність укладається в обмеження: $O ((n + q) n)$ O((n+q)\sqrt{n}).

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 2e5 + 11, inf = 1000111222;


int a[max_n];

const int C = 400;

int id[max_n];


struct seg {
    int l, r;
    int l1, r1, k;
    int id;

    bool operator < (const seg &x) const {
        if (::id[l] != ::id[x.l]) {
            return l < x.l;
        }
        return r < x.r;
    }
};


int cnt[max_n];
int block[max_n / C + 11];


int val[1000];

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < max_n; i++) {
        id[i] = i / C;
    }

    int n, q;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        umin(a[i], n);
    }
    cin >> q;
    vector <seg> Q(q);
    vector <int> ans(q);
    for (int i = 0, l, r, k; i < q; i++) {
        cin >> l >> r >> k;
        --l, --r, --k;
        k = k - l;
        // k from zero
        k += l;
        int c = 1;
        int L = l;
        while (l + c - 1 < k) {
            l += c;
            ++c;
        }
        Q[i].id = i;
        Q[i].l = L;
        Q[i].r = l - 1;
        Q[i].l1 = l;
        Q[i].r1 = min(r, l + c - 1);
        Q[i].k = k - l;
    }
    sort(all(Q));
    int l = 0, r = -1;
    auto add = [&] (int x) {
        LOG("+", x);
        if (cnt[x]++ == 0) {
            ++block[id[x]];
        }
    };
    auto del = [&] (int x) {
        LOG("-", x);
        if (--cnt[x] == 0) {
            --block[id[x]];
        }
    };
    for (auto &i : Q) {
        LOG(i.l, i.r, l, r);
        while (i.r > r) {
            ++r;
            add(a[r]);
        }
        while (l > i.l) {
            --l;
            add(a[l]);
        }
        while (i.r < r) {
            del(a[r]);
            --r;
        }
        while (l < i.l) {
            del(a[l]);
            ++l;
        }

        assert(i.r1 - i.l1 + 1 <= 1000);
        for (int j = i.l1; j <= i.r1; j++) {
            val[j - i.l1] = a[j];
        }
        nth_element(val, val + i.k, val + (i.r1 - i.l1 + 1));
        for (int j = 0; j <= i.k; j++) {
            add(val[j]);
        }
        int res = 0;

        while (block[res] == C) {
            ++res;
        }
        res *= C;
        while (cnt[res]) {
            ++res;
        }
        LOG(i.id, cnt[0]);

        ans[i.id] = res;


        for (int j = 0; j <= i.k; j++) {
            del(val[j]);
        }
    }
    for (auto &i : ans) {
        cout << i << '\n';
    }
}

/*
KoRoVa!
*/

C++