Truy vấn trên hoán vị với khóa (Queries on a Permutation With Key) trong C++

Cho mảng queries (giá trị 1..m) và số m. Khởi tạo hoán vị P = [1,2,...,m]. Với mỗi queries[i]: tìm vị trí (0-index) của nó trong P, sau đó di chuyển nó lên đầu P. Trả về mảng các vị trí tìm được.

Ví dụ

Đầu vào: queries = [3,1,2,1], m = 5
Đầu ra: [2,1,2,1].

Thuật toán mô phỏng

Vì m ≤ 1000 (constraints thường), mô phỏng trực tiếp với vector đủ nhanh O(m * q).

1. Khởi tạo P = {1,2,...,m}.
2. Với mỗi truy vấn x:
   • Tìm chỉ số pos của x trong P (linear search).
   • Xóa x khỏi P, chèn vào đầu.
   • Ghi pos vào kết quả.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector processQueries(vector& q, int m) {
        vector P(m);
        iota(P.begin(), P.end(), 1);
        vector ans;
        for (int x : q) {
            int pos = find(P.begin(), P.end(), x) - P.begin();
            ans.push_back(pos);
            P.erase(P.begin() + pos);
            P.insert(P.begin(), x);
        }
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(Q * M) - Q truy vấn, mỗi truy vấn tìm/xóa/chèn O(M).
• Không gian: O(M) lưu hoán vị.

Kết quả kiểm thử

Đầu vào: {3,1,2,1}, 5
Đầu ra: [2,1,2,1]