1409. 查询带键的排列

解法一：模拟

记录每个数的下标位置，每次查询直接给出结果，然后更新下标数组：比该位置小的都加1，该位置的值更新为0。
时间复杂度：

class Solution {
    public int[] processQueries(int[] queries, int m) {
        int[] index = new int[m + 1];
        for (int i = 1; i <= m; ++i) {
            index[i] = i - 1;
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            ans[i] = index[queries[i]];
            for (int j = 1; j <= m; ++j) {
                if (index[j] < ans[i]) {
                    index[j]++;
                }
            }
            index[queries[i]] = 0;
        }
        return ans;
    }
}

解法二：树状数组

参考：https://leetcode-cn.com/problems/queries-on-a-permutation-with-key/solution/cha-xun-dai-jian-de-pai-lie-by-leetcode-solution/
关于区间查询、单点更新的树状数组，参见：https://www.yuque.com/herormluzhan/uup252/noom0v

class Solution {
    private class TreeArray {
        // 树状数组，下标从1开始
        private int[] value;
        // 长度
        private final int length;
        public TreeArray(int n) {
            length = n;
            value = new int[length + 1];
        }
        public TreeArray(int[] arr) {
            length = arr.length;
            value = new int[length + 1];
            for (int i = 1; i <= length; ++i) {
                update(i, arr[i - 1]);
            }
        }
        /**
         * k：x的二进制形式从最低位到最高位连续0的个数
         * 求2^k
         *
         * @param x 非负整数
         * @return 2^k
         */
        private int lowBit(int x) {
            return x & (-x);
        }
        /**
         * 原数组的第i个元素增加k，更新树状数组的值
         *
         * @param i 原数组元素索引位置
         * @param k 更新值
         */
        public void update(int i, int k) {
            while (i <= length) {
                value[i] += k;
                i += lowBit(i);
            }
        }
        /**
         * 求[1,i]这i个数的和
         *
         * @param i 索引位置
         * @return 前i个数的和
         */
        public int getSum(int i) {
            int sum = 0;
            while (i >= 1) {
                sum += value[i];
                i -= lowBit(i);
            }
            return sum;
        }
    }
    public int[] processQueries(int[] queries, int m) {
        int[] ans = new int[queries.length];
        // 1 表示有数占据；0 表示没有数占据
        // 一开始将原来的 m 个数放到树状数组的最后 m 位
        TreeArray t = new TreeArray(queries.length + m);
        for (int i = 1; i <= m; ++i) {
            t.update(i + queries.length, 1);
        }
        // pos[i] 表示 i 在树状数组中的位置
        int[] pos = new int[m + 1];
        for (int i = 1; i <= m; ++i) {
            pos[i] = i + queries.length;
        }
        for (int i = 0; i < queries.length; ++i) {
            int curPos = pos[queries[i]];
            ans[i] = t.getSum(curPos - 1);
            // 从原来位置移动到队列首位
            // 将树状数组的原来位置从 1 置为 0，将新位置从 0 置为 1
            t.update(curPos, -1);
            pos[queries[i]] = queries.length - i;
            t.update(pos[queries[i]], 1);
        }
        return ans;
    }
}