思路：先约定，左指针 ii 初始值为 11 ，以及右指针 jj。从左往右逐个元素进行枚举，①、如果某个元素值与下标相同，代表该元素处于正确的位置，左指针 ii 加 11 枚举下一个元素。②、不同则代表该元素处于不正确的位置，此时左指针 ii 指向的下标即为排序的左端点，因此生成右指针 jj ，初始化为 i + 1i+1 ，开始往后查找排序的右端点。该查找过程还需要一个 maxvmaxv 变量来维护双指针范围内的区间最大值，当右指针 jj 不停向右滑动，直至指向的下标大于等于区间最大值时，右指针 jj 指向的下标即为排序的右端点（这个道理应该是显然的，因为如果右指针 jj 指向的下标不如区间最大值 maxvmaxv 大，代表还没找到区间最大值的对应位置，还需要进一步扩大区间长度，所以右指针 jj 还需要继续右移）。此时排序区间长度为 j - i + 1j−i+1 。更新左指针 ii 为右指针 jj 的下一个位置，重复以上过程，直至全部元素枚举完毕。最终时间复杂度为 O(n)O(n) 。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[1000005];
int main()
{
int T;
cin >> T;
while (T--)
{
int n, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int i = 1;
while (i <= n)
{
if (a[i] == i) // 相同
i++;
else // 不同
{
int maxv = a[i];
int j = i + 1;
maxv = max(maxv, a[j]);
while (maxv > j)
{
j++;
maxv = max(maxv, a[j]);
}
ans += j - i + 1;
i = j + 1;
}
}
cout << ans << endl;
}
return 0;
}
