Queries on a Permutation With Key solution and explanation

def process_queries(queries, m):
    P = list(range(1, m + 1))
    result = []
    for q in queries:
        index = P.index(q)
        result.append(index)
        P.pop(index)
        P.insert(0, q)
    return result

queries = [3, 1, 2, 1]
m = 5
result = process_queries(queries, m)
print(result)

import java.util.ArrayList;
import java.util.List;

public class QueriesProcessor {
    public static List<Integer> processQueries(int[] queries, int m) {
        List<Integer> P = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= m; i++) P.add(i);
        for (int q : queries) {
            int index = P.indexOf(q);
            result.add(index);
            P.remove(index);
            P.add(0, q);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] queries = {3, 1, 2, 1};
        int m = 5;
        List<Integer> result = processQueries(queries, m);
        for (int r : result) {
            System.out.print(r + " ");
        }
    }
}

#include <iostream>
#include <vector>

std::vector<int> processQueries(std::vector<int>& queries, int m) {
    std::vector<int> P(m);
    std::vector<int> result;
    for(int i = 0; i < m; ++i) P[i] = i + 1;
    for(auto q : queries) {
        auto it = std::find(P.begin(), P.end(), q);
        int index = std::distance(P.begin(), it);
        result.push_back(index);
        P.erase(it);
        P.insert(P.begin(), q);
    }
    return result;
}

int main() {
    std::vector<int> queries = {3, 1, 2, 1};
    int m = 5;
    std::vector<int> result = processQueries(queries, m);
    for(int r : result) {
        std::cout << r << " ";
    }
    return 0;
}

function processQueries(queries, m) {
    let P = Array.from({length: m}, (_, i) => i + 1);
    let result = [];
    queries.forEach(q => {
        let index = P.indexOf(q);
        result.push(index);
        P.splice(index, 1);
        P.unshift(q);
    });
    return result;
}

let queries = [3, 1, 2, 1];
let m = 5;
let result = processQueries(queries, m);
console.log(result);

#include <stdio.h>

void processQueries(int* queries, int queriesSize, int m, int* returnSize, int* result) {
    int P[m];
    for(int i = 0; i < m; i++) {
        P[i] = i + 1;
    }
    for(int i = 0; i < queriesSize; i++) {
        int index = 0;
        while(P[index] != queries[i]) index++;
        result[i] = index;
        int value = P[index];
        for(int j = index; j > 0; j--) {
            P[j] = P[j - 1];
        }
        P[0] = value;
    }
    *returnSize = queriesSize;
}

int main() {
    int queries[] = {3, 1, 2, 1};
    int m = 5;
    int result[4];
    int returnSize;
    processQueries(queries, 4, m, &returnSize, result);
    for(int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public static List<int> ProcessQueries(int[] queries, int m) {
        List<int> P = new List<int>();
        List<int> result = new List<int>();
        for (int i = 1; i <= m; i++) P.Add(i);
        foreach (int q in queries) {
            int index = P.IndexOf(q);
            result.Add(index);
            P.RemoveAt(index);
            P.Insert(0, q);
        }
        return result;
    }

    public static void Main() {
        int[] queries = {3, 1, 2, 1};
        int m = 5;
        List<int> result = ProcessQueries(queries, m);
        foreach (int r in result) {
            Console.Write(r + " ");
        }
    }
}

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, idx, delta):
        while idx <= self.size:
            self.tree[idx] += delta
            idx += idx & -idx

    def query(self, idx):
        sum_ = 0
        while idx > 0:
            sum_ += self.tree[idx]
            idx -= idx & -idx
        return sum_


def process_queries(queries, m):
    max_size = m + len(queries)
    bit = FenwickTree(max_size)
    position = {i + 1: i + len(queries) for i in range(m)}
    result = []
    for i, q in enumerate(queries):
        current_pos = position[q]
        res = bit.query(current_pos) - bit.query(i)
        result.append(res)
        # Update the position in BIT and to new index i
        bit.update(current_pos + 1, -1)
        position[q] = i
        bit.update(i + 1, 1)
    return result

queries = [3, 1, 2, 1]
m = 5
result = process_queries(queries, m)
print(result)

func processQueries(queries []int, m int) []int {
	p := make([]int, m)
	for i := range p {
		p[i] = i + 1
	}
	ans := []int{}
	for _, v := range queries {
		j := 0
		for i := range p {
			if p[i] == v {
				j = i
				break
			}
		}
		ans = append(ans, j)
		p = append(p[:j], p[j+1:]...)
		p = append([]int{v}, p...)
	}
	return ans
}

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	c := make([]int, n+1)
	return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) lowbit(x int) int {
	return x & -x
}

func (this *BinaryIndexedTree) update(x, delta int) {
	for x <= this.n {
		this.c[x] += delta
		x += this.lowbit(x)
	}
}

func (this *BinaryIndexedTree) query(x int) int {
	s := 0
	for x > 0 {
		s += this.c[x]
		x -= this.lowbit(x)
	}
	return s
}

func processQueries(queries []int, m int) []int {
	n := len(queries)
	pos := make([]int, m+1)
	tree := newBinaryIndexedTree(m + n)
	for i := 1; i <= m; i++ {
		pos[i] = n + i
		tree.update(n+i, 1)
	}
	ans := []int{}
	for i, v := range queries {
		j := pos[v]
		tree.update(j, -1)
		ans = append(ans, tree.query(j))
		pos[v] = n - i
		tree.update(n-i, 1)
	}
	return ans
}