\(\mathrm{Sleepy Cow Sorting}\)

问题描述

LG5200

题解

树状数组。

设\(c[i]\)代表\([1,i]\)中归位数。

显然最终的目的是将整个序列排序为一个上升序列，于是倒序枚举，先把最后有序的插入。

剩下来前面无序的就是要操作的，于是直接输出操作次数。

接下来方案很容易构造。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

void read(int &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

const int maxn=100000+7;

#define lowbit(pos) (pos&(-pos))

int c[maxn],n,a[maxn];

void change(int pos,int k){

	while(pos<=n){

		c[pos]+=k;pos+=lowbit(pos);

	}

}

int query(int pos){

	int ret=0;

	while(pos){

		ret+=c[pos];pos-=lowbit(pos);

	}

	return ret;

}

int ans,cnt;

int main(){

	freopen("sleepy.in","r",stdin);freopen("sleepy.out","w",stdout);

	read(n);

	for(int i=1;i<=n;i++) read(a[i]);

	for(int i=n;i>=1;i--){

		ans++;--cnt;change(a[i],1);

		if(a[i-1]>a[i]) break;

	}

	cnt+=n;

	printf("%d\n",cnt);

	for(int i=1;i<=n-ans;i++){

		--cnt;printf("%d ",query(a[i])+cnt);

		change(a[i],1);

	}

	fclose(stdin);fclose(stdout);

	return 0;

}