DID : PS 1문제 (2023/04/07)

간단히 한 문제 풀었다.
BOJ 13547 수열과 쿼리 5
문제가 꽤나 어려웠는데, 수열을 주고 i~j 인덱스에 서로 다른 수의 개수를 출력하는 문제다. 처음 보고 뭐지 했다. 우선 하나의 쿼리를 처리하려고 생각했을 때, 값이 1~1,000,000 사이니까 i~j까지 돌면서 값 인덱스에 1씩 더하면서 서로 다른 것의 개수를 센다고 생각하면 O(N)이 들고, Q개 쿼리를 처리할려면 O(QN)이 걸리는데, 이런 naive한 풀이는 역시 어림도 없다.
한 쿼리를 처리한 정보를 가지고 다음 쿼리를 처리하려고 생각해도, i와 j 모두 하나씩 움직일때 횟수가 O(N)이라 거기서 거기, 즉 똑같이 O(QN)이 걸리므로 조금 더 생각 해 봐야 한다.

이 문제는 쿼리를 정렬해서 푸는 오프라인 쿼리로 푸는게 정해이다. 즉, Mo's algorithm을 써 시간복잡도를 줄일 수 있다. 정렬 방법은 j를 sqrtN으로 나눠서 몫을 랭크로 매기고, 우선 랭크순으로 정렬한다. 같은 랭크에 대해서는 i를 오름차순으로 정렬하면 된다. 이렇게 하면 시간복잡도가 다음과 같다.

(1) j의 이동 횟수 : 다음 쿼리가 같은 랭크면 sqrtN보다 작게 움직이고, 총 쿼리 수가 Q개니까 최대 QsqrtN이다. / 다음 쿼리가 다른 랭크면 최대 N만큼 움직인다. 랭크 전이는 최대 sqrtN번 일어나니까 이 경우는 NsqrtN, 즉 총 이동횟수는 O((Q + N)sqrtN)

(2) i의 이동횟수 : 같은 랭크 내에서 오름차순이니까 최대 N번, 총 랭크 수가 sqrtN이니까 NsqrtN회 이동한다. / 랭크 전이 시에는 최대 N번 이동하고, 랭크 전이가 최대 sqrtN번이니까 총 이동횟수는 O(NsqrtN)이다.

즉, 전체 시간 복잡도는 O(QN)에서 O((Q+N)sqrtN)으로 줄었다. 이렇게 하면 문제를 해결할 수 있다.

#include<bits/stdc++.h>
using namespace std;
typedef vector<pair<int,pair<int,int> > > vipii;
typedef pair<int,pair<int,int> > pipii;
typedef pair<int,int> pii;
int seq[(int)1e5+7], sq;
int ans[(int)1e5+7];
int arr[(int)1e6+7], ret;
vipii q;
int div(int t){return t / sq;}
bool cmp(pipii a,pipii b)
{
    if(div(a.second.second) == div(b.second.second))
        return a.second.first < b.second.first;
    return div(a.second.second) < div(b.second.second);
}

int transition(pii s, pii e) //[s.first, s.second] -> [e.first,e.second]
{
    if(s.second < e.second)
        while(s.second != e.second)
            if(arr[seq[++s.second]]++ == 0)
                ret++;
    if(e.first < s.first)
        while(s.first != e.first)
            if(arr[seq[--s.first]]++ == 0)
                ret++;
    if(s.second > e.second)
        while(s.second != e.second)
            if(--arr[seq[s.second--]] == 0)
                ret--;
    if(e.first > s.first)
        while(s.first != e.first)
            if(--arr[seq[s.first++]] == 0)
                ret--;
    return ret;
}
int main()
{
    int n; scanf("%d",&n); sq = (int)sqrt(n);
    for(int i =1; i<= n; i++) scanf("%d", seq+i);
    int m; scanf("%d",&m);

    for(int i = 1; i<= m; i++)
    {
        int a,b; scanf("%d %d", &a,&b);
        q.push_back({i,{a,b}});
    }
    sort(q.begin(),q.end(), cmp);
    int ba = 1, bb = 1;
    arr[seq[1]]++; ret = 1;
    for(auto i : q)
    {
        ans[i.first] = transition({ba,bb},i.second);
        //printf("%d %d %d %d %d %d\n",ba,bb, i.second.first, i.second.second, ans[i.first], bans);
        ba = i.second.first;
        bb = i.second.second;
    }
    for(int i = 1; i<= m; i++) printf("%d\n", ans[i]);
}