codeforces 501D Misha and Permutations Summation（康拓展开+数据结构）_康拓2 电梯数据结构

题目链接

2
0 1
0 1

0 1

2
0 1
1 0

1 0

3
1 2 0
2 1 0

1 0 2

题意：已知两个0到n-1的n个数的排列a，b。ord（a）在0到n-1的数的所有排列中的按字典序排序后的位置。ord（b）同理。输出排列x，ord（x）=（ord（a）+ord（b））%n！。

题解：首先要了解康拓展开：康拓展开。

x=a[n]*(n-1)!+a[n-1]*(n-2)!+.......a[1]*0!。，0<=a[i]<i。

由于数据范围太大，直接求出ord显然是不行的。我们可以根据a，b的康拓展开式，直接求出x的康拓展开式。

因为a[i]<=i-1。

所以，排列a康拓展开有可能的最大值为：(n-1)*(n-1)!+(n-2)*(n-2)!+.....(i-1)*(i-1)!+...0*0!

同理排列b康拓展开的最大值为：(n-1)*(n-1)!+(n-2)*(n-2)!+.....(i-1)*(i-1)!+...0*0!

      将两个排列的康拓展开相加可得：n!+(n-1)*(n-1)!+(n-2)*(n-2)!+....(i-1)*(i-1)!+....0*0!

       上式%n!，则可得：(n-1)*(n-1)!+(n-2)*(n-2)!+.........(i-1)*(i-1)!+....0*0!

由此可见，两个排列的康拓展开之和，最大到达n!的数量级，对n!取模过后,剩下的就是一个排列的康拓展开。我们把这个康拓展开逆展开，就解决问题了。

我们可以用类似高精度加法的方法，求出两个排列的康拓展开的和%n!的康拓展开。然后用树状数组+二分的方法，将康拓展开逆展开。复杂度为O(n*lgn*lgn)。当然也可以用平衡树或者线段树，不用二分，复杂度为O(n*lgn)。

我的代码是树状数组+二分的方法，代码如下：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<stdlib.h>
#include<vector>
#define inff 0x3fffffff
#define nn 210000
#define mod 1000000007
typedef long long LL;
const LL inf64=inff*(LL)inff;
using namespace std;
int n;
int a[nn],b[nn];
int ans[nn];
int c[nn];
int dp[nn];
int lowbit(int x)
{
    return x&(-x);
}
void modify(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        c[i]+=y;
    }
}
int getsum(int x)
{
    int sum=0;
    for(int i=x;i>=1;i-=lowbit(i))
        sum+=c[i];
    return sum;
}
int main()
{
    int i;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
        }
        int ix;
        memset(c,0,sizeof(c));
        for(i=1;i<=n;i++)
        {
            ix=getsum(a[i]);
            modify(a[i]+1,1);
            a[i]=a[i]-ix;
        }
        memset(c,0,sizeof(c));
        for(i=1;i<=n;i++)
        {
            ix=getsum(b[i]);
            modify(b[i]+1,1);
            b[i]=b[i]-ix;
        }
        ix=0;
        for(i=n;i>=1;i--)
        {
            ans[i]=(a[i]+b[i]+ix)%(n-i+1);
            ix=(a[i]+b[i]+ix)/(n-i+1);
        }
        for(i=1;i<=n+1;i++)
            dp[i]=i;
        memset(c,1,sizeof(1));
        int l,r,mid;
        for(i=1;i<=n;i++)
        {
            l=1,r=n;
            while(l<r)
            {
                mid=(l+r)/2;
                if(mid-getsum(mid)<ans[i]+1)
                    l=mid+1;
                else
                    r=mid;
            }
            ans[i]=l;
            modify(l,1);
        }
        for(i=1;i<=n;i++)
        {
            printf("%d%c",ans[i]-1,i==n?'\n':' ');
        }
    }
    return 0;
}

线段树做法代码如下：

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<math.h>
#define nn 210000
#define eps 1e-8
#define inff 0x7fffffff
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define mod 20071027
using namespace std;
typedef __int64 LL;
typedef unsigned long long LLU;
int n;
int a[nn],b[nn],c[nn];
int L[nn*4],R[nn*4],sum[nn*4];
void push_up(int id)
{
    sum[id]=sum[id<<1]+sum[id<<1|1];
}
void build(int id,int l,int r)
{
    L[id]=l,R[id]=r;
    if(l==r)
    {
        sum[id]=1;
        return ;
    }
    int m=(l+r)>>1;
    build(2*id,l,m);
    build(2*id+1,m+1,r);
    push_up(id);
}
void update(int  id,int x)
{
    if(L[id]==R[id])
    {
        sum[id]=0;
        return ;
    }
    int m=(L[id]+R[id])>>1;
    if(x<=m)
        update(2*id,x);
    else
        update(2*id+1,x);
    push_up(id);
}
int query(int id,int l,int r)
{
    if(L[id]>=l&&R[id]<=r)
    {
        return sum[id];
    }
    int m=(L[id]+R[id])>>1;
    int re=0;
    if(l<=m)
        re+=query(2*id,l,r);
    if(r>m)
        re+=query(2*id+1,l,r);
    return re;
}
int ask(int id,int x)
{
    if(L[id]==R[id])
    {
        sum[id]=0;
        return L[id];
    }
    int re;
    if(sum[2*id]>=x)
        re=ask(2*id,x);
    else
        re=ask(2*id+1,x-sum[2*id]);
    push_up(id);
    return re;
}
int main()
{
    int i,x;
    while(scanf("%d",&n)!=EOF)
    {
        build(1,0,n-1);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&x);
            update(1,x);
            a[i]=query(1,0,x);
        }
        build(1,0,n-1);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&x);
            update(1,x);
            b[i]=query(1,0,x);
        }
        int ix=0;
        build(1,0,n-1);
        for(i=n;i>=1;i--)
        {
            c[i]=(a[i]+b[i]+ix)%(n-i+1);
            ix=(a[i]+b[i]+ix)/(n-i+1);
        }
        for(i=1;i<=n;i++)
        {
            printf("%d%c",ask(1,c[i]+1),i==n?'\n':' ');
        }
    }
    return 0;
}