1409. Queries on a Permutation With Key

Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

• In the beginning, you have the permutation P=[1,2,3,…,m].
• For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].

Return an array containing the result for the given queries.

class Solution {
    int fenwick[2020];
    void update(int n, int v) {
        while(n < 2020) {
            fenwick[n] += v;
            n += n & -n;
        }
    }
    int query(int n) {
        int res = 0;
        while(n) {
            res += fenwick[n];
            n -= n & -n;
        }
        return res;
    }
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        memset(fenwick, 0, sizeof fenwick);
        vector<int> p(m + 1);
        for(int i = 1; i <= m; i++) {
            p[i] = m + i;
            update(p[i], 1);
        }
        vector<int> res;
        for(auto& q : queries) {
            res.push_back(query(p[q] - 1));
            update(p[q], -1);
            p[q] = m--;
            update(p[q], 1);
        }
        return res;
    }
};