Solution to https://open.kattis.com/problems/moviecollection

MovieCollection.cpp

#include <iostream>
#include <cstring>

template<typename T>
T read() {
    T var;
    std::cin >> var;
    return var;
}
const int kMax = 100005;
int T[2*kMax];
int P[kMax];

inline int lowestOneBit(int i) {
    return i & -i;
}

void update(int i, int delta) {
    while (i < 2 * kMax) {
        T[i] += delta;
        i += lowestOneBit(i);
    }
}

int read(int i) {
    int sum = 0;
    while (i > 0) {
        sum += T[i];
        i -= lowestOneBit(i);
    }
    return sum;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    const int tests = read<int>();
    for (int test = 1; test <= tests; test++) {
        const int m = read<int>();
        const int r = read<int>();
        memset(T, 0, sizeof T);
        int nextIndex = 2 * kMax - 1;
        for (int v = m; v >= 1; v--) {
            update(nextIndex, 1);
            P[v] = nextIndex;
            nextIndex--;
        }
        for (int i = 0; i < r; i++) {
            const int a = read<int>();
            std::cout << read(P[a] - 1) << " ";
            update(P[a], -1);
            P[a] = nextIndex--;
            update(P[a], +1);
        }
        std::cout << "\n";
    }
    return 0;
}