Oh no, sorting#12371

Oh no, sorting (Анализа на решението)

Problem Author:	Andriy Kholod (Connect)
Prepared by:	Andriy Kholod (Connect)
Analysis:	Andriy Kholod (Connect)

Idea

For each query $[l, r, k]$ [l,r,k], we apply projector sorting to the subarray $a [l .. r]$ , and then we look for $m e x (a [l .. k])$ mex(a[l..k]).

At first glance, this looks like some strange simulation of sorting within many blocks. But there is a very important observation here:

the answer includes all completely covered blocks as they are, and from the last block — only a few smallest elements.

1) How the prefix looks after projector sorting

Let's say we start at position $l$ . Then the subarray $a [l .. r]$ is divided into blocks of lengths $1, 2, 3, \dots$ 1,2,3,\dots until the elements run out.

Let position $k$ lie in some block of length $c$ .

Then all previous blocks fully fit into the prefix $a [l .. k]$ . After sorting, each of them is simply rearranged within itself, but the set of elements in the block does not change. Thus, for $m e x$ , only the presence of numbers matters, not their order.

However, from the block that contains $k$ , only the first $t + 1$ t+1 elements enter the prefix, where $t$ is the position of $k$ within this block.

After sorting the block, these first $t + 1$ t+1 elements are simply the $t + 1$ t+1 smallest elements of the block.

Thus, the answer to the query is the $m e x$ of the set:

all elements from completely covered blocks;
plus the $t + 1$ t+1 smallest elements from the current block.

2) How to process the query

For each query, we find the block that contains $k$ .

Let:

$L$ — the initial $l$ ,
$[L, l - 1]$ [L, l-1] — all completely covered blocks,
$[l, r_{1}]$ [l, r_1] — the block that contains $k$ ,
$k^{'}$ k' — the position of $k$ within this block.

That is:

[l, r] — this is the large part that can be processed offline;
[l1, r1] — a small block from which we need to take only a few smallest;
k — how many elements we take from this block.

3) Why the small block is really small

The sizes of the blocks are $1, 2, 3, \dots$ 1,2,3,\dots. If position $k$ lies in a block of length $c$ , then approximately $1 + 2 + \dots + c = \frac{c ( c + 1 )}{2}$ 1 + 2 + \dots + c = \frac{c(c+1)}{2} elements have already been covered.

From this, we have

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

For $n \leq 2 \cdot 1 0^{5}$ n \le 2 \cdot 10^5, we have $c ≲ 650$ c \lesssim 650, so the block is very small.

That is why we can work with the last block separately directly.

4) What to do with the completely covered part

For all queries, we need to know the set of values in the subarray $a [Q_{l}, ..., Q_{r}] .$ a[Q_l,...,Q_r].

This is a classic offline processing using Mo's algorithm.

Queries are sorted by the left boundary block and the right boundary. Then we maintain the current segment $[l, r]$ [l,r] and the frequency array cnt[x]. For $m e x$ , we need to know which values are present and which are not.

5) How to quickly maintain mex

Since $m e x$ for an array of length no more than $n$ never exceeds $n$ , all values can be trimmed.

This is correct because numbers greater than $n$ will never affect $m e x$ .

Next, the values $0, 1, \dots, n$ 0,1,\dots,n are divided into blocks of length $C = 400$ C=400.

cnt[x] — how many times the number $x$ is present in the current set;
block[b] — how many numbers from this block are present at least once.

Then, to find $m e x$ :

we find the first block where not all $C$ numbers are present;
inside it, we linearly search for the first number with zero frequency.

6) What to do with the last block

The last block is small, so we can simply copy its elements. We only need to take i.k + 1 smallest elements from this block. After copying, it is guaranteed that:

the element at position i.k is in the same position as in the sorted array;
all elements to the left are not greater than it.

Thus, the first i.k+1 elements are indeed some order of the i.k+1 smallest elements of the block. For $m e x$ , the order does not matter; only the set is important, so this is completely sufficient.

8) Asymptotics

Let $B = O (n)$ B = O(\sqrt{n}) — the maximum size of the block for projector sorting.

Mo's algorithm gives the standard complexity $O ((n + q) n)$ O((n+q)\sqrt{n}) for moving the boundaries.
For each query, we also process the small block in $O (B)$ on average using nth_element and a few add/del.

Therefore, the total complexity fits within the bounds: $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++