[BOJ] 3653 영화수집

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

문제

상근이는 영화 DVD 수집가이다. 상근이는 그의 DVD 콜렉션을 쌓아 보관한다.

보고 싶은 영화가 있을 때는, DVD의 위치를 찾은 다음 쌓아놓은 콜렉션이 무너지지 않게 조심스럽게 DVD를 뺀다. 영화를 다 본 이후에는 가장 위에 놓는다.

상근이는 DVD가 매우 많기 때문에, 영화의 위치를 찾는데 시간이 너무 오래 걸린다. 각 DVD의 위치는, 찾으려는 DVD의 위에 있는 영화의 개수만 알면 쉽게 구할 수 있다. 각 영화는 DVD 표지에 붙어있는 숫자로 쉽게 구별할 수 있다.

각 영화의 위치를 기록하는 프로그램을 작성하시오. 상근이가 영화를 한 편 볼 때마다 그 DVD의 위에 몇 개의 DVD가 있었는지를 구해야 한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 영화의 수 n과 보려고 하는 영화의 수 m이 주어진다. (1 ≤ n, m ≤ 100,000) 둘째 줄에는 보려고 하는 영화의 번호가 순서대로 주어진다.

영화의 번호는 1부터 n까지 이며, 가장 처음에 영화가 쌓여진 순서는 1부터 증가하는 순서이다. 가장 위에 있는 영화의 번호는 1이다. 

출력

각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD를 가장 위에 놓는다.

풀이

이렇게 보면 RSQ 문제가 아니다. 하지만, 하나의 과정을 거치면 RSQ 문제로 변하게 된다.

총 M개의 쿼리가 들어올거기 때문에, 우린 모든 영화가 쿼리 전, 즉 처리하기 전에 1번은 m+1번째에, 2번은 m+2번째에, 3번은 m+3번째에... 이렇게 꽂혀있다고 생각해보자.

그리고, 영화 i번째를 보겠다고 하면 현재 i가 꽂혀있는 위치는 0으로 하고, 맨 위의 위치를 1로 한다.

그리고, i번째 영화 앞에 쌓여있는 영화의 개수는 (현재 i가 꽂혀있는 위치)-1 까지 영화가 꽂혀있는 개수가 된다.

기적같이 RSQ

코드

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int a[MAXN*4],sear[MAXN*4];
int n,m;
void update(int pos,int val)
{
    for(a[pos+=(n+m)]=val;pos>1;pos>>=1)
    {
        a[pos>>1]=a[pos]+a[pos^1];
    }
}
int query(int l,int r)
{
    int ans=0;
    for(l+=(n+m),r+=(n+m);l<r;l>>=1,r>>=1)
    {
        if(l&1) ans+=a[l++];
        if(r&1) ans+=a[--r];
    }
    return ans;
}
void main2()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
    {
        update(i+m,1),sear[i]=i+m;
    }
    int idx=m;
    for(int i=0;i<m;i++)
    {
        int x; scanf("%d",&x);
        --x;
        printf("%d ",query(0,sear[x]));
        update(sear[x],0);
        sear[x]=--idx;
        update(sear[x],1);
    }
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        memset(a,0,sizeof(a));
        memset(sear,0,sizeof(sear));
        main2();
        puts("");
    }
    return 0;
}