差分、前缀和

注意到一个数至多被排序一次，如果 $a_i \neq i$ 那么 $a_i$ 就需要被排序，令 $p_i$ 表示 $i$ 在数组 $a$ 中的位置，也就是说至少要对端点为 $i,p_i$ 的区间进行排序。

枚举 $i$ 得到所有需要排序的区间，对所有区间取并得到最终需要排序的区间。时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
int n,ans,a[1000005],p[1000005],sum[1000005];
void solution(){
    cin>>n,ans=0;
    for(int i=1;i<=n;i++) cin>>a[i],sum[i]=0,p[a[i]]=i;
    for(int i=1;i<=n;i++) if(a[i]!=i) ++sum[min(i,p[i])],--sum[max(i,p[i])+1];
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1],ans+=(sum[i]!=0);
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--) solution();
    return 0;
}