boj3653_영화수집
- 접근 방식이 일반적인 세그랑 달라 약간 신선!
#include<iostream>
#include<vector>
using namespace std;
void update(vector<int> &v, int i, int diff) {
while (i < v.size()) {
v[i] += diff;
i += (i&-i);
}
}
int sum(vector<int> &v, int i) {
int ans = 0;
while (i > 0) {
ans += v[i];
i -= (i&-i);
}
return ans;
}
int main() {
int t, n, m,num;
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
vector<int> v(n+m+10,0);
vector<int> idx(n+1);
for (int i = 1; i <= n; i++) {
idx[i] = m+i;
update(v, m + i, 1);
}
int nowidx = m;
for (int i = 0; i < m; i++) {
scanf("%d", &num);
int num_idx = idx[num];
idx[num] = nowidx;
int cnt = sum(v, num_idx - 1);
update(v, num_idx, -1);
update(v, nowidx, 1);
printf("%d ", cnt);
nowidx--;
}
printf("\n");
}
}
