Оптимальная сортировка для средних массивов

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
 
 
using t_positions = std::set<unsigned>;
 
 
std::vector<t_positions> prepare(const std::vector<unsigned>& base)
{
    std::vector<t_positions> res(base.size() + 1);
    for (size_t i = 0; i < base.size(); ++i)
        res[base[i]].insert(i);
    return res;
}
 
struct lookup
{
    unsigned left;
    unsigned right;
    bool operator<(lookup r) const { return left < r.left || (left == r.left && right < r.right); }
    bool operator==(lookup r) const { return left == r.left && right == r.right; }
 
    unsigned distance(unsigned pos) const
    {
        if (left <= pos && right >= pos)
            return 0;
        if (pos < left)
            return left - pos;
        return pos - right;
    }
 
    bool contains(const lookup in) const
    {
        return left <= in.left && right >= in.right;
    }
};
 
std::vector<std::set<lookup>> lookups;
 
 
 
void build_lookups(const std::vector<t_positions>& mapper)
{
    // clean up
    lookups.resize(mapper.size());
    for (auto& l : lookups)
    {
        if(l.empty())
            break;
        l.clear();
    }
 
 
    for (unsigned pos : mapper[0])
    {
        lookup look{pos, pos};
        lookups[0].insert(look);
    }
 
    for (unsigned i = 1; i < mapper.size(); ++i)
    {
        for (unsigned pos : mapper[i])
        {
            lookup closest;
            bool initialized = false;
            auto start = lookups[i - 1].lower_bound({ pos, pos });
            if(start!=lookups[i - 1].begin())
            {
                --start;
                start = lookups[i - 1].lower_bound({ start->left, start->left });
            }
            auto stop = lookups[i - 1].upper_bound({ pos, pos });
            for (auto iter = start; iter!=lookups[i-1].end(); ++iter)
            {
                const lookup prev = *iter;
                if (!initialized)
                {
                    closest = prev;
                    initialized = true;
                    if (iter == stop)
                        break;
                    continue;
                }
                const unsigned prev_dist = prev.distance(pos),
                               curr_dist = closest.distance(pos);
                if (prev_dist < curr_dist)
                {
                    closest = prev;
                    if (iter == stop)
                        break;
                    continue;
                }
                if (prev_dist == curr_dist && prev.right - prev.left < closest.right - closest.left)
                {
                    closest = prev;
                }
                if(iter==stop)
                    break;
            }
            if (initialized)
            {
                unsigned l = std::min(pos, closest.left);
                unsigned r = std::max(pos, closest.right);
                lookup adding{l, r};
                bool add = true;
 
                auto iter = lookups[i].lower_bound(adding);
                while(iter!= lookups[i].end() && iter->left<=adding.right)
                {
                    if(adding.contains(*iter))
                    {
                        add = false;
                        break;
                    }
                }
 
                if (add)
                    lookups[i].insert(adding);
            }
        }
        if (lookups[i].empty())
            break;
    }
}
 
void update_lookups(size_t upd_pos, unsigned val, const std::vector<t_positions>& mapper)
{
    for (unsigned i = val; i < mapper.size(); ++i)
    {
        if(lookups[i].empty())
            break;
        lookups[i].clear();
    }
    for (unsigned i = val; i < mapper.size(); ++i)
    {
        for (unsigned pos : mapper[i])
        {
            lookup closest;
            bool initialized = false;
            auto start = lookups[i - 1].lower_bound({ pos, pos });
            if (start != lookups[i - 1].begin())
            {
                --start;
                start = lookups[i - 1].lower_bound({ start->left, start->left });
            }
            auto stop = lookups[i - 1].upper_bound({ pos, pos });
            for (auto iter = start; iter != lookups[i - 1].end(); ++iter)
            {
                const lookup prev = *iter;
                if (!initialized)
                {
                    closest = prev;
                    initialized = true;
                    continue;
                }
                const unsigned prev_dist = prev.distance(pos),
                    curr_dist = closest.distance(pos);
                if (prev_dist < curr_dist)
                {
                    closest = prev;
                    continue;
                }
                if (prev_dist == curr_dist && prev.right - prev.left < closest.right - closest.left)
                {
                    closest = prev;
                }
                if (iter == stop)
                    break;
            }
            if (initialized)
            {
                unsigned l = std::min(pos, closest.left);
                unsigned r = std::max(pos, closest.right);
                lookup adding{ l, r };
                bool add = true;
 
                auto iter = lookups[i].lower_bound(adding);
                while (iter != lookups[i].end() && iter->left <= adding.right)
                {
                    if (adding.contains(*iter))
                    {
                        add = false;
                        break;
                    }
                }
 
                if (add)
                    lookups[i].insert(adding);
            }
        }
        if (lookups[i].empty())
            break;
    }
}
 
