POJ 2085 Inversion

問題

1〜nを並べ替えた数列のうち、
転置がちょうどm個あるもので、辞書順最小のものを求めよ。

制約条件

n≦50000
m≦n(n-1)/2

方針

数列を頭から決定していく。
今までで使っていない数のうち、何番目に小さいものを頭におけるかを考える。

転置の残りの数が、頭より右の部分だけで作れるなら一番小さいものを頭においてよい。
そうでないなら、転置の残りの数を、頭より右の部分だけで作れないぶんだけ、
頭に置く数で作ってやる必要がある。

すなわち、今までで使ってない数のうち、何番目に小さいものをそこに使えばよいかがO(1)でわかる。

今までで使ってない数のうち何番目に小さいものかというのが全て決まったら、
binary indexed tree+二分探索で元の数列が復元できる。

ソースコード

int n,k;
int d[50000],a[50000];
int bit[50001];
int sum(int i){
	int res=0;
	for(;i;i-=i&-i)res+=bit[i];
	return res;
}
void add(int x,int i){
	for(;i<50001;i+=i&-i)bit[i]+=x;
}

int main()
{
	for(int i=1;i<50000;i++)d[i]=d[i-1]+i;
	while(scanf("%d%d",&n,&k),~n){
		
		for(int i=n-1;i>=0;i--){
			int idx=0;
			if(i){
				idx=max(0,k-d[i-1]);
				k-=max(0,k-d[i-1]);
			}
			a[n-i-1]=idx;
		}
		rep(i,n+1)bit[i]=0;
		rep(i,n){
			int lo=-1,hi=n,mid;
			while(lo+1<hi){
				mid=(lo+hi)/2;
				if(mid-sum(mid+1)<a[i])lo=mid;
				else hi=mid;
			}
			a[i]=hi+1;
			add(1,hi+1);
		}
		rep(i,n)printf("%d%c",a[i],i==n-1?'\n':' ');
	}
	return 0;
}