BOJ 13546 - 수열과 쿼리 4

문제 링크 : https://www.acmicpc.net/problem/13546

문제 태그

Mo's algorithm

문제 소개

1보다 크거나 같고, K보다 작거나 같은 수로 이루어져 있는 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• l r: max{|x − y| : l ≤ x, y ≤ r and $A_x$ = $A_y$} 을 출력한다.

문제 풀이

일단 각 쿼리의 구간내에서 각 숫자별로 그 숫자들이 존재하는 위치들을 전부 알고 있어야 쿼리의 질문에 대한 답을 구할 수 있다. "구간 별로 숫자의 집합을 관리한다." 는 Mo's algorithm을 통해서 해줄 수 있다. 

deque 를 숫자 범위의 갯수만큼 만들어서 각 deque별로 그 숫자가 위치하고 있는 곳을 전부 관리하자. 쿼리의 구간이 바뀔 때 마다 바뀌는 구간의 숫자들에 대해서 해당 deque의 앞/뒤 에 위치를 추가/삭제 해주면 된다. 따라서 구간내에서 각 숫자별로 그 숫자들이 존재하는 위치를 전부 알고 있을 수 있다.

쿼리의 질문에 대한 답을 처리하려고 해보자. 이때 모든 deque에 대해서 가장 앞의 위치와 가장 뒤의 위치를 알고 있으므로 다 한 번씩 구해서 비교를 하고 싶지만, 그렇게 하면 시간초과가 나게 된다. 이 방법이 비효율적인 이유는 무엇일까? 아예 존재하지 않는 숫자에 대해서도 보며, 이미 알고 있는 값들에 대해서도 모두 다시 구해야 한다는 것이다. 이런 이유로 비효율 적인 경우에는 보통 "바뀐 부분만 고려" 하는 것이 이에 대한 해답이 되는 경우가 많다.

이 문제의 해결방법은 구간변화 당시에 답도 함께 변화시키는 것이다. Mo's는 숫자의 집합을 관리하는 것에 굉장히 좋게 활용되기 때문에 이번에도 각 숫자별로 가장 먼 거리 값을 다 모아서 관리할 것이다. 즉, 변경점으로 인해 수가 k인 위치의 가장 먼 거리가 3에서 1이 되었다면 cnt[3]--; cnt[1]++을 하는 방식처럼 말이다. 

이제 우리는 각 쿼리의 상황별로 cnt의 배열값이 1이상인 가장 큰 곳을 구해야 한다. 당연히 배열 전체를 탐색하면 시간초과가 나게 되고, 이를 변화마다 관리할 수도 없다. 따라서 이를 해결하기 위해 추가적인 트릭을 사용해 주어야 한다. cnt 전체 배열을 sqrt개씩 나눠서 추가로 관리해주자. 즉 1~100이 범위라면 1~10->new1, 11~20->new2, 21~30->new3 이런식으로 말이다. 그렇다면 배열의 전체를 탐색하고 가장 큰 위치를 찾는 것이 아니라, 구역을 1차적으로 탐색하여 그 위치가 속한 구역을 찾은 뒤, 그 구역 내에서 한 번더 탐색해서 최종적으로 위치를 찾아주면 된다. 이로써 숫자의 최대범위 만큼 걸리던 탐색시간을 루트로 줄일 수 있게 되고, 시간안에 작동을 할 수 있게 된다.

여기까지만 보면 정말 좋은 문제이지만 너무 시간제한이 빡빡해서 deque를 쓰면 시간초과가 나고 list를 써야 맞는 경우가 많다. 마이너스 요인이다. 주의해야한다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
struct q{
    ll idx,s,e;
};
 
q qer[1010101];
ll ans[1010101];
list<ll> cnt[1010101];
 
ll dcnt[101010];
ll sqcnt[101010];
 
ll arr[1010101];
ll sqn;
ll now;
ll lf,rf;
 
bool sf(q a,q b)
{
    if(a.s/sqn!=b.s/sqn) return a.s<b.s;
    return a.e<b.e;
}
 
