O(n.logn) 中的 Josephus 排列（移除顺序）

Question

有没有办法在O(n.logn)中打印出约瑟夫斯问题中的移除顺序？

例子

人数为n = 7，跳过人数为k = 3。淘汰顺序为：

3, 6, 2, 7, 5, 1, 4

Answer 1

有一种使用有序集的方法

(https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/):

初始化一个有序集合V，将[1,N]范围内的元素插入V
初始化一个变量，比如pos为0，用来存放变量的索引删除元素。
迭代直到V的大小大于1，执行以下步骤：
- 将集合的大小存储在变量中，比如 X
- 将pos的值更新为(pos + K) % X
- 在V中打印pos指向的元素，然后擦除
- 将pos更新为pos%V.size()
打印集合 V 开头存储的最后一个元素

代码如下：

#include <iostream>
using namespace std;

// Header files, namespaces to use
// ordered set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set                          \
    tree<int, null_type, less<int>, rb_tree_tag, \
        tree_order_statistics_node_update>

// Function to find the person who
// will get killed in the i'th step
void orderOfExecution(int N, int K)
{

    // Create an ordered set
    ordered_set V;

    // Push elements in the range
    // [1, N] in the set
    for (int i = 1; i <= N; ++i)
        V.insert(i);

    // Stores the position to be removed
    int pos = 0;

    // Iterate until the size of the set
    // is greater than 1
    while (V.size() > 1) {

        // Update the position
        pos = (pos + K) % (int)V.size();

        // Print the removed element
        cout << *(V.find_by_order(pos)) << ' ';

        // Erase it from the ordered set
        V.erase(*(V.find_by_order(pos)));

        // Update position
        pos %= (int)V.size();
    }

    // Print the first element of the set
    cout << *(V.find_by_order(0));
}

int main()
{
    int N = 5, K = 2;

    // Function Call
    orderOfExecution(N, K);

    return 0;
}

时间复杂度：O(N * log(N))

为了更好地理解，我建议观看此视频：

https://youtu.be/KnsDFCcBJbY

Answer 2

你可以构建线段树来解决这些类型的操作

M(p, v): 修改a[p] := v
S(l, r): 计算a[l] + a[l+1] + ... + a[r]
F(p, k): 找到 (x >= p) 和 S(1, x) >= k

以上所有操作都可以在O(log n)时间内完成

使用上述算法，您可以在 O(n log n)

中获得相同的结果

/*
    @Author: SPyofgame
    @License: Free to use
*/

#include <iostream>
#include <vector>

using namespace std;

/// Segment Tree Data Structure
struct Segtree
{
    int n;
    vector<int> t;

    /// O(n)
    /// Construct Segment Tree
    void init(int lim)
    {
        for (n = 1; n < lim; n <<= 1);
        t.assign(n << 1, 0);
    }

    /// O(log n)
    /// Modify: a[pos] := v
    void modify(int pos, int v, int ct, int lt, int rt)
    {
        if (rt - lt == 1)
        {
            t[ct] = v;
            return ;
        }

        int mt = (lt + rt) >> 1;
        if (mt > pos)
            modify(pos, v, ct * 2 + 1, lt, mt);
        else 
            modify(pos, v, ct * 2 + 2, mt, rt);

        t[ct] = t[ct * 2 + 1] + t[ct * 2 + 2];
    }

    /// O(log n)
    void modify(int pos, int v)
    {
        return modify(pos, v, 0, 0, n);
    }
    
    /// O(log n)
    /// Query: Sigma(a[i] | l <= i <= r)
    int query(int l, int r, int ct, int lt, int rt)
    {
        if (lt >= r || l >= rt) return 0;
        if (lt >= l && r >= rt) return t[ct];

        int mt = (lt + rt) >> 1;
        int lv = query(l, r, ct * 2 + 1, lt, mt);
        int rv = query(l, r, ct * 2 + 2, mt, rt);
        return lv + rv;
    }

    /// O(log n)
    int query(int l, int r)
    {
        return query(l, r + 1, 0, 0, n);
    }

    /// O(log n)
    /// Search: Min(x | Query(1, x) >= k)
    int search_for(int k, int ct, int lt, int rt)
    {
        if (k > t[ct]) return -1;
        if (rt - lt == 1) return lt;

        int mt = (lt + rt) >> 1;
        int v = t[ct * 2 + 1];
        int res = search_for(k - 0, ct * 2 + 1, lt, mt);
        if (res == -1)
            res = search_for(k - v, ct * 2 + 2, mt, rt);
    
        return res;
    }

    /// O(log n)
    int search_for(int k)
    {
        return search_for(k, 0, 0, n);
    }

    /// O(log n)
    /// Search: Min(x | x >= pos & Query(1, x) >= k)
    int search_for_at_least(int pos, int k)
    {
        return search_for(k + query(1, pos - 1), 0, 0, n);
    }
};

int main()
{
    // file("Test");
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    /// Input: Number of element and steps
    int n, k;
    cin >> n >> k;

    Segtree T;
    T.init(n + 1);
    for (int x = 1; x <= n; ++x) /// O(n log n)
        T.modify(x, 1);

    int pos = 1;
    for (int remain = n; remain >= 1; --remain) /// O(n log n)
    {
        /// Number of steps
        int step = k + 1;
        
        /// Move move (remain) times remain the same pos
        step %= remain;
        if (step == 0) step = remain; /// Current pos my not the result, therefore move more (remain) steps

        /// The current segment is not the part we need to search
        int right = T.query(pos, n);
        if (step > right)
        {
            pos = 1; /// Set it back to first pos
            step -= right; /// Number of step traveled
        }

        /// Search for real pos
        pos = T.search_for_at_least(pos, step);
        T.modify(pos, 0);
        cout << pos << " ";
    }

    return 0;
}

你也可以使用迭代线段树

/*
    @Author: SPyofgame
    @License: Free to use
*/

#include <iostream>
 
using namespace std;
 
const int N = 1 << 18;
int T[N+N];

void init(int n)
{
    for (int i = 0; i < n; ++i) T[i + N] = 1;
    for (int i = N - 1; i > 0; --i) T[i] = T[i << 1] + T[i << 1 | 1];
}
 
int lower_bound(int x, int p = 1)
{
    while (p < N) if (T[p <<= 1] < x) x -= T[p++];
    return p - N;
}
 
void update(int p, int v)
{
    for (T[p += N] = v; p > 1; p >>= 1) T[p >> 1] = T[p] + T[p ^ 1];
}
 
int main()
{
    int n, k;
    cin >> n >> k;
    
    init(n);
    for (int remain = n, pos = 0; remain > 0; --remain)
    {
        pos += remain + k;
        pos %= remain;
        int p = lower_bound(pos + 1);
        cout << p + 1 << " ";
        update(p, 0);
    }
 
    return 0;
}

O(n.logn) 中的 Josephus 排列（移除顺序）

Josephus Permutation (Removal Order) in O(n.logn)

algorithm

recursion

math

time-complexity

josephus