【题目链接】:http://codeforces.com/problemset/problem/501/D

【题意】



给你两个排列;

求出它们的字典序num1和num2;

然后让你求出第(num1+num2)%n!个排列是什么;

(字典序);

【题解】



首先。

求出两个排列的字典序；

->康拓展开搞出来;

然后得到

v1[1]∗(n−1)!+..+v1[i]∗(n−i)!+...+v1[n]∗(0)!

的形式

这里v1[i]是i+1..n中比a[i]小的数的个数;

同样的能够得到

v2[1]∗(n−1)!+..+v2[i]∗(n−i)!+...+v2[n]∗(0)!

这里v2[i]是i+1..n中比b[i]小的数的个数;

然后考虑把两个数加起来;

即合并成

(v1[1]+v2[1])∗(n−1)!+..+(v1[i]+v2[i])∗(n−i)!+...+(v1[n]+v2[n])∗(0)!

这里合并之后(v1[i]+v2[i])的值不一定会比(n-i)小;

这就可能让某一个v1[i]+v2[i]进到前一位去;

比如(3+3)4!进到x*5!去;

就会让x加1

因为(3+3)*4!可以写成(5+1)*4!的形式;

即5!+1*4!

也即让5!的系数+1了;

然后4!的系数会减去5

一直往前进位就好;

别忘了要%n!

所以n!的系数可以不用管它了;

然后就能得到(num1+num2)%n!

这个排列的康拓展开的各个

v值了;

从第1位开始;

根据v[1],可以得到比a[1]小的数有多少个;

然后直接让他等于那个v[1]+1;

然后考虑v[2];

这个时候仍旧能够直接得到比a[2]小的数有多少个;

但是不能再包括a[1]了,因为是从2+1..n这个范围里面找比a[2]小的数的个数;

根据找到的合适的位置,确定a[2]即可

以此类推获得a[n]

(可以用树状数组+二分搞出来)

掌握了康拓展开、逆康拓展开吧..

还是很优秀的。



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 2e5+100;

int n;

struct BIT

{

    int data[N];

    int lowbit(int x){

        return (-x)&x;

    }

    int get_sum(int x){

        int sum = 0;

        while (x > 0){

            sum+=data[x];

            x-=lowbit(x);

        }

        return sum;

    }

    void add(int x,int y)

    {

        while (x<=n){

            data[x]+=y;

            x+=lowbit(x);

        }

    }

    void init()

    {

        ms(data,0);

    }

};

BIT c;

int a[N],b[N],v[N],ans[N];

void kangtuo(int *a,BIT &bit){

    bit.init();

    rep1(i,1,n){

        int s = a[i]-1-bit.get_sum(a[i]-1);

        bit.add(a[i],1);

        v[i]+=s;

    }

}

int Bsearch(int l,int r,int k)

{

    int ans = 0;

    while (l <= r)

    {

        int mid = (l+r)>>1;

        int temp = c.get_sum(mid);

        if (mid-temp>=k){

                ans = mid;

                r = mid-1;

        }

        else

            l = mid+1;

    }

    return ans;

}

void nikangtuo(BIT &bit){

    bit.init();

    rep1(i,1,n){

        int s = Bsearch(1,n,v[i]+1);

        ans[i] = s;

        c.add(s,1);

    }

}

int main(){

    //Open();

    Close();//scanf,puts,printf not use

    //init??????

    cin >> n;

    rep1(i,1,n)

        cin>>a[i],a[i]++;

    rep1(i,1,n)

        cin>>b[i],b[i]++;

    kangtuo(a,c);

    kangtuo(b,c);

    rep2(i,n,1){

        int you = n-i+1;

        v[i-1]+=v[i]/you;

        v[i]%=you;

    }

    nikangtuo(c);

    rep1(i,1,n)

    {

        cout<<ans[i]-1<<(i==n?'\n':' ');

    }

    return 0;

}