# Queries to check if subarrays over given range of indices is non-decreasing or not

Queries to check if subarrays over given range of indices is non-decreasing or not

Given an array arr[] consisting of N integers and an array Q[][2] consisting of K queries of type {L, R}, the task for each query is to check if the subarray {arr[L], .. arr[R]} of the array is non-decreasing or not. If found to be true, then print “Yes”. Otherwise, print “No“.

Examples:

Input: arr[] = {1, 7, 3, 4, 9}, K = 2, Q[][] = {{1, 2}, {2, 4}}Output:YesNoExplanation:Query 1: The subarray in the range [1, 2] is {1, 7} which is non-decreasing. Therefore, print “Yes”.Query 2: The subarray in the range [2, 4] is {7, 3, 4, 9} which is not non-decreasing. Therefore, print “No”.

Input: arr[] = {3, 5, 7, 1, 8, 2}, K = 3, Q[][] = {{1, 3}, {2, 5}, {4, 6}}Output:YesNoNo

Naive Approach: The simplest approach is to traverse the array over the range of indices [L, R] for each query and check if the subarray is sorted in ascending order or not. If found to be true, then print “Yes”. Otherwise, print “No“.Time Complexity: O(N * Q)Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized by precomputing the count of adjacent elements satisfying arr[i] > arr[i + 1] in the range [1, i] which results in constant time calculation of numbers of such indices in the range [L, R – 1]. Follow the steps below to solve the problem:

Initialize an array, say pre[], to store the count of indices from the starting index, having adjacent elements in increasing order.

Iterate over the range [1, N – 1] and assign pre[i] = pre[i – 1] and then increment pre[i] by 1, if arr[i – 1] > arr[i].

Traverse the array Q[][] and for each query {L, R}, if pre[R – 1] – pre[L – 1] is 0, then print “Yes”. Otherwise, print “No“.

Below is the implementation of the above approach:

C++

#include

using namespace std;

void checkSorted(int arr[], int N,

vector& Q)

{

int pre[N] = { 0 };

for (int i = 1; i < N; i++) {
pre[i] = pre[i - 1]
+ (arr[i - 1] > arr[i]);

}

for (int i = 0; i < Q.size(); i++) {
int l = Q[i][0];
int r = Q[i][1] - 1;
if (pre[r] - pre[l - 1] == 0)
cout