Codeforces #300 Div1 F. A Heap of Heaps

本番には解けなかったが、解答がわかるとあっさりな問題。
http://codeforces.com/contest/538/problem/F

問題

N要素の整数列A[i]が与えられる。

整数列から1～(N-1)分木のヒープをそれぞれ作ったとする。
各ヒープの違反数とは、親頂点の整数よりも大きな整数を持つ頂点の数とする。

1～(N-1)分木のヒープの違反数を順に求めよ。

解法

Aを1-indexの配列とする。
k分木のヒープでは、x番目の頂点の親頂点はx/k番となる。
よってkごとにA[x/k]＜A[x]となるxの数を求めたい。

kが小さい場合、kが1増えるごとにx/kの値が変わる。
しかしkが大きくなると、x/kが1変わるのにkがいくつか変わらないと変わらない。

そこで平方分割を用いる。
各A[x]に対し、

• k＜√Nの範囲では、kを1ずつ動かしながらA[x/k]＜A[x]となる数を愚直に数え上げる。
• k≧√Nの範囲では、あるyに対してfloow(x/k)=yとなるようなkの範囲、すなわちx/y≦k＜x/(y-1)となるkに対し、A[y]＜A[x]なら1ずつ加算する。
  • 1ずつの加算法はimos法の要領で行う。

こうするとO(N√O)で解ける。

int N;
ll A[303000];
int ret[303000];
const int sp=300;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	for(x=1;x<N;x++) {
		for(int pa=0;;pa++) {
			int mik=max(1,(x+pa)/(pa+1));
			int mak=(pa==0)?201000:(x-1)/pa;
			
			if(mak<=sp) break;
			
			if(A[pa]>A[x]) {
				ret[mak]++;
				if(mik-1>sp) ret[mik-1]--;
			}
		}
		
		for(i=1;i<=min(N-1,sp);i++) {
			int pa=(x-1)/i;
			if(A[pa]>A[x]) ret[i]++;
		}
	}
	for(i=202001;i>sp;i--) ret[i]+=ret[i+1];
	
	for(i=1;i<N;i++) _P("%d ",ret[i]);
	_P("\n");
}

まとめ

これなんで本番解けなかったんだろう…。