BOJ 17163(가희의 수열놀이 (Large))풀이

 

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

17163번: 가희의 수열놀이 (Large)

 

문제에 쿼리가 있어 세그라는 생각을 할 수 있지만 1 <= mod <= 2*10^9라고 쓰여있어서 세그 크기를 mod로 못 잡는다고 생각을 할 수 있다. 하지만 그 바로 앞에 Q의 범위를 보면 1 <= Q <= 10^6이라고 쓰여있는데 이 문제는 가장 뒤에서 나머지가 0부터 mod-1까지 모두 한 번 이상 있을 때 최소의 개수를 출력하는 문제이기 때문에 Q <mod라면 절대 0부터 mod-1까지 채울 수 없다. 그렇기 때문에 Q <mod 즉 10^6보다 큰 mod는 무조건 -1이 되므로 세그를 10^6로 만들고 Q <mod 일 때는 세그에서 처리하지 않고 -1만 출력해주면 된다. 이제 이런 문제가 해결됐으니 다음은 세그를 어떻게 만드냐 인데 여러 가지 방법이 있을 수 있지만 여기선 우선순위 큐를 이용한 풀이를 설명하겠다.

위에서 말했드시 값은 최대 10^6 이기 때문에 10^6 개의 우선순위 큐를 만들어 준다. 그리고 값이 추가될 때마다 그 값의 나머지 위치에 현재 추가되는 값의 위치를 추가해준다.(사실 우선순위 큐 없이 deque만 있어도 되지만 이 사실을 이 글을 쓸 때 깨달았다. 하지만 이미 코드를 우선순위 큐를 사용해서 풀었으니 우선순위 큐로 설명을 하겠다.)

값을 추가해준 뒤 세그에도 나머지 위치에 위치 값을 변경해준다. 이 때 세그는 min 세그를 만드는데 초기 값은 -1으로 한다. 이러면 전체 구간의 최솟값이 -1이라면 0부터 mod-1 중 하나 이상이 아직 나오지 않은 것이기 때문에 그때는 -1을 출력하고 만약 -1이 아닐 경우 min값을 현재까지 추가된 개수에 빼주고 +1을 해준다. 값을 추가를 했으니 빼주는 것도 해주면 되는데 빼는 것도 더하는 것과 같은 방법으로 해주면 된다. 가장 큰 값을 빼주고 뺀 나머지 값들 중 큰 값으로 세그에 변경을 해준다. 이때 세그에선 위에서 뺀 큰 값 위치에 빼준다.

이렇게 코드를 구성해주면 맞출 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>l;
vector<ll>tree(5000000);
vector<priority_queue<ll>>st(1001000);
ll seg(ll n,ll s,ll e){
    if(s==e){return tree[n]=-1;}
    seg(n*2,s,(s+e)/2);
    seg(n*2+1,(s+e)/2+1,e);
    return tree[n]=min(tree[n*2],tree[n*2+1]);
}
void change(ll n,ll s,ll e,ll idx,ll v){
    if(idx>e||idx<s)return;
    if(s==e){tree[n]=v;return;}
    ll md=(s+e)/2;
    change(n*2,s,md,idx,v);
    change(n*2+1,md+1,e,idx,v);
    tree[n]=min(tree[n*2],tree[n*2+1]);
}
ll mn(ll n,ll s,ll e,ll left,ll right){
    if(left>e||right<s){return 1000000001;}
    if(left<=s&&e<=right){return tree[n];}
    return min(mn(n*2,s,(s+e)/2,left,right),mn(n*2+1,(s+e)/2+1,e,left,right));
}
int main()
{
    ll a,b,c,d;
    scanf("%lld %lld",&a,&b);
    seg(1,0,1000100);
    ll cnt=0;
    for(int i=0;i<a;i++){
        scanf("%lld ",&c);
        if(c==1){
            scanf("%lld",&d);
            if(a<b)continue;
            d%=b;
            cnt++;
            st[d].push(cnt);
            l.push_back(d);
            change(1,0,b-1,d,cnt);
        }
        if(c==2){
            if(cnt>0){
                if(a<b)continue;
               ll ty=l[cnt-1];
                l.pop_back();
                cnt--;
                st[ty].pop();
                if(st[ty].size()==0)change(1,0,b-1,ty,-1);
                else change(1,0,b-1,ty,st[ty].top()); 
            }
        }
        if(c==3){
            if(a<b){printf("-1\n");continue;}
            ll yu=tree[1];
            if(yu==-1)printf("-1\n");
            else{
                printf("%lld\n",cnt-yu+1);
            }
        }
    }
}