Codeforces Round #285 (Div. 1) B

B. Misha and Permutations Summation

        題意：有兩個0~n-1的排列p和q，設p是第x小的排列，q是第y小的排列，求0~n-1的全排列中第(x+y)mod(n!)小的排列。

        思路：很容易想到康托展開。。但是n太大了，無法真正康托展開。是以用樹狀數組統計p和q中每個數後面有多少個比它小的數，然後求和，進位（最後一位滿1進，倒數第二位滿2進...）。進位後的結果就是需要輸出的那個排列的每一位後面有多少個數比它小，需要轉換為對應的排列。可以用二分搜尋+樹狀數組的方法解決。

#include <iostream>
#include <stdio.h>
#include <string>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <string.h>
#include <algorithm>

using namespace std;

const int maxn=200010;

int p[maxn];
int q[maxn];

int cp[maxn];
int cq[maxn];
int cc[maxn];
int n;
int sum[maxn];

bool use[maxn];

inline int lowbit(int x){
	return x&(-x);
}

void update(int pos,int val,int flag){
	int* c;
	if(flag==0)c=cq;
	if(flag==1)c=cp;
	if(flag==2)c=cc;
	while(pos<=n){
		c[pos]+=val;
		pos+=lowbit(pos);
	}
}

int query(int pos,int flag){
	int* c;
	if(flag==0)c=cq;
	if(flag==1)c=cp;
	if(flag==2)c=cc;
	
	int re=0;
	while(pos){
		re+=c[pos];
		pos-=lowbit(pos);
	}
	return re;
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d",&p[i]);
		p[i]++;	//避免用樹狀數組處理0 
	}
	for(int i=0;i<n;i++){
		scanf("%d",&q[i]);
		q[i]++;
	}
	
	//對每一位統計後面比它小的數有多少。。
	for(int i=0;i<n;i++){
		int q_p=(p[i]-1)-query(p[i],0);
		int q_q=(q[i]-1)-query(q[i],1);
		
		sum[i]=q_p+q_q;
		
		update(p[i],1,0);
		update(q[i],1,1);
	}
	
	for(int i=n-1;i>=0;i--){
		while(sum[i]>=(n-i)){
			if(i)sum[i-1]++;
			sum[i]-=(n-i);
		}
	}
	
	//對每一位，有一個等式，即前面比它小的個數+後面比它小的個數+1=數本身 
	for(int i=0;i<n;i++){
		int res=-1;
		int l=1,r=n;
		//二分搜尋 
		while(l<=r){
			int mid=(l+r)>>1;
			if(query(mid,2)+sum[i]+1<=mid){
				r=mid-1;
				if(query(mid,2)+sum[i]+1==mid ){
					res=mid;
				}
			}else{
				l=mid+1;
			}
		}
		printf("%d ",res-1);
		update(res,1,2);
	}
	return 0;
}