题解 | #koala的程序#

提供一个 L 题的 python 题解。本题是约瑟夫环问题的优化模拟，核心在于：（1）过程中高效维护已经删去的位置；（2）并快速找到下一个跳到的位置。

考虑使用线段树（当然是码量更小的树状数组啦），对于（1），将对应位置置零即可；对于（2），在前缀和上二分，找到当前位置往后推的第 m 个位置即可。对于环形，取模即可，细节：为了能取到 n，稍微处理一下（见代码）。

class Fenwick:
    __slots__ = 'tree'

    def __init__(self, n): 
        self.tree = [0] * (n + 1)

    def add_delta(self, i: int, delta: int) -> None: 
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def pre(self, i: int) -> int: 
        res = 0
        while i > 0:
            res += self.tree[i]
            i &= i - 1
        return res

    def find_kth(self, k: int) -> int:
        left, right = 1, len(self.tree)
        while left < right:
            mid = (left + right) // 2
            if self.pre(mid) < k: left = mid + 1
            else: right = mid
        return left


def solve():
    n, m = mii()
    T = Fenwick(n)

    for i in range(1, n + 1): T.add_delta(i, 1)

    res = []
    cur = 1

    while n > 1:
        cur = (cur - 1 + m - 1) % n + 1
        nxt = T.find_kth(cur)
        res.append(nxt)
        T.add_delta(nxt, -1)
        n -= 1

    print(*res)