void replace(size_t pos, unsigned value, std::vector<unsigned>& arr, std::vector<t_positions>& mapper)
{
    unsigned old = arr[pos];
    if (old == value)
        return;
    arr[pos] = value;
 
    mapper[old].erase(pos);
    mapper[value].insert(pos);
 
    if (old == 0 || value == 0)
        build_lookups(mapper);
    else
        update_lookups(pos, std::min(old, value), mapper);
}
 
/// Both inclusive
bool is_set_contains(const t_positions& positions, size_t left, size_t right)
{
    if (positions.empty())
        return false;
    const auto iter = positions.lower_bound(left);
    if (iter == positions.end() || *iter > right)
        return false;
    return true;
}
 
bool check_look_up(unsigned val, lookup range, const std::vector<std::set<lookup>>& lookups)
{
    const std::set<lookup>& look = lookups[val];
    auto start = look.lower_bound(range);
    if(start!=look.begin())
    {
        --start;
        start = look.lower_bound({ start->left, start->left });
    }
    while(start!=look.end() && range.right>start->left)
    {
        if (range.contains(*start))
            return true;
        ++start;
    }
    return  false;
}
 
unsigned find_start(const std::vector<std::set<lookup>>& lookups, unsigned left, unsigned right)
{
    unsigned lower = 0, upper = right - left;
    lookup current{left, right};
    if (!check_look_up(0, current, lookups))
        return 0;
    if (check_look_up(upper, current, lookups))
        return upper;
    do
    {
        unsigned middle = (static_cast<unsigned long long>(lower) + upper) >> 1;
        bool contains_all_lower = check_look_up(middle, current, lookups);
        if (contains_all_lower)
            lower = middle + 1;
        else
            upper = middle;
    } while (upper - lower>5);
    return lower;
}
 
size_t first_lost(unsigned left, unsigned right, const std::vector<t_positions>& mapper)
{
    size_t start = find_start(lookups, left, right);
 
    for (size_t i = start; i < mapper.size(); ++i)
        if (!is_set_contains(mapper[i], left, right))
        {
            return i;
        }
    return mapper.size();
}
 
 
int main()
{
    size_t n;
    size_t number_of_commands;
    std::cin >> n;
    std::cin >> number_of_commands;
    std::vector<unsigned> arr(n);
    for (unsigned& v : arr)
        std::cin >> v;
    std::vector<t_positions> mapper = prepare(arr);
    build_lookups(mapper);
    std::vector<unsigned> prints;
    prints.reserve(number_of_commands);
    for (size_t i = 0; i < number_of_commands; ++i)
    {
        char cmd;
        std::cin >> cmd;
        if (cmd == '?')
        {
            size_t l, r;
            std::cin >> l >> r;
            prints.push_back(first_lost(l - 1, r - 1, mapper));
        }
        else
        {
            unsigned value;
            size_t pos;
            std::cin >> pos >> value;
            replace(pos - 1, value, arr, mapper);
        }
    }
 
    for (unsigned v : prints)
        std::cout << v << '\n';
}

//curr_right == -1 означает, что были изменения, элемента под номером curr_left как было описано выше.
 
//выполнение этого условия значит, что в введенном диапазоне были изменения и в нем число надо искать заново
(curr_right == -1 && input_left <= curr_left && input_right >= curr_left) 
 
//а выполнение это означает, что нужно просто вывести результат
(curr_left == input_left && curr_right == input_right)