3653번: 영화 수집

https://www.acmicpc.net/problem/3653


$O(t(n+m \lg (n+m)))$

처음에 아래부터 n, n-1, ..., 2, 1 과 같이 쌓여 있을 것이다. 이후 들어올 쿼리 qi를 누적해서 써보면,
ai: n, n-1, ..., 2, 1, q0, q1, q2 ...
위 수열에서 x 이전의 항중 값이 x인 항의 가장 큰 번호를 f(x) 라 하자.
구하고자 하는 답은 i번째 항과 f(ai)번째 항 사이에 있는 수의 종류와 같음을 알 수 있다.
쿼리 x가 들어올 때마다 f(x)를 이용하여 bit를 업데이트 하는 방식으로 해결할 수 있다.

#include<cstdio>
const int MXN = 1e5;
int t, n, m, a[MXN + 1], bit[MXN * 2 + 1];
void update(int h) {
    for (; h <= n + m; h += h&-h) bit[h]++;
}
int query(int h) {
    int s = 0;
    for (; h; h -= h&-h) s += bit[h];
    return s;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n + m; i++) bit[i] = 0;
        int i = 1, x;
        for (; i <= n; i++) a[i] = n + 1 - i;
        for (; i <= n + m; i++) {
            scanf("%d", &x);
            printf("%d ", i - a[x] - 1 - query(i) + query(a[x]));
            update(a[x]);
            a[x] = i;
        }
        puts("");
    }
    return 0;
}