Solution P14062 | Well I'm still NOOB

注意到进行 $k$ 级排序的时候，已经进行了 $2k,3k,4k,\cdots$ 级排序。

所以取出下标模

k

余

x

的一个序列（

x

是

[0,k)

中的任意整数）后，这个序列不应出现距离

\ge 2

的逆序对。

也就是说，题目中的排序操作，可以改成跑一轮冒泡排序（检查相邻两项，若是逆序对则交换）！

重新模拟整个过程，不难发现它就等价于每次交换最远的一对逆序对，而且相同距离的逆序对互不影响。

现在引入拆分值域的思想。枚举一个

i

，将所有

\le i

的值赋为

0

，否则赋为

1

，求出将

01

序列排序需要的排序轮数

F_i

。答案即为

\max \limits_{i=1}^{n-1} F_i

。

操作相当于每次将最右边的

1

和最左边的

0

交换，直到排好序。

考虑在序列上找到一个分界线，分界线左边的

1

的数量等于右边的

0

的数量，然后这些逆序的

(1,0)

对将会依次完成交换。

由于最终状态，不难发现分界线就在

i

和

i+1

之间。

那么求出

i+1

右边下标最大的

0

和

i

左边下标最大的

1

的下标之差（因为它们是最后一对交换的

(1,0)

），这样就可以算出

F_i

。

对

i

扫描线。后面的维护方法不再赘述。

时间复杂度

\mathcal{O}(n)

（这里偷懒写了并查集，多了

\alpha(n)

）。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
#define popcnt __builtin_popcountll
const ll mod = 998244353;
inline ll read(){
	ll x=0, f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}
inline int lg2(int x){ return 31^__builtin_clz(x); }
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline void addmod(int &x){ if(x >= mod) x -= mod; }
inline void addmod(ll &x){ if(x >= mod) x -= mod; }
inline ll qpow(ll a,ll b){
	ll ans=1, base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod; b>>=1;
	}
	return ans;
}
inline ll INV(ll x){ return qpow(x, mod-2); };
int n,p[4000005],iv[4000005],L[4000005],R[4000005];
int fa[4000005];
inline int find(int x){
	if(x!=fa[x]) fa[x]=find(fa[x]);
	return fa[x];
}
inline void merge(int x,int y,int p){
	x=find(x),y=find(y);
	if(!p){
		if(x>y) fa[x]=y; else fa[y]=x;
	}else{
		if(x<y) fa[x]=y; else fa[y]=x;
	}
}
void procedure(){
	n=read();
	for(int i=1;i<=n;i++) iv[p[i]=read()]=fa[i]=i;
	for(int i=1;i<n;i++){
		int pos=iv[i];
		if(pos>1 && p[pos-1]<=i) merge(pos-1,pos,0);
		if(pos<n && p[pos+1]<=i) merge(pos,pos+1,0);
		if(p[i]<=i){
			L[i]=i-find(i)+1;
			if(find(i)==1) L[i]=n;
		}else L[i]=0;
	}
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=n-1;i>=1;i--){
		int pos=iv[i+1];
		if(pos>1 && p[pos-1]>i) merge(pos-1,pos,1);
		if(pos<n && p[pos+1]>i) merge(pos,pos+1,1);
		if(p[i+1]>i){
			R[i]=find(i+1)+1-i;
			if(find(i+1)==n) R[i]=n;
		}
		else R[i]=1;
	}
	int ans=n;
	for(int i=1;i<n;i++){
		ans=min(ans,L[i]+R[i]);
	}
	printf("%d\n",n-ans);
}

Solution P14062 | Well I'm still NOOB

文章操作

相关推荐

评论

Solution P14062 | Well I'm still NOOB