yukicoder : No.694 square1001 and Permutation 3

不参加でした。
https://yukicoder.me/problems/no/694

問題

N要素の整数列Aが与えられる。
Aを1つずつrotateしつつ転倒数を随時答えよ。

解法

まずAを座標圧縮し、BITを使って初期状態の転倒数を数えよう。
以後1つずつrotateしつつ転倒数の差分を計算していく。

数列の先頭要素A[0]を末尾に移動した場合、A[0]＞A[i]となるiの数だけ転倒数が減少後、A[0]＜A[i]となるiの数だけ転倒数が増加するので、その分をBITで数えていけばよい。

int N;
int A[505050];

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,20> bt;



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

まとめ

これはまぁ簡単。