CodeTON Round 7 : E. Permutation Sorting

こっちの方がDより簡単？
https://codeforces.com/contest/1896/problem/E

問題

N要素の順列Pが与えられる。
Pが昇順になるまで、以下の処理を行う。

• PのうちP[i]=iでない要素を、右にrotateする

各iについて、P[i]=iとなるまでの操作回数を求めよ。

解法

P[i]がiに至るには、(i-P[i])%N回右に移動しなければならない。
ただし、P[i]～iの間にi未満の値があるなら、それらの個数だけrotateを省略できる。
よってBITを使いそのような値の数を計算しよう。

int T,N,A[1010101];

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,22> bt;
int ret[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,2*N+2) bt.add(i,-bt(i));
		vector<pair<int,int>> V;
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
			if(i<=A[i]) {
				V.push_back({i,A[i]});
				V.push_back({i+N,A[i]+N});
			}
			else {
				V.push_back({i,A[i]+N});
			}
		}
		sort(ALL(V));
		reverse(ALL(V));
		FORR2(x,y,V) {
			if(x<N) ret[A[x]]=y-x-(bt(y)-bt(x));
			bt.add(y,1);
		}
		FOR(i,N) cout<<ret[i]<<" ";
		cout<<endl;
	}
}

まとめ

これ上限がN=10^5でもよさそうだけど、想定O(NlogN)なんだよなぁ。