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

핵심 아이디어

내 위에 DVD가 몇 개가 있는지 세그먼트 트리로 관리한다.

맨 밑에서부터 첫 번째라고 한다면 첫 상태는 다음과 같다. (맨 위를 N번째라고 하면 N = 5)

<aside> 💡

3번째 DVD를 뺀다면 3번째 DVD위에 즉 $[4,N]$범위의 DVD 개수를 구해 출력한다.

이후 3번째 DVD는 맨 위로 올라가기 때문에 그냥 $3$번째 DVD의 개수를 0으로 만들고 $N+1$의 DVD 개수를 1로 만든다. 이후 맨 위를 $N+1$로 보면 된다.

</aside>

즉 DVD의 꼭대기는 최대 $N+M$이 되고 세그먼트 트리의 배열 크기를 $N+M$로 잡아서 $O(Mlog(N+M))$으로 문제를 해결할 수 있다.

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

class Seg
{
    private:
        int n;
        vector<int> tree;

        void upd(int node, int start, int end, int idx, int val)
        {
            if(idx<start || end<idx) return;
            if(start == end){
                tree[node] = val;
                return;
            }
            
            int mid = start+end>>1;
            upd(2*node, start, mid, idx, val);
            upd(2*node+1, mid+1, end, idx, val);

            tree[node] = tree[2*node]+tree[2*node+1];
        }

        int qry(int node, int start, int end, int left, int right)
        {
            if(end<left || right<start) return 0;
            if(left<=start && end<=right) return tree[node];

            int mid = start+end>>1;
            int l = qry(2*node, start, mid, left, right);
            int r = qry(2*node+1, mid+1, end, left, right);

            return l+r;
        }

    public:
        void init(int n)
        {
            this->n = n;
            tree.resize(4*n);
        }

        void upd(int idx, int val){upd(1, 1, n, idx, val);}
        int qry(int left, int right){return qry(1, 1, n, left, right);}
};

int vtoi[100'001];

void solve()
{
    int n, m;
    Seg cnt;
    
    cin >> n >> m;
    int eidx = n;
    cnt.init(n+m);
    for(int i = n; i>0; i--){
        vtoi[i] = n-i+1;
        cnt.upd(i, 1);
    }

    for(int i = 0; i<m; i++){
        int e; cin >> e;
        cout << cnt.qry(vtoi[e]+1, eidx) <<' ';
        cnt.upd(vtoi[e], 0);
        vtoi[e] = ++eidx;
        cnt.upd(vtoi[e], 1);
    }

    cout << '\\n';
}

signed main()
{
    FASTIO;
    int _tc; cin >> _tc;
    while(_tc--) solve();    
    return 0;
}