Codeforces #285 Div1 B. Misha and Permutations Summation

本番割とあっさり思いつけた。
http://codeforces.com/contest/504/problem/B

問題

0～(N-1)のpermutationを成す数列xを考える。
Ord(x)とは、0～(N-1)のpermutationを辞書順に並べた場合、数列xが(0-indexで)何番目に来るかを示す。
逆にPerm(y)とは、0～(N-1)のpermutationを辞書順に並べた場合(0-indexで)y番目に来るpermutationを示す。

２つのpermutationであるp,qが与えられる。
Perm*1 % N!)を答えよ。

(0-indexで)i桁目が(N-i)進数となるような整数P'、Q'を考え、Ord(p)、Ord(q)をそのような整数で表現する。
この整数の大小関係は、permutationの辞書順大小と一致する。

P'のi桁目P'[i]は、0～(N-1)のうちP[0]～P[i-1]で登場したものを除き、P[i]が何個目の数字かを格納すればよい。
これはBITを使って求めることができる。

同様にQ'[i]を求める。
するとOrd(p)+Ord(q)はP'[i]とQ'[i]の和で表現できる。
i桁目が(N-i)進数であることを考慮しながら繰り上がりを処理し、P'[i]とQ'[i]の和R'[i]を求める。

今度は逆にR'[i]をPermutation R[i]に戻す作業が必要となる。
R'[i]の値は、R[i]が(R[0]～R[i-1]で使われた数字を除き)R'[i]番目の数字であることを示すので、これも同様にBITを駆使して求めることができる。

なお、今回「(0-indexで)i桁目が(N-i)進数となるような整数」という表現を自分で思いついたけど、既にそういう概念はあったのね…。
Factorial number system - Wikipedia, the free encyclopedia

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void update(int e, V val) {e++; while(e<=1<<ME) bit[e-1]+=val,e+=e&-e;}
};
BIT<int,20> btp,btq,btr;

int N;
int P[201000],Q[201000];
int P2[201000],Q2[201000],R[201000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) btp.update(i+1,1),btq.update(i+1,1),btr.update(i+1,1);
	
	FOR(i,N) {
		cin>>P[i];
		P2[i]=btp.total(P[i]);
		btp.update(P[i]+1,-1);
	}
	FOR(i,N) {
		cin>>Q[i];
		Q2[i]=btq.total(Q[i]);
		btq.update(Q[i]+1,-1);
	}
	
	for(i=N-1;i>=0;i--) {
		R[i]+=P2[i]+Q2[i];
		while(R[i]>=(N-i)) {
			R[i]-=(N-i);
			if(i!=0) R[i-1]++;
		}
		
	}
	
	FOR(i,N) {
		
		y=(1<<19)-1;
		for(j=18;j>=0;j--) if(btr.total(y-(1<<j))>=R[i]) y-=1<<j;
		
		_P("%d ",y);
		btr.update(y,-1);
	}
	_P("\n");
		
}

まとめ

自分でFactorial number system相当のものを発見できてテンションあがったんだけどな。
まぁA,B共に回答かなり速かったしそれで満足しておくか…。

*1:Ord(p)+Ord(q