yukicoder : No.3469 ジャッジ結果の逆転数

ジャッジのテスト用らしく簡単目。
https://yukicoder.me/problems/no/3469

問題

整数列Aが与えられる。
i＜jかつA[i]＞A[j]となる(i,j)の組は何通りか。

解法

転倒数を求めるだけで良い。

int N,A[202020];
vector<int> As;
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<int,20> bt;


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

まとめ

今となっては典型だし、★2～2.5でもいい気はするけど、初期のyukicoderを考えれば★3でも悪くないかも？