void mib(ll s, ll e)
{
    ll i;
    for(i=e;i>=s;i--)
    {
        ll j=arr[i];
        if(cnt[j].size()>=2)
        {
            ll dis=cnt[j].back()-cnt[j].front();
            dcnt[dis]--;
            sqcnt[dis/400]--;
        }
        cnt[j].pop_back();
        if(cnt[j].size()>=2)
        {
            ll dis=cnt[j].back()-cnt[j].front();
            dcnt[dis]++;
            sqcnt[dis/400]++;
        }
    }
}
 
void mif(ll s, ll e)
{
    ll i;
    for(i=s;i<=e;i++)
    {
        ll j=arr[i];
        if(cnt[j].size()>=2)
        {
            ll dis=cnt[j].back()-cnt[j].front();
            dcnt[dis]--;
            sqcnt[dis/400]--;
        }
        cnt[j].pop_front();
        if(cnt[j].size()>=2)
        {
            ll dis=cnt[j].back()-cnt[j].front();
            dcnt[dis]++;
            sqcnt[dis/400]++;
        }
    }
}
 
void plf(ll s, ll e)
{
    ll i;
    for(i=e;i>=s;i--)
    {
        ll j=arr[i];
        if(cnt[j].size()>=2)
        {
            ll dis=cnt[j].back()-cnt[j].front();
            dcnt[dis]--;
            sqcnt[dis/400]--;
        }
        cnt[j].push_front(i);
        ll dis=cnt[j].back()-cnt[j].front();
        dcnt[dis]++;
        sqcnt[dis/400]++;
    }
}
 
void plb(ll s, ll e)
{
    //printf("%lld %lld+\n",s,e);
    ll i;
    for(i=s;i<=e;i++)
    {
        ll j=arr[i];
        if(cnt[j].size()>=2)
        {
            ll dis=cnt[j].back()-cnt[j].front();
            dcnt[dis]--;
            sqcnt[dis/400]--;
        }
        cnt[j].push_back(i);
        ll dis=cnt[j].back()-cnt[j].front();
        dcnt[dis]++;
        sqcnt[dis/400]++;
    }
}
 
 
int main()
{
    ll i,j,k,l,m,n,Q;
    scanf("%lld %lld",&n,&m);
    sqn=sqrt(n);
    for(i=1;i<=n;i++)
        scanf("%lld",&arr[i]);
 
    scanf("%lld",&Q);
    for(i=1;i<=Q;i++)
    {
        scanf("%lld %lld",&qer[i].s,&qer[i].e);
        qer[i].idx=i;
    }
 
    sort(qer+1,qer+1+Q,sf);
 
 
    plf(qer[1].s,qer[1].e);
    for(i=260;i>=0;i--)
    {
        if(sqcnt[i]!=0)
        {
            for(j=399;j>=0;j--)
            {
                if(dcnt[i*400+j]!=0) {
                    now=i*400+j;
                    break;
                }
            }
            break;
        }
    }
    ans[qer[1].idx]=now;
 
    lf=qer[1].s;
    rf=qer[1].e;
 
    for(i=2;i<=Q;i++)
    {    
        if(qer[i].s<lf) plf(qer[i].s,lf-1);
        if(qer[i].e>rf) plb(rf+1,qer[i].e);
        if(qer[i].s>lf) mif(lf,qer[i].s-1);
        if(qer[i].e<rf) mib(qer[i].e+1,rf);
 
        lf=qer[i].s;
        rf=qer[i].e;
        
        for(k=260;k>=0;k--)
        {
            if(sqcnt[k]!=0)
            {
                for(j=399;j>=0;j--)
                {
                    if(dcnt[k*400+j]!=0) {
                        now=k*400+j;
                        break;
                    }
                }
                break;
            }
        }
        ans[qer[i].idx]=now;
    }
 
    for(i=1;i<=Q;i++)
        printf("%lld\n",ans[i]);
}