Oh yox, sıralama#12371

Oh yox, sıralama (Həll təhlili)

Problem Müəllifi:	Andriy Kholod (Connect)
Hazırlayan:	Andriy Kholod (Connect)
Analiz:	Andriy Kholod (Connect)

Fikir

Hər bir sorğu üçün $[l, r, k]$ [l,r,k], biz $a [l .. r]$ alt massivinə proyektor sıralaması tətbiq edirik və sonra $m e x (a [l .. k])$ mex(a[l..k]) axtarırıq.

İlk baxışda, bu, bir çox blok daxilində sıralamanın qəribə bir simulyasiyası kimi görünür. Amma burada çox vacib bir müşahidə var:

cavab tamamilə örtülmüş blokları olduğu kimi, və son blokdan — yalnız bir neçə ən kiçik elementi əhatə edir.

1) Proyektor sıralamasından sonra prefiks necə görünür

Gəlin $l$ mövqeyindən başlayaq. Sonra $a [l .. r]$ alt massivi uzunluqları $1, 2, 3, \dots$ 1,2,3,\dots olan bloklara bölünür. Elementlər bitənə qədər.

Gəlin $k$ mövqeyi uzunluğu $c$ olan bir blokda olsun.

Onda bütün əvvəlki bloklar tamamilə $a [l .. k]$ prefiksinə sığır. Sıraladıqdan sonra, hər biri sadəcə öz içində yenidən düzülür, amma blokdakı elementlərin dəsti dəyişmir. Beləliklə, $m e x$ üçün yalnız ədədlərin mövcudluğu vacibdir, onların sırası deyil.

Amma $k$ -ni ehtiva edən blokdan yalnız ilk $t + 1$ t+1 element prefikse daxil olur, burada $t$ bu blokdakı $k$ -nin mövqeyidir.

Bloku sıraladıqdan sonra, bu ilk $t + 1$ t+1 elementlər sadəcə blokun $t + 1$ t+1 ən kiçik elementidir.

Beləliklə, sorğunun cavabı aşağıdakı dəstin $m e x$ -idir:

tamamilə örtülmüş bloklardan bütün elementlər;
üstəlik, cari blokdan $t + 1$ t+1 ən kiçik elementlər.

2) Sorğunu necə işləmək olar

Hər bir sorğu üçün $k$ -ni ehtiva edən bloku tapırıq.

Gəlin:

$L$ — ilkin $l$ ,
$[L, l - 1]$ [L, l-1] — tamamilə örtülmüş bloklar,
$[l, r_{1}]$ [l, r_1] — $k$ -ni ehtiva edən blok,
$k^{'}$ k' — bu blokdakı $k$ -nin mövqeyi.

Yəni:

[l, r] — bu, offline işlənə bilən böyük hissədir;
[l1, r1] — yalnız bir neçə ən kiçik element götürməli olduğumuz kiçik blok;
k — bu blokdan neçə element götürəcəyimiz.

3) Niyə kiçik blok həqiqətən kiçikdir

Blokların ölçüləri $1, 2, 3, \dots$ 1,2,3,\dots. Əgər $k$ mövqeyi uzunluğu $c$ olan bir blokda yerləşirsə, deməli təxminən $1 + 2 + \dots + c = \frac{c ( c + 1 )}{2}$ 1 + 2 + \dots + c = \frac{c(c+1)}{2} element artıq örtülmüşdür.

Bundan, bizdə

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

$n \leq 2 \cdot 1 0^{5}$ n \le 2 \cdot 10^5 üçün, $c ≲ 650$ c \lesssim 650 olur, yəni blok çox kiçikdir.

Ona görə də son blokla birbaşa ayrıca işləyə bilərik.

4) Tamamilə örtülmüş hissə ilə nə etmək lazımdır

Bütün sorğular üçün, $a [Q_{l}, ..., Q_{r}]$ a[Q_l,...,Q_r] alt massivindəki dəyərlər dəstini bilmək lazımdır.

Bu, Mo-nun alqoritmi istifadə edərək klassik offline işləmədir.

Sorğular sol sərhəd blokuna və sağ sərhədə görə sıralanır. Sonra cari seqmenti $[l, r]$ [l,r] və tezlik massivini cnt[x] saxlayırıq. $m e x$ üçün, hansı dəyərlərin mövcud olduğunu və hansının olmadığını bilmək lazımdır.

5) Mex-i necə tez saxlamaq olar

$M e x$ uzunluğu $n$ -dən çox olmayan bir massiv üçün heç vaxt $n$ -i aşmadığı üçün, bütün dəyərləri kəsmək olar.

Bu doğrudur, çünki $n$ -dən böyük ədədlər heç vaxt $m e x$ -ə təsir etməyəcək.

Sonra, $0, 1, \dots, n$ 0,1,\dots,n dəyərləri uzunluğu $C = 400$ C=400 olan bloklara bölünür.

cnt[x] — cari dəstdə $x$ ədədinin neçə dəfə olduğunu;
block[b] — bu blokdan ən azı bir dəfə olan ədədlərin sayı.

Sonra, $m e x$ -i tapmaq üçün:

ilk blokda bütün $C$ ədədlərin mövcud olmadığı yeri tapırıq;
onun içində, sıfır tezliyi olan ilk ədədi xətti axtarırıq.

6) Son blokla nə etmək lazımdır

Son blok kiçikdir, ona görə də sadəcə onun elementlərini kopyalaya bilərik. Bu blokdan yalnız i.k + 1 ən kiçik elementləri götürməliyik. Kopyaladıqdan sonra, zəmanət verilir ki:

i.k mövqeyindəki element sıralanmış massivdəki eyni mövqedədir;
soldakı bütün elementlər ondan böyük deyil.

Beləliklə, ilk i.k+1 elementlər həqiqətən blokun i.k+1 ən kiçik elementlərinin bir sırasıdır. $M e x$ üçün, sıralama vacib deyil; yalnız dəst vacibdir, buna görə də bu tamamilə kifayətdir.

8) Asimptotiklər

Gəlin $B = O (n)$ B = O(\sqrt{n}) — proyektor sıralaması üçün maksimum blok ölçüsü.

Mo-nun alqoritmi sərhədləri hərəkət etdirmək üçün standart mürəkkəbliyi $O ((n + q) n)$ O((n+q)\sqrt{n}) verir.
Hər bir sorğu üçün, biz də kiçik bloku $O (B)$ ortalama olaraq nth_element və bir neçə add/del istifadə edərək işləyirik.

Buna görə də, ümumi mürəkkəblik sərhədlərə uyğun gəlir: $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 sıfırdan
        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++