查询带键的排列

难度: Medium

给定一个正整数数组 queries ，其取值范围在 1 到 m 之间。请你根据以下规则按顺序处理所有 queries[i]（从 i=0 到 i=queries.length-1）：

首先，你有一个排列 P=[1,2,3,...,m]。
对于当前的 i ，找到 queries[i] 在排列 P 中的位置（从 0 开始索引），然后将它移到排列 P 的开头（即下标为 0 处）。注意， queries[i] 的查询结果是 queries[i] 在 P 中移动前的位置。

返回一个数组，包含从给定 queries 中查询到的结果。

示例 1：

输入：queries = [3,1,2,1], m = 5
输出：[2,1,2,1] 
解释：处理 queries 的过程如下：
对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 2，然后我们把 3 移动到 P 的开头，得到 P=[3,1,2,4,5] 。
对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 1，然后我们把 1 移动到 P 的开头，得到 P=[1,3,2,4,5] 。 
对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 2，然后我们把 2 移动到 P 的开头，得到 P=[2,1,3,4,5] 。
对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 1，然后我们把 1 移动到 P 的开头，得到 P=[1,2,3,4,5] 。 
因此，包含结果的数组为 [2,1,2,1] 。

示例 2：

输入：queries = [4,1,2,2], m = 4
输出：[3,1,2,0]

示例 3：

输入：queries = [7,5,5,8,3], m = 8
输出：[6,5,0,7,5]

提示：

1 <= m <= 10^3
1 <= queries.length <= m
1 <= queries[i] <= m

Submission

运行时间: 37 ms

内存: 16.2 MB

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

    @staticmethod
    def lowbit(x):
        return x & (-x)

    def query(self, x):
        ret = 0
        while x:
            ret += self.a[x]
            x -= BIT.lowbit(x)
        return ret

    def update(self, x, dt):
        while x <= self.n:
            self.a[x] += dt
            x += BIT.lowbit(x)

class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        n = len(queries)
        bit = BIT(n + m)
        pos = [0] * (m + 1)
        for i in range(n, n + m):
            pos[i - n + 1] = i + 1
            bit.update(i + 1, 1)
        ans = []
        for i, x in enumerate(queries):
            cur = pos[x]
            ans.append(bit.query(cur - 1))
            bit.update(cur, -1)
            #记录移动数字后，该数字在bit中的位置
            cur = pos[x] = n - i
            bit.update(cur, 1)
        return ans

Explain

此题解采用了树状数组(BIT)来高效地处理数组内元素的位置变动和查询。树状数组提供了两个关键操作：查询前缀和和更新元素，这使得我们可以在对数时间内查询任何元素的位置并更新。首先，初始化一个长度为 n+m 的树状数组，其中 n 是 queries 的长度，m 是排列 P 的长度。使用数组 pos 来记录排列 P 中每个元素的当前位置。初始时，P=[1,2,...,m] 并映射到树状数组的尾部，即 pos[1] = n+1, pos[2] = n+2，依此类推。处理 queries 时，对于每个查询 x，先通过 pos[x] 查询 x 在 P 中的位置，然后更新树状数组以反映 x 被移至数组前端的变化。这是通过减少当前位置的计数并在新位置（数组前端）增加计数来实现的。

时间复杂度: O(n log(m+n))

空间复杂度: O(m+n)

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

    @staticmethod
    def lowbit(x):
        return x & (-x)

    def query(self, x):
        ret = 0
        while x:
            ret += self.a[x]
            x -= BIT.lowbit(x)
        return ret

    def update(self, x, dt):
        while x <= self.n:
            self.a[x] += dt
            x += BIT.lowbit(x)

class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        n = len(queries)
        bit = BIT(n + m)
        pos = [0] * (m + 1)
        for i in range(n, n + m):
            pos[i - n + 1] = i + 1
            bit.update(i + 1, 1)
        ans = []
        for i, x in enumerate(queries):
            cur = pos[x]
            ans.append(bit.query(cur - 1))
            bit.update(cur, -1)
            cur = pos[x] = n - i
            bit.update(cur, 1)
        return ans

Explore

树状数组（Binary Indexed Tree, BIT），也被称为Fenwick Tree，是一种用于高效处理前缀和查询及单点更新的数据结构。在一个数组中，BIT可以在O(log n)时间复杂度内完成前缀和查询和元素的更新操作。BIT的核心在于它的存储方式，每个位置存储一段数组区间的和，而这个区间的大小依赖于该位置的二进制表示中最低位的1对应的值。这种结构使得更新一个元素影响的其他元素数量对数级，同样地，计算前缀和时跳过的元素也是对数级的，从而实现快速查询和更新。

在题解中，n 代表查询数组 queries 的长度，而 m 代表初始排列 P 的长度。树状数组的长度设为 n+m 是因为需要同时处理两部分内容：原始的排列 P 以及对于每个 queries 项的处理。每次一个元素 x 被查询，它都被移动到数组的前部，因此需要额外的空间来处理这些移动后的位置，以及保持数组 P 剩余部分的有效性。这种组合可以使得数组的索引和更新操作在整个处理过程中保持有效和高效。

将排列 P 中的元素映射到树状数组的尾部是为了方便在处理 queries 时，每次查询后可以将元素 x 移到数组的前端。这样做的目的是确保每次查询元素时，该元素前面的元素数量可以直接通过树状数组查询得到，而不影响后续元素的位置。此外，这种策略也便于利用树状数组的结构特性，通过逐步移动元素到数组前端，动态调整其位置，而不需要重建或大规模调整整个数据结构。

在查询元素 x 的位置后，题解中通过树状数组进行了两个关键的操作来实现将其移至前端：首先，利用树状数组的 `update` 函数减少当前 x 的位置的计数，这表示从当前位置移除了元素 x；其次，更新树状数组，在数组的前端（具体位置为 n-i, 其中 i 是当前查询的索引）增加计数，表示将元素 x 移到了前端。这种操作保证了元素 x 移动后，所有相关的前缀和和位置信息都能即时更新，从而在后续查询中能正确反映每个元素的新位置。