有疑问的地方已经在代码中标注出

题

题目描述

给定一个 $1 \sim n$ 的排列 $P$ 你希望通过以下操作使得 $\forall i \in [1,n]$。

选择一个正整数 $k$, $1 \leq k \leq n$,若 $k>1$ 就将 $P_1 \sim P_{k-1}$ 按升序排列；若 $k<n$ ,就将 $P_{k+1} \sim P_n$ 按升序排列。

问至少需要几次操作。

可以证明一定可以通过若干次操作达到要求。

输入格式

有多组测试数据。

第一行输入测试数据组数 $T$ 。

对于每组数据，第一行为排列的长度 $n$ ,第二行 $n$ 个正整数表示排列。

输出格式

对于每组测试数据，输出一行一个整数表示答案。

样例 #1

样例输入 #1

3
5
2 1 3 5 4
3
1 2 3
7
3 2 1 7 5 6 4

样例输出 #1

1
0
2

数据范围

$1 \leq T \leq 10^5, 3\leq n \leq 2 \times 10^5 , \sum n \leq 2 \times 10 ^ 5$

对于 $20\%$ 的数据，保证 $n \leq 10$

对于另外 $10\%$ 的数据，保证 $P_1=1$

题解

容易观察到至多三次操作即可完成。

依次取 $k=1,k=n,k=1$ 即可。

只需考虑能否以更少的次数完成。

$0$ 次是显然的

$1$ 次完成当且仅当存在一个 $k$，使得 $P_k=k$ 且 $P_i<k,i<k$ 且 $P_i>k,i>k$

$3$ 次完成当且仅当不满足上面两种情况且 $P_n=1,P_1=n$

其余情况均为 $2$ 次完成

My Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rd read()
#define mkp make_pair
#define psb push_back
#define Elaina 0
#define random(a,b) (1ll*rand()*rand()*rand()%((b)-(a)+1)+(a))
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f=(ch=='-'?-1:1);
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
	return f*x;
}
const int p=1e9+7;
const int N=1e6+100;
const int inf=0x7fffffff7fffffff;

int T,n,a[N];

struct SZSZ{
	int num[N];
	
	int lowbit(int x){
		return x&(-x);
	}
	
	void add(int x,int k){
		while(x<=n){
			num[x]+=k;
			x+=lowbit(x);
		}
	}
	
	int query(int x){
		int sum=0;
		while(x>0){
			sum+=num[x];
			x-=lowbit(x);
		}
		return sum;
	}
}sz;

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>T;
	while(T--){
		bool flag=0,is_pm=1;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]!=i){
				is_pm=0;
			}
		}
		if(is_pm){
			cout<<0<<'\n';
			continue;
		}
		if(a[1]==1){
			cout<<1<<'\n';
			continue;
		}
		if(a[n]==n){
			cout<<1<<'\n';
			continue;
		}
		if(a[1]==n && a[n]==1){
			cout<<3<<'\n';
			continue;
		}
		if(a[n]==1){
			cout<<2<<'\n';
			continue;
		}
		if(a[1]==n){
			cout<<2<<'\n';
			continue;
		}
		
		for(int i=1;i<=n;i++){
			if(a[i]==i&&sz.query(i-1)==i-1){
				flag=1;
                //break; 原本这里是加了break的，实际得分89pts，删去break就AC了
			}
			sz.add(a[i],1);
		}
		
		for(int i=1;i<=n;i++) sz.add(a[i],-1);
		
		if(flag){
			cout<<1<<'\n';
			continue;
		}
		cout<<2<<'\n';
	}
	return Elaina;
}