「CodeForces 501D」Misha and Permutations Summation

发表于 |
字数统计: 1k | 阅读时长 ≈ 4

设$P$是一个长度为$n$的排列，定义$\operatorname{ord}P$为$P$在所有排列中的名次。
给定两个长度为$n$的排列$P_1,P_2$，求第$\operatorname{ord}P_1+\operatorname{ord}P_2 \bmod n!$小的排列。

前置技能

康托展开
这里讲从排列映射到数的过程，还是假设这个排列长度为$n$。
对于第$i$次操作，统计这个数后面有多少个比它小的数，记为$a_i$
那么答案是$\sum_{i=1}^{n}a_i(n-i)!$

题解

这一个题和UVa 11525很像，不会做的可以参考一下本蒟蒻的题解，做法就是用一颗权值线段树维护全局没被放进排列中的第$k$小，所以做这个题可以先把它转化为上面那个题。
首先把两个排列映射到整数，这里要统计后面有多少个比第$i$个数$a_i$小的数。如果暴力找的话是$O(n^2)$的。但是，可以发现排列是由$0,1\cdots n-1$组成的，那么排列里比这个数小的数的个数就是这个数。
这句话不是很好懂，但是很重要。因为排列里比这个数$x$小的只有$0,1\cdots x-1$，共有$x$个，所以有$x$个数比$x$小。
所以可以显然推出后面比$a_i$小的数的个$=$总共比$a_i$小的数$-$在$a_i$前面比$a_i$小的数。而排在前面比$a_i$小的数可以用树状数组维护。
用一个树状数组维护第$i$个数是否出现过。对于当前的数，统计$1$到当前数$-1$中的和，就是在这个数前面比它小的数。
所以说，可以用$O(n\log n)$的时间复杂度把$a_{P_1,i}$和$a_{P_2,i}$（$a$指的是前置技能里的$a$数组）求出来，记$S_i=a_{P_1,i}+a_{P_2,i}$。
接下来化简$S$，由于$(x+1)\cdot x!=(x+1)!$，于是可以用这个性质化简$S_i$，使得$0\leq S_i\leq n-i$。
具体方法是，对于$S_i$，$S_{i+1}+=S_i \% n-i,S_i\%=n-i$就可以简化$S$数组了。
最后我们就把问题转化为上面的那个题了，用那个题的方法做就可以了qwq。
时间复杂度$O(n\log n)$，常数不大除了权值线段树，跑了$2270$ms，拿了最优解qwq。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=2e5+51;
struct BIT{
    ll size;
    ll num[MAXN];
    inline ll lowbit(ll x)
    {
        return x&-x;
    }
    inline void add(ll pos,ll val)
    {
        for(;pos<=size;pos+=lowbit(pos))
        {
            num[pos]+=val;
        }
    }
    inline ll queryPrefix(ll pos)
    {
        ll res=0;
        for(;pos;pos-=lowbit(pos))
        {
            res+=num[pos];
        }
        return res;
    }
};
struct SegmentTree{
    ll l,r,size;
};
BIT bit,bit2;
SegmentTree tree[MAXN<<2];
ll cnt,num;
ll perm[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void update(ll node)
{
    tree[node].size=tree[node<<1].size+tree[(node<<1)|1].size;
}
inline void create(ll l,ll r,ll node)
{
    tree[node].l=l,tree[node].r=r;
    if(l==r)
    {
        tree[node].size=1;
        return;
    }
    ll mid=(l+r)>>1;
    create(l,mid,node<<1);
    create(mid+1,r,(node<<1)|1);
    update(node);
}
inline ll findVal(ll rk,ll node)
{
    if(tree[node].l==tree[node].r)
    {
        tree[node].size=0;
        return tree[node].l;	
    }	
    ll res=0;
    if(rk<=tree[node<<1].size)
    {
        res=findVal(rk,node<<1);
    }
    else
    {
        res=findVal(rk-tree[node<<1].size,(node<<1)|1);
    } 
    update(node);
    return res;
}
int main()
{
    bit.size=bit2.size=cnt=read();
    for(register int i=1;i<=cnt;i++)
    {
        num=read();
        perm[i]=num-bit.queryPrefix(num),bit.add(num+1,1);
    }
    for(register int i=1;i<=cnt;i++)
    {
        num=read();
        perm[i]+=num-bit2.queryPrefix(num),bit2.add(num+1,1);
    }
    for(register int i=cnt,j=0;i;i--,j++)
    {
        perm[i-1]+=perm[i]/(j+1),perm[i]%=(j+1);
    }
    create(1,cnt,1);
    for(register int i=1;i<=cnt;i++)
    {
        printf("%d ",findVal(perm[i]+1,1)-1);
    } 
}