Codeforces #609 Div1 C. K Integers

Div1Cにしては楽？
https://codeforces.com/contest/1268/problem/C

問題

1～NのPermutationとなる数列Aが与えられる。
整数Kに対し、2値のswapを繰り返し、A中に1～Kが個の順で連続するようにするときの最小swap数を考える。
K=1～Nに対し、それぞれ上記値を求めよ。

解法

1～KのAにおける転倒数分と、あとはK個の要素を中央に寄せるのにかかる手数の和が必要最小数となる。
前者はBITで求めるのは定番だし、後者もBIT上で二分探索して寄せるべき中央の位置と、寄せるのにかかる手数を数えられる。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[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) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<ll,20> bt,dist;

int N;
int P[202020];
int re[202020];
int inv[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
		re[P[i]]=i+1;
	}
	
	ll sinv=0;
	FOR(i,N) {
		sinv+=bt((1<<20)-1)-bt(re[i]);
		bt.add(re[i],1);
		dist.add(re[i],re[i]);
		int mid=bt.lower_bound(i/2+1);
		ll RD=dist((1<<20)-1)-dist(mid);
		ll rnum=bt((1<<20)-1)-bt(mid);
		ll LD=dist(mid-1);
		ll lnum=bt(mid-1);
		ll ret=sinv+RD-(mid*rnum)-rnum*(rnum+1)/2+lnum*mid-LD-lnum*(lnum+1)/2;
		cout<<ret<<" ";
	}
	cout<<endl;
	
	
}

まとめ

面倒と思ったけど結局BITだけで行けるし、コードもそこまで長くなかったか。