Model the positions, not the movie IDs
A stack of DVDs changes position whenever a movie is requested, so a data structure indexed only by movie ID does not directly represent how many DVDs are above a movie. Instead, represent each possible stack position with an occupancy value: 1 means a DVD is there and 0 means it is empty. A Fenwick tree stores prefix sums of these values.
Let N be the number of movies and M the number of requests in one test case. Reserve positions 1 through M for future moves to the top, and put movie i at position M + i initially. Thus the initial stack, from top to bottom, occupies positions M + 1 through M + N. Store each movie’s current position in position[i], and initialize the Fenwick tree with a 1 at every occupied position.
Positions with smaller indices are closer to the top. If movie x is currently at position p, the number of DVDs above it is the sum of occupied positions strictly before p, namely the Fenwick prefix sum through p - 1.
To serve a request for x, first calculate and output that count. Then remove its old position from the tree, put it at next_top, and update position[x]. Start next_top at M and decrement it after each request. Each request therefore gets a fresh position above all positions used so far. This also handles repeated requests: after a movie is moved, its stored position points to its new location, and the next request counts zero DVDs above it if it is still on top.
Complexity
Each request performs one prefix-sum query and two point updates, each taking $O(\log(N+M))$ time. Initializing the occupied positions also takes $O(N\log(N+M))$ with the implementation below. Total time is $O((N+M)\log(N+M))$ per test case, with $O(N+M)$ space.
C++17 implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
using namespace std;
class FenwickTree {
vector<int> tree;
public:
explicit FenwickTree(int size) : tree(size + 1, 0) {}
void add(int index, int delta) {
for (int i = index; i < static_cast<int>(tree.size()); i += i & -i) {
tree[i] += delta;
}
}
int prefixSum(int index) const {
int sum = 0;
for (int i = index; i > 0; i -= i & -i) {
sum += tree[i];
}
return sum;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
while (testCases--) {
int n, m;
cin >> n >> m;
FenwickTree occupied(n + m);
vector<int> position(n + 1);
for (int movie = 1; movie <= n; ++movie) {
position[movie] = m + movie;
occupied.add(position[movie], 1);
}
int nextTop = m;
for (int request = 0; request < m; ++request) {
int movie;
cin >> movie;
int current = position[movie];
cout << occupied.prefixSum(current - 1) << (request + 1 == m ? '\n' : ' ');
occupied.add(current, -1);
position[movie] = nextTop;
occupied.add(nextTop, 1);
--nextTop;
}
}
return 0;
}