[3653번] 영화 수집

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 펜윅 트리 :: http://www.crocus.co.kr/666

2. 세그먼트 트리 :: http://www.crocus.co.kr/648

문제의 내용은 다음과 같다.

dvd는 1번부터 n번까지

1　　-> n층

2　　-> n-1층

3　　-> n-2층

...　　

n - 1 -> 2층

n　　-> 1층

이런식으로 차곡차곡 쌓인다.

만약 3번 dvd를 빼고싶다면 다음과 같이 된다.

3　　-> n층

1　　-> n-1층

2　　-> n-2층

...　　

n - 1 -> 2층

n　　-> 1층

이 방식을 토대로 세그먼트 트리 혹은 펜윅 트리를 이용하여 구현하고자 한다.

이 코드는 펜윅 트리를 이용하였고, query는 sum을 기반으로 한다.

        for (int i = 1; i <= n; i++)
        {
            floor[i] = n - i + 1;
            update(tree, i, 1);
        }

이 코드는 초기화 단계로 1번 dvd은 n층에, 2번 dvd는 n-1층에 ... n번 dvd는 1층에 있는 것을 표현하고

펜윅 트리에 업데이트 해주는 과정이다.

이렇게 한다면 펜윅 트리(펜윅 트리로 접근하기 힘들다면 세그먼트 트리를 생각하면서 펜윅 트리를 이용해도 된다.)에는

이따가 query를 이용하기 위한 값들이 쌓일 것이다.

// 펜윅 트리에 쌓인 모든 dvd - 펜윅 트리 자신의 위치 아래까지 쌓인 dvd = 자신 보다 위에 있는 dvd수 
printf("%lld ", query(tree, 200001) - query(tree, floor[val]));
            
// 자신의 층수에 dvd를 -1로 하여 자신의 층수에는 이제 dvd가 없도록 한다.
update(tree, floor[val], -1);
            
// 123층에 dvd가 있었고 1층 dvd를 뺐으면 dvd는 4층으로 가야한다.            
floor[val] = next++;
        
// 4층에 쌓는 과정            
update(tree, floor[val], 1);

이 과정에서 query(tree, 200001)의 의미는 현재 n과 m의 범위가 100000이다.

따라서 100000 + 100000 = 200000이므로 최대 층수는 200000까지밖에 될 수 없다.

이를 이용하여 아에 처음부터 범위가 200000인 펜윅 트리라고 생각하고 진행하는 방식이다.

위의 printf( query() - query() )는 구간 합을 구할 때 이용하는 방식과 같다.

저렇게 빼준다면 전체 dvd - 자신보다 밑에 있는 dvd = 자신보다 위에 있는 dvd가 될 것이다.

그리고 floor[val] = next++를 통해 뺏던 dvd를 가장 꼭대기 층에 넣어준다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
ll query(vector<ll> &tree, int i)
{
    ll ans = 0;
    while (i > 0)
    {
        ans += tree[i];
        i -= (i & -i);
    }
    return ans;
}
 
void update(vector<ll> &tree, int i, ll diff)
{
    while (i < tree.size())
    {
        tree[i] += diff;
        i += (i & -i);
    }
}
 
int main()
{
    int tCase;
    scanf("%d", &tCase);
 
    while (tCase--)
    {
        vector<ll> tree(200002);
        vector<int> floor(200002);
 
        int n,m;
        scanf("%d %d", &n, &m);
 
        for (int i = 1; i <= n; i++)
        {
            floor[i] = n - i + 1;
            update(tree, i, 1);
        }
        
        // dvd를 빼고 넣게 되는 다음 층수
        int next = n + 1;
 
        while (m--)
        {
            int val;
            scanf("%d", &val);
 
            // 펜윅 트리에 쌓인 모든 dvd - 펜윅 트리 자신의 위치 아래까지 쌓인 dvd = 자신 보다 위에 있는 dvd수 
            printf("%lld ", query(tree, 200001) - query(tree, floor[val]));
 
            // 자신의 층수에 dvd를 -1로 하여 자신의 층수에는 이제 dvd가 없도록 한다.
            update(tree, floor[val], -1);
            // 123층에 dvd가 있었고 1층 dvd를 뺐으면 dvd는 4층으로 가야한다.
            floor[val] = next++;
            // 4층에 쌓는 과정
            update(tree, floor[val], 1);
        }
        printf("\n");
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>