UVA 11525 Permutation

Permutation

https://ac.nowcoder.com/acm/problem/117139

Permutation

Permutation - UVA 11525 - Virtual Judge (vjudge.net)

题目描述

给定整数n和k输出1~k的所有排列中，按照字典序从小到大排序后的第n个

n可能很大，本题用k个整数 $S_1,S_2,...$ 来间接给出n方式如下

$n = S_1 * (k - 1)! + S_2*(k - 2)! + ...$

输出满足条件的1~k的排列

样例

算法1

(树状数组倍增求k小数 + 康托展开)

前导

康托展开:

给定的询问形式就是一个康托展开（参考文献）

问题就是从康托展开中还原原序列
树状数组的结构
1. 对于节点i，如果它是左子节点，那么父节点的编号就是i + lowbit(i)；如果他是右子节点，那么父节点的编号就是i - lowbit(i)
2. 节点 $i$ 保存着以 $i$ 结尾的一段连续区间和
3. 树状数组每一层都是一个长度为 $2^i$ 的区间

分析：

本题的核心思想就是用树状数组维护一个数组 $A$
$A[i] == 1$ 表示数字 $i$ 还未被使用
$A[i] == 0$ 表示数字 $i$ 已经被使用
假设进行完x操作，剩下的数字个数为k - x
则 $i = k - x$ 在目前数字集合中的排名就是 $\sum_{j = 1}^i A[j]$
这个值我们可以用树状数组维护

倍增：

本题的问题不是求一个 $i$ 的排名是多少而是给定一个排名求在当前集合中这个排名的数字是多少
由于树状数组是一个树的结构
节点 $i$ 保存着以 $i$ 结尾的一段连续区间和
树状数组每一层都是一个长度为 $2^i$ 的区间
树根覆盖的区间最长，长度为 $log_2(n)$

我们对这棵树进行搜索

int up = log(n) / log(2);
int k = 0,tot = 0;
for(int i = up;i >= 0;i --)
{
    if((1 << i) + k <= n && tot + tr[k + (1 << i)] <= x)
    //如果tot + tr[k + (1 << i)] <= x走到右子树，否则走到左子树
    {
        tot += tr[k + (1 << i)];
        k += (1 << i);//走到右子树
    }
}

时间复杂度 $O(nlogn)$

参考文献

UVA11525 Permutation[康托展開樹狀數組求第k小值] - 开发者知识库 (itdaan.com)

UVA11525 Permutation - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

#define x first
#define y second

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 50010;
int tr[N];
int s[N];
int n;

int lowbit(int x)
{
    return x & -x;
}

void add(int x,int k)
{
    // cout << k << endl;
    for(int i = x;i <= n;i += lowbit(i)) tr[i] += k;
}

int sum(int x)
{
    int res = 0;
    for(int i = x;i;i -= lowbit(i)) res += tr[i];
    return res;
}

int query(int x)
{
    int up = log(n) / log(2);
    int k = 0,tot = 0;
    for(int i = up;i >= 0;i --)
    {
        if((1 << i) + k <= n && tot + tr[k + (1 << i)] <= x)
        {
            tot += tr[k + (1 << i)];
            k += (1 << i);
        }
    }
    return k + 1;
}

void solve()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) add(i,1);
    for(int i = 1;i <= n;i ++) scanf("%d",&s[i]);
    for(int i = 1;i <= n;i ++)
    {
        int t = query(s[i]);
        printf("%d%c",t," \n"[i == n]);
        add(t,-1);
    }
} 

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    // init(N - 1); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cin >> _;

    scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

注：还有一种二分 + 树状数组的做法但是时间复杂度是 $O(nlog^2n)$ 的

算法2

(线段树求k小数 + 康托展开)

用 $sum$ 维护上述的 $\sum A[i]$
如果 $tr[lc].sum <= k$ 递归到左子树
$tr[rc].sum > k$ 递归到右子树同时 $k - tr[rc].sum$

时间复杂度 $O(nlogn)$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

#define x first
#define y second

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 50010;
struct Node
{
    int l,r;
    int sum;
}tr[N * 4];
int n;

void pushup(int u)
{
    tr[u].sum = tr[lc].sum + tr[rc].sum;
}

inline void build(int u,int l,int r)
{
    if(l == r)
    {
        tr[u] = Node({l,r,1});
        return;
    }
    int mid = (l + r) >> 1;
    tr[u] = Node({l,r});
    build(lc,l,mid);
    build(rc,mid + 1,r);
    pushup(u);
}

void modify(int u,int x,int k)
{
    if(tr[u].l == x && tr[u].r == x)
    {
        tr[u].sum = k;
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(x <= mid) modify(lc,x,k);
    else modify(rc,x,k);
    pushup(u);
}

int query(int u,int k)
{
    if(tr[u].l == tr[u].r)  return tr[u].l;
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(tr[lc].sum >= k) return query(lc,k);
    else return query(rc,k - tr[lc].sum);
}

void solve()
{
    scanf("%d",&n);
    build(1,1,n);
    for(int i = 1;i <= n;i ++)
    {
        int s;
        scanf("%d",&s);
        int t = query(1,s + 1);
        printf("%d%c",t," \n"[i == n]);
        modify(1,t,0);
    }
} 

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    // init(N - 1); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cin >> _;

    scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}