[C++] 13547번 수열과 쿼리 5 - 오프라인 쿼리, mo's

1. 문제

• 길이가 N인 수열 Ai이 주어진다. 다음 쿼리를 수행하는 프로그램을 작성하시오.
• i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력하라.

<입력>

• -1-   수열의 크기 \(N(1 \leq N \leq 100,000)\)
• -2-    A1, A2, ..., AN \((1 \leq A_{i} \leq 1,000,000))\)
• -3-   쿼리의 개수 M \((1 \leq M \leq 100,000)\)
• -M개-   쿼리 i, j \((1 \leq i \leq j \leq N)\)

<출력>

• 한 줄에 하나씩 각각의 쿼리의 정답을 출력하라.

2. 재정의

• X

3. 해결 방법

• 쿼리 정렬로 i/sqrt(N)에 따라 정렬하고 만약 같다면 j가 큰 걸로 오름차순 정렬하기
• isIn[A[i]]에 넣고 없으면 cnt++. 있으면 그대로
• 제거하면 isIn[A[i]]--, 제거해서 0이면 cnt-- 아니면 그대로
• 추가하면 isIn[A[i]]++, 추가하기 전에 0이면 cnt++ 아니면 그대로

4. 실수한 점, 개선할 점

• 개산할 때 계산량 줄이면 소요 시간 확 줄어듦.

 

<코드>

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>

using namespace std;

const int MAX_N = 100001;
const int MAX_V = 1000001;

// Sqrt Decomposition
int sqrtN;
struct Query {
    // 쿼리가 저장된 index와 시작점과, 끝점
    int idx, s, e, sq;
    // sort compare
    bool operator < (Query &x) {
        if(sq != x.sq)
            return sq < x.sq;
        return e < x.e;
    }
};

// 수열의 크기 N, 쿼리의 개수 M
int N, M;
// 수열 A[i]
int A[MAX_N];
// 쿼리 배열
vector<Query> query;
// 이미 부분 수열에 포함되어 있는가?
int isIn[MAX_V];
// 서로 다른 수의 개수
int cnt;
// 쿼리 결과
int ans[MAX_N];

void input() {
    cin >> N;
    sqrtN = (int)sqrt(N);
    for(int i=1; i<=N; i++)
        cin >> A[i];
    cin >> M;
    for(int i=0; i<M; i++) {
        //query
        int a, b;
        cin >> a >> b;
        query.push_back({i, a, b, (a-1)/sqrtN});
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    // mo's algorithm
    sort(query.begin(), query.end());
    
    // 처음은 일일이 구해주기
    int s = query[0].s, e = query[0].e;
    for(int i=s; i<=e; i++) {
        if(!isIn[A[i]])
            cnt++;
        isIn[A[i]]++;
        //cout << A[i] << ' ';
    }
    ans[query[0].idx] = cnt;
    
    for(int i=1; i<M; i++) {
        while(s < query[i].s)
            if(!(--isIn[A[s++]]))
                cnt--;
        while(s > query[i].s)
            if(!(isIn[A[--s]]++))
                cnt++;
        while(e < query[i].e)
            if(!(isIn[A[++e]]++))
                cnt++;
        while(e > query[i].e)
            if(!(--isIn[A[e--]]))
                cnt--;
        ans[query[i].idx] = cnt;
    }
    
    for(int i=0; i<M; i++)
        cout << ans[i] << '\n';
    
    return 0;
}

 

 

<Sqrt Decomposition>

https://justicehui.github.io/medium-algorithm/2019/03/03/SqrtDecomposition/

[구간쿼리] Sqrt Decomposition

 

<Mo's Algorithm>

https://justicehui.github.io/hard-algorithm/2019/06/17/MoAlgorithm/

[구간쿼리] Mo's Algorithm(모스 알고리즘)

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.