AT4363 [ARC102D] Revenge of BBuBBBlesort!

题面传送门

奇妙的题目。

首先有一个看上去很对的做法：我们从\(a_i=i\)向当前序列移动，每次满足当前位置上不满足的第一个，如果换不过去那么就是NO，否则YES。

但是很遗憾这个东西没有什么优化方法，所以尝试从另一个角度做。

手完几组数据可以发现，只有\(p_i=i\)的位置是可以作为中间节点的。

证明：如果其它可以作为中间节点，那么在转了一次以后，如果这个要继续转，那么需要满足左边转出来了一个更小的，变成了子问题，因此不能。

考虑设\(op_i=(p_i==i)\)，因此如果有连续三个\(op_i=0\)，那么就是不行的。

否则会形成若干个连续的01串，可以分成若干个子段，一个序列满足要求要每个子段都满足要求。

一个子段要满足要求需要两个条件：

1.每个值都在原来应该在的范围内。

2.最长下降子序列长度不超过\(2\)。

因此可以做到\(O(n)\)

code:

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=3e5+5,M=1e7,K=2e3+5,mod=1e9+7,Mod=mod-1;const db eps=1e-5;const int INF=1e9+7;
int n,A[N],p[N],g[N],Fl[N],op[N];
void Fail(){puts("No");exit(0);}
void Solve(int l,int r){
	int i,j,h,L=0,R=0;for(i=l;i<=r;i++) if(A[i]<l||A[i]>r)Fail();
	for(i=l;i<=r;i+=2) A[i]>L?(L=A[i]):(A[i]>R?(R=A[i]):(Fail(),0));
}
int main(){
	freopen("1.in","r",stdin);//freopen("2.out","w",stdout);
	int i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&A[i]),op[i]=(A[i]==i);for(i=2;i<n;i++) if(!op[i]&&!op[i-1]&&!op[i+1]) Fail(); 
	for(i=1;i<=n;i=j+1){if(op[i]||!op[i+1]) {j=i;continue;}
		for(j=i;j+2<=n;j+=2) if(op[j]||!op[j+1]) break;Solve(i,j);	
	}puts("Yes");
}

原文地址：http://www.cnblogs.com/275307894a/p/16798858.html