1409. Queries on a Permutation With Key

数组 1到M ，输入查询数组，每次查询元素所在的下标，查询完后元素要往头部移动，M不会超过1000

暴力解法

因为M的数量限制，因此可以使用暴力解法进行遍历和移动元素

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        vector<int> a(m);
        a[0]=1;
        vector<int> res;
        for(int i=1;i<a.size();++i) {
            a[i]=a[i-1]+1;
        }
        
        for(int i=0;i<queries.size();++i) {
            int target=queries[i];
            int j;
            for(j=0;j<a.size();++j) {
                if (a[j] == target) {
                    res.push_back(j);
                    break;
                }
            }
            for(int k=j;k>0;--k) {
                a[k]=a[k-1];
            }
            a[0]=target;
        }
        return res;
    }
};

前缀和解法

使用 fenwick tree 对元素更新求前缀和问题进行加速，把要查询的下标结果看成是元素的前缀和，元素移动需要把 tree 中的元素进行更新加一或者减一

class Fenwick {
public:
    Fenwick(int n) : val(n) {}
    
    int query(int i) {
        int s=0;
        while(i>0) {
            s+=val[i];
            i-=i&-i;
        }
        return s;
    }
    
    void update(int i, int delta) {
        while(i<val.size()) {
            val[i]+=delta;
            i+=i&-i;
        }
    }
    
    vector<int> val;
};

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        Fenwick tree((m<<1)+1);
        vector<int> pos(m+1);
        vector<int> res;
        
        for(int i=1;i<=m;++i) {
            pos[i]=i+m;
            tree.update(i+m, 1);
        }
        
        for(int q : queries) {
            res.push_back(tree.query(pos[q]-1));
            tree.update(pos[q], -1);
            pos[q]=m--;
            tree.update(pos[q], 1);
        }
        return res;
    }
};

#tree #前缀和

135. Candy 分糖果 15. 3Sum