# 1409. Queries on a Permutation With Key¶

• Time: $O(q\log m)$
• Space: $O(q + m)$
  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 class FenwickTree { public: FenwickTree(int n) : sums(n + 1) {} void update(int i, int delta) { while (i < sums.size()) { sums[i] += delta; i += lowbit(i); } } int get(int i) const { int sum = 0; while (i > 0) { sum += sums[i]; i -= lowbit(i); } return sum; } private: vector sums; static inline int lowbit(int i) { return i & -i; } }; class Solution { public: vector processQueries(vector& queries, int m) { vector ans; // Map [-m, m] to [0, 2 * m]. FenwickTree tree(2 * m + 1); unordered_map numToIndex; for (int num = 1; num <= m; ++num) { numToIndex[num] = num + m; tree.update(num + m, 1); } int nextEmptyIndex = m; // Map 0 to m. for (const int query : queries) { const int index = numToIndex[query]; ans.push_back(tree.get(index - 1)); // Move query from index to nextEmptyIndex. tree.update(index, -1); tree.update(nextEmptyIndex, 1); numToIndex[query] = nextEmptyIndex--; } return ans; } }; 
  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 class FenwickTree { public FenwickTree(int n) { sums = new int[n + 1]; } public void update(int i, int delta) { while (i < sums.length) { sums[i] += delta; i += lowbit(i); } } public int get(int i) { int sum = 0; while (i > 0) { sum += sums[i]; i -= lowbit(i); } return sum; } private int[] sums; private static int lowbit(int i) { return i & -i; } } class Solution { public int[] processQueries(int[] queries, int m) { int[] ans = new int[queries.length]; // Map [-m, m] to [0, 2 * m]. FenwickTree tree = new FenwickTree(2 * m + 1); Map numToIndex = new HashMap<>(); for (int num = 1; num <= m; ++num) { numToIndex.put(num, num + m); tree.update(num + m, 1); } int nextEmptyIndex = m; // Map 0 to m. for (int i = 0; i < queries.length; ++i) { final int query = queries[i]; final int index = numToIndex.get(query); ans[i] = tree.get(index - 1); // Move query from index to nextEmptyIndex. tree.update(index, -1); tree.update(nextEmptyIndex, 1); numToIndex.put(query, nextEmptyIndex--); } return ans; } } 
  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 class FenwickTree: def __init__(self, n: int): self.sums = [0] * (n + 1) def update(self, i: int, delta: int) -> None: while i < len(self.sums): self.sums[i] += delta i += FenwickTree.lowbit(i) def get(self, i: int) -> int: summ = 0 while i > 0: summ += self.sums[i] i -= FenwickTree.lowbit(i) return summ @staticmethod def lowbit(i: int) -> int: return i & -i class Solution: def processQueries(self, queries: List[int], m: int) -> List[int]: ans = [] # Map [-m, m] to [0, 2 * m]. tree = FenwickTree(2 * m + 1) numToIndex = {num: num + m for num in range(1, m + 1)} for num in range(1, m + 1): tree.update(num + m, 1) nextEmptyIndex = m # Map 0 to m. for query in queries: index = numToIndex[query] ans.append(tree.get(index - 1)) # Move query from index to nextEmptyIndex. tree.update(index, -1) tree.update(nextEmptyIndex, 1) numToIndex[query] = nextEmptyIndex nextEmptyIndex -= 1 return ans