排列置换环上构造：1025T3

http://cplusoj.com/d/senior/p/SS231025C

排列构造的新知识：上置换环！

我们发现朴素做法是 $n^2$ 级别的，但数据范围希望我们是 $\frac{n^2}{2}$ 级别的。我们发现我们暴力复制序列显得非常蠢，因为很多序列前后我们其实可以考虑合并。

至于怎么合并？我们直接维护指针。然后我们现在要“运”东西到相应位置。而“运”东西的期望步数是 $\frac{n}{2}$ 的。

然后这个证明直接上置换环。我们相当于一个个置换环来搞。而置换环个数的期望是 $\ln$ 个.

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int 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<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 1010
//#define M
//#define mo
int n, m, i, j, k, T;
int a[N], b[N], p; 
vector<int>ans; signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);freopen("yacolorful.in", "r", stdin);freopen("yacolorful.out", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}n=read(); for(i=1; i<=n; ++i) a[i]=read(), ans.pb(i), b[i]=i; 
//	printf("%d\n", n); 
//	for(i=1; i<=n; ++i) printf("%d ", a[i]); printf("\n"); for(p=2; ; ++p) {if(p==n+1) p=2; if(b[1]!=a[1]) {if(a[p]==b[1]) swap(b[1], b[p]); }else  {if(a[p]!=b[p]) k=0, swap(b[1], b[p]); else ++k; }ans.pb(b[p]); if(k>n) break; }while(p+1<=n) ans.pb(b[p+1]), ++p; for(i=1; i<=n; ++i) ans.pb(a[i]); printf("%d\n", ans.size()); for(auto t : ans) printf("%d ", t); return 0;
}