mo`s. [13548]

[1. 문제 설명]

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

---

[2. 풀이 접근]

동일한 숫자의 발생 횟수를 저장할 배열이 필요함. (occurs)

• index: 수열의 원소
• value: 현재 구간에서 해당 원소의 발생 횟수

발생 횟수에 대해서 해당 횟수만큼 존재하는 숫자의 개수. 

- 3이라는 원소가 4번 발생하고, 5라는 원소가 4번 발생한 경우

- 4번 발생한 원소의 개수는 2개가 된다.

• index: 횟수
• value: 횟수만큼 존재하는 숫자의 개수.

즉, 쿼리에 대해서 각 포인터가 (Left, Right) 넓혀지는 방향으로 움직이는 경우.

• 구하고자 하는 최대 값이 갱신 되는지 확인 하도록 한다.

반대로, 각 포인터가 좁혀지는 방향으로 움직이는 경우.

• 현재 포인터가 가리키는 원소 a 의 발생 횟수가 1 줄어들게 된다.
• 이 원소 a 의 발생 횟수가 기존 최대 값인 경우, 그리고 기존 최대값의 발생 횟수가 더 이상 존재하지 않게 되는 경우
• 단순히 최대 값에서 1 빼는 것이 그 다음 최대 값이 된다.
• 왜냐하면, 3이라는 원소가 현재까지 4번 발생해서 최대 값이 되었다고 하자.
• 즉, 다른 원소는 최대 4개까지 공통으로 존재하지 않는 상황인 것이다.
• 3이라는 원소가 하나 줄어들면 3번 발생하게 되고, 이것이 다음 최대 값이 되는 것은 자명하다.

---

[쿼리의 정렬 방식]

mo`s 알고리즘 적용 시 쿼리의 정렬 방식에 따라 성능에 유의미한 차이가 발생 할 수 있다.

• 보통, 제일 좋은 성능을 보이는 것이 지그재그 방식으로 정렬하는 것인데,,
• 쿼리를 가급적 한 방향으로 움직이게 만들고, 이는 cpu 캐시의 hit 를 증가하게 한다.
• 이 문제에서 동일한 코드를 대상으로 정렬 방식만 다르게 하였는데,
• 172ms -> 148ms -> 116ms 순으로 처리 속도가 개선되었음.
•  

    // case 1
    std::sort(indices.begin(), indices.end(), [&](const int l, const int r){
        const int a = queries[l].first / sqrtn;
        const int b = queries[r].first / sqrtn;
        if (a != b) {
            // 같은 블록이 아닌 경우, 단순히 left 값을 기준으로 정렬한다.
            return queries[l].first < queries[r].first;
        }
        return queries[l].second < queries[r].second;
    });

    // case 2
    std::sort(indices.begin(), indices.end(), [&](const int l, const int r){
        const int a = queries[l].first / sqrtn;
        const int b = queries[r].first / sqrtn;
        if (a != b) {
            // 같은 블록이 아닌 경우, 블록 단위로 정렬한다.
            return queries[l].first < queries[r].first;
        }
        return queries[l].second < queries[r].second;
    });

    // case 3
    std::sort(indices.begin(), indices.end(), [&](const int l, const int r){
        const int a = queries[l].first / sqrtn;
        const int b = queries[r].first / sqrtn;
        if (a != b) {
            // 같은 블록이 아닌 경우, 블록 단위로 정렬하고,
            return a < b;
        }

        // 홀수번째 블록인 경우, 내림차순으로
        // 짝수번째 블록인 경우, 오름차순으로 정렬한다.
        return (a & 1) ? 
            queries[l].second > queries[r].second :
            queries[l].second < queries[r].second;
    });

---

[3. 코드]