C - Sort Subarray Editorial by en_translator
Let \(X=(X _ 1,X _ 2,\ldots,X _ N)\) be the sequence obtained by sorting \(A _ 1,A _ 2,\ldots,A _ N\) in ascending order.
Suppose \(A\) became sorted in ascending order (i.e. coincided with \(X\)) by choosing some \(i\) to perform the operation. The values of \(A _ 1,A _ 2,\ldots,A _ {i-1}\) and \(A _ {i+K},A _ {i+K+1},\ldots,A _ N\) do not change by the operation, these must be equal to \(X\).
Conversely, if it holds for some \(i\) that \(A _ 1=X _ 1,A _ 2=X _ 2,\ldots,A _ {i-1}=X _ {i-1}\) and \(A _ {i+K}=X _ {i+K},A _ {i+K+1}=X _ {i+K+1},\ldots,A _ N=X _ N\), then performing the operation for such \(i\) makes \(A\) equal to \(X\).
Therefore, the following approaches, for example, can decide the answer:
- Find the minimum \(i\) and maximum \(i\) such that \(A _ i\ne X _ i\), and check if their difference is strictly less than \(K\).
- Perform the operation for the minimum \(i\) with \(A _ i\ne X _ i\), and check if \(A=X\).
Directly finding \(X\) requires sorting, which costs \(O(N\log N)\) time. While this is fast enough, but a clever reinterpretation of “the minimum \(i\) such that \(A _ i\ne X _ i\)” helps solving the problem in just \(O(N)\) time.
The following is sample code.
#include <iostream>
#include <vector>
#include <ranges>
int main() {
using namespace std;
unsigned N, K;
cin >> N >> K;
vector<unsigned> A(N);
for (auto&& a : A) cin >> a;
// The maximum i with A[i] != X[i] is the maximum i such that there exists j < i such that A[j] > A[i]
unsigned prefix_max{}, max_i{};
for (const auto& [i, a] : A | views::enumerate) {
prefix_max = max(a, prefix_max);
if (prefix_max > a) max_i = i;
}
// The minimum i with A[i] != X[i] is the minimum i such that there exists j > i such that A[i] > A[j]
unsigned suffix_min{N}, min_i{N};
for (const auto& [i, a] : A | views::enumerate | views::reverse) {
suffix_min = min(a, suffix_min);
if (suffix_min < a) min_i = i;
}
cout << (K + min_i > max_i ? "Yes" : "No") << endl;
return 0;
}