Какой эффективный способ проверить, отсортированы ли некоторые подмассивы или нет, когда есть несколько запросов?

Question

Предположим, массив A = {5, 4, 3, 7, 9, 11, 2}.Есть K количество запросов.В каждом запросе мне будут даны два целых числа L и R, где 0 <= L <= R < N (где N - размер массива).Я должен сказать, отсортирован ли подмассив A[L...R].

Например, 1-й запрос запрашивает у меня, отсортирован ли под массив с индексом от 0 до 6 (индекс на основе 0) или нет.Ответ: A[0...6] не отсортировано.Затем второй запрос спрашивает меня, отсортирован ли A[2...5] или нет.Этот под-массив отсортирован.Вот как я подошел к нему.Есть ли лучший подход?

int main()
{
    int a[7] = { 5, 4, 3, 7, 9, 11, 2}, k = 2;

    for(int i = 1; i <= k; i++)
    {
        int l, r;
        cin >> l >> r;
        bool isSorted = true;
        for(int j = l; j < r; j++)
        {
            if(a[j] > a[j + 1] )
            {
                isSorted = false;
                break;
            }
        }
        if(isSorted == true)
            cout << "Sorted" << endl;
        else
            cout << "Not Sorted" << endl;
    }
}

Answer 1

Вы можете сделать один проход через данные, сохраняя в каждом индексе ближайший предшествующий индекс, в котором список уменьшился.

Тогда запрос будет состоять из поиска правого индекса диапазона и сравнения полученного значения с левым индексом диапазона.

int main(void)
{
    constexpr int a[7] = { 5, 4, 3, 7, 9, 11, 2};
    constexpr size_t k = 2;
    constexpr size_t N = sizeof a/sizeof a[0];
    size_t b[N];

    { /* preprocess */
        size_t last_decrease = 0;
        b[0] = 0;
        for( int x = 1; x < N; ++x )
        {
            if (a[x] < a[x-1]) last_decrease = x;
            b[x] = last_decrease;
        }
    }

    for(int i = 0; i < k; i++)
    {
        int l, r;
        std::cin >> l >> r;
        bool isSorted = l >= b[r];

        if (isSorted)
            std::cout << "Sorted\n";
        else
            std::cout << "Not Sorted\n";
    }
}

Нет вложенных циклов, поэтому это решение имеет линейное время выполнения.