AtCoder ABC #190 : F - Shift and Inversions

拍子抜け？
https://atcoder.jp/contests/abc190/tasks/abc190_f

問題

0～(N-1)のPermutationが与えられる。
k要素分rotateしたときの転倒数を順次求めよ。

解法

k=0の時は典型でBITを使い求める。
その後、1つずつrotateしたとき転倒数がどうなるか差分を考える。

先頭要素がxの時、xが先頭から消えることで、以降にあるx未満の要素x個分だけ転倒数が減る。
その後rotateによりxが末尾に追加されるので、手前にあるxより大きな要素(N-1-x)個分だけ転倒数が増える。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,21> bt;
int N;
int A[606060];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	FOR(i,N) {
		cin>>A[i];
		ret+=bt(N)-bt(A[i]);
		bt.add(A[i],1);
	}
	FOR(i,N) {
		cout<<ret<<endl;
		ret-=A[i];
		ret+=N-1-A[i];
	}
	
}

まとめ

過去ABCのFで一番簡単？