[EZOJ3388] 排序

cnt=0;
for(int i=1; i<=n; ++i){
	for(int j=i+1; j<=n; ++j){
		if(a[i]>a[j]) swap(a[i],a[j]);
		++cnt;
	}
}

给出一个排列a(1…n)和值cnt。
对a进行上述操作，cnt刚好为题目给定的值时的a序列。

把零散的放最后暴力处理。
定义一轮操作是跑一遍j。
对于一轮操作，可以看作是从数列中拿出一些数进行轮换。
不考虑稳定的前面的区间，发现对于一个"前缀"区间实际上是把这个区间的最小数扔到了后面。
现在考虑第i位。
以i结尾的区间会把这个区间最小值扔到后面。
以i-1结尾的区间也会把这个区间的最小值扔到后面。
当i-1结尾的区间扔出来的值比i小的时候，i是不会动的。
当i-1结尾的区间扔出来的值比i大的时候，i上的值是这个区间的最小值，而且现在会被前面扔出来的值踢下去。
进行一轮操作，对第i位的影响可以看成让i和把i前面最小的取一次max。
现在进行k轮，对于第i位的影响其实是对前面的k个最小值取一次max。
用堆维护第k小值，对后面的区间的每一位取一次max。

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
typedef long long lint;
const int N=1e6+5;
int n,val[N];
lint m;

namespace IO{
	const int SIZE=1<<16;
	char ibuf[SIZE],*ih,*it,obuf[SIZE],*oh=obuf,*ot=obuf+SIZE;
	inline void flush(){
		fwrite(obuf,1,oh-obuf,stdout);
		oh=obuf;
	}
	struct Flusher{
		~Flusher(){flush();};
	}_flusher;
	inline void put_c(const char c){
		*oh++=c;
		if(oh==ot) flush();
	}
	inline char get_c(){
		if(ih==it){
			it=(ih=ibuf)+fread(ibuf,1,SIZE,stdin);
			if(ih==it) return EOF;
		}
		return *ih++;
	}
	template <class T> inline T nxi(){
		T x=0;
		char c;
		while((c=getchar())>'9'||c<'0');
		while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
		return x;
	}
	template <class T> inline void pti(T x){
		static char tmp[20];
		char *pt=tmp;
		if(!x) put_c('0');
		for(int y=x/10; x; x=y,y=x/10){
			*pt++=x-y*10+'0';
		}
		while(pt!=tmp) put_c(*--pt);
	}
}
using IO::nxi;
using IO::pti;
using IO::get_c;
using IO::put_c;

inline void solve(){
	std::priority_queue <int> pq;
	int len=0;
	while(len<=n&&m>=n-len-1){
		m-=n-++len;
	}
	if(len){
		for(int i=1; i<=len; ++i){
			pq.push(val[i]);
			val[i]=i;
		}
		for(int i=len+1; i<=n; ++i){
			if(val[i]<pq.top()){
				pq.push(val[i]);
				val[i]=pq.top();
				pq.pop();
			}
		}
	}
	for(int j=1; j<=m; ++j){
		if(val[len+1]>val[len+1+j]){
			std::swap(val[len+1],val[len+1+j]);
		}
	}
	for(int i=1; i<=n; ++i){
		pti(val[i]);
		put_c(' ');
	}
	put_c('\n');
}

int main(){
	n=nxi<int>(),m=nxi<lint>();
	for(int i=1; i<=n; ++i){
		val[i]=nxi<int>();
	}
	solve();
	return 0;
}