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;
}