「UVa 11525」Permutation

发表于 |
字数统计: 700 | 阅读时长 ≈ 3

给定$n$个数$x_1,x_2\cdots x_n$，已知$S=\sum^{n}_{i=1}x_i(n-i)!$，求第$S$个排列

前置技能

康托展开是一个比较常用的哈希技巧，可以将一个排列$a_1,a_2\cdots a_n$映射到一个整数$k$，这个整数$k$就是这个排列在所有排列中的名次。
由于它是双射的，所以也可以从一个整数还原这个整数所对应的全排列。
假定这个排列是由$n$个数组成的，那么有从一个整数$k$映射到第$k$小的排列的方法：
将$k$写成$\sum^{n}_{i=1}x_i(n-i)!$的形式，其中对于任意$x_i$，有$0\leq x_i\leq i$。
对于第$i$次操作，选择当前没有选过的第$x_i$大的数加入排列。
进行第二步$n$次，所得的排列即为所求。

题解

注意到，题目已经完成了第一步，所以只需要完成第二步就可以了。
而数据范围$k\leq 5\times10^4$，所以要写一种高效的数据结构，支持区间第$k$小和删除一个数。
这里用权值线段树实现，由于$1\leq x_i\leq n$（这里的变量都是值上面的题意而言的），所以不用离散化。于是查询变得很简单了，但删除呢？
可以将这个数置为$0$，意思是被删除了。如果这个节点的值为$0$，那么整个子树都不复存在。
这份代码还是跑的蛮快的，$60$ms。可还是没有最优解跑的快
最后，此题卡输出格式，要像我这么写才能AC

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=5e4+51;
struct SegmentTree{
    ll l,r,size;
};
ll test,cnt,num;
SegmentTree tree[MAXN<<2];
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;
    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()
{
    test=read();
    for(register int i=0;i<test;i++)
    {
        cnt=read();
        create(1,cnt,1);
        for(register int j=0;j<cnt;j++)
        {
            num=read()+1;
            printf("%d",findVal(num,1));
            putchar(j==cnt-1?'\n':' ');
        }
    }
}