CSAcademy Round #42 : D. Sorting Steps

なんだこりゃ。
https://csacademy.com/contest/round-42/task/sorting-steps/

問題

下記のような数列Aをバブルソートするコードを考える。
Aが与えられたとき、stepsはいくつになるか。

int steps = 0;
while (true) {
    ++steps;
    bool isSorted = true;
    for (int i = 1; i < N; ++i)
        if (A[i] > A[i + 1]) {
             swap(A[i], A[i + 1]);
             isSorted = false;
        }
    if (isSorted) break;
}

解法

for文を1回回すと、大きな値は一気に数列の後ろに動くが、小さな値は1つだけ前に動く。
この前に動く回数は、自身より左にある自身より大きな数の数である。

よってBIT等で「自身より左にある自身より大きな数の数」を数え、1加えた値を答えればよい。

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

int N;
int A[101010];
vector<int> V;

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

まとめ

定番すぎてCの方が悩んだ。