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

1. 문제

• 길이가 N인 수열 Ai가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.
• i j: Ai, ..., Aj에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다.

<입력>

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

<출력>

• 각 쿼리마다 정답을 한 줄에 하나씩 출력

2. 재정의

• X

3. 해결방법

• Sqrt Decomposition으로 나누기
• isIn[A[i]]에 A[i]가 부분 수열에 몇 번 들어갔는지를 저장하기
  • ex) isIn[A[i]]++;
• MaxNum[isIn[A[i]]]에 isIn[A[i]]개 만큼 있는 숫자가 몇 개 있는지를 저장하기
• 즉 MaxNum배열에서 0이 아닌 숫자가 들어있는 칸의 max index가 쿼리의 정답이다.

4. 실수한 점, 개선할 점

• 함수를 함수 바깥에서 정의하는 것보다 함수 내에서 auto f [&] ()으로 정의했을 때 더 빠르게 작동한다.

 

<코드>

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

using namespace std;

const int MAX_N = 100001;
const int MAX_V = 100001;
const int MAX_M = 100001;

int sqrtN;
struct Query {
    int idx, s, e, sq;
    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 res[MAX_M];
// 부분 수열안에 들어있는 숫자의 개수
int isIn[MAX_V];
// i개 있는 원소의 개수, 가장 많이 등장한 횟수
int MaxNum[MAX_N], Maxid;

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++) {
        int a, b;
        cin >> a >> b;
        query.push_back({i, a, b, a/sqrtN});
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    // Sqrt Decomposition
    sort(query.begin(), query.end());
    
    // query를 계산할 때 부분배열에 수 추가하기
    auto add = [&] (int i) {
        int num = isIn[A[i]]++;
        MaxNum[num]--;
        MaxNum[num+1]++;
        if(Maxid == num)
            Maxid++;
    };
    // query를 계싼할 때 부분배열에 수 제거하기
    auto erase = [&] (int i) {
        int num = isIn[A[i]]--;
        MaxNum[num]--;
        MaxNum[num-1]++;
        if(Maxid == num && !MaxNum[num])
            Maxid--;
    };
    
    int s = query[0].s, e = query[0].e;
    for(int i=s; i<=e; i++)
        add(i);
    res[query[0].idx] = Maxid;
    
    for(int i=1; i<M; i++) {
        while(s < query[i].s)
            erase(s++);
        while(s > query[i].s)
            add(--s);
        while(e < query[i].e)
            add(++e);
        while(e > query[i].e)
            erase(e--);
        res[query[i].idx] = Maxid;
    }
    
    for(int i=0; i<M; i++)
        cout << res[i] << '\n';
    
    return 0;
}

 

 

<mo's algorithm>

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

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

 

 

 

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