【五一省选集训day4】Permutation

每次操作把数分成两组，每组内的顺序不变，把第 \(0\) 组放到第 \(1\) 组前面。

发现这很像基于二进制的基数排序。

假设我们进行 \(k\) 次这样的操作，就相当于给每个数赋一个值 \((x,y)\)，其中 \(0\le x\le 2^k-1,y=\texttt{数的下标}\)。然后对第一维进行基数排序。

因此我们要求我们需要多少个 \(x\)。

发现，设 \(a<b\)，若 \(p_a<p_b\)，则好像 \(p_a\) 和 \(p_b\) 可以共用一个 \(x\)。但实际上这是错误的。如果存在 \(c>b,p_a<p_c<p_b\)，可以发现它们并不能共用一个 \(x\)。

我们发现一个结论，设 \(a<b\)，若 \(p_a+1=p_b\)，则 \(a,b\) 可以共用一个 \(x\)。即值域连续的极长上升子序列可以共用一个 \(x\)。设 \(q_i\) 表示值 \(i\) 的下标，即 \(q=p^{-1}\)。我们需要的 \(x\) 的个数 \(= q_i<q_{i-1}\) 的个数。

这个感觉很贪心，可以拍个暴力证明其正确性：）

构造方案的话，就模拟基数排序。对 \(x\) 进行基数排序。

代码很好写。如下：

函数 stable_partition(a+1,a+n+1,cmp) 表示稳定分组，满足 cmp 的在前，不满足的在后。

#include<bits/stdc++.h>
//#define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N=50005;
template <typename T>
inline void read(T &x){
	x=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
template <typename T>
inline void write(T x){
	static int st[20];
	int cnt=0;
	do{
		st[cnt++]=x%10;
		x/=10;
	}while(x);
	while(cnt) putchar(st[--cnt]+'0');
}
template <typename T>
inline void write (T x,char ch){
	write(x);
	putchar(ch);
}
int n,T;
int a[N],b[N];
int ans,id[N];
int s;
int k;
bool cmp(int x) {return (id[x]>>k&1)==0; }
int main(){
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("my.out","w",stdout);
	#endif
	sf("%d%d",&n,&T);
	rep(i,1,n) sf("%d",&a[i]),b[a[i]]=i;
	rep(i,1,n) {
		if(b[i]<b[i-1]) ans++;
		id[i]=ans;
	}
	while(ans) s++,ans>>=1;
	pf("%d\n",s);
	if(!T) return 0;
	rep(i,1,n) pf("%d ",a[i]);pf("\n");
	rep(i,0,s-1){
		k=i;
		stable_partition(a+1,a+n+1,cmp);
		rep(j,1,n) pf("%d ",a[j]);pf("\n");
	} 
}