백준 13028 - 민호의 소원 (C++)

문제

• 문제 링크

  
   BOJ 13028 - 민호의 소원 
  

• 문제 요약

길이 $N$의 수열과 $Q$개의 쿼리가 주어진다.
각 쿼리로 주어지는 $[x, y]$에 대해, 세 번 이상 등장하는 수의 개수를 구해보자.

• 제한

TL : $2$ sec, ML : $512$ MB




$1 ≤ N, Q ≤ 100,000$

$1 ≤ A_i ≤ 100,000$

알고리즘 분류

• mo's(mo's algorithm)
• 오프라인 쿼리(offline_queries)

풀이

$mo's$로 해결할 수 있는 문제들 중 가장 기본적인 형태의 문제이다.

임의의 시점에서 관리하는 구간의 양 끝 $s, e$가 변화하면서 새로운 수가 추가될 때 / 기존의 수가 제거될 때로 구분해보자.

우리가 구해야 하는 건 세 번 이상 등장하는 수의 개수이고, $1 ≤ A_i ≤ 100,000$ 이다.
이에 따라 구간이 관리하는 각 수들의 개수를 기록할 배열을 추가로 정의해 이용할 수 있다.

수 $x$가 추가될 때 : $x$가 추가됨으로써 $cnt[x] == 3$ 가 된다면 조건을 만족하는 수의 종류가 하나 증가한다.

수 $x$가 제거될 때 : $x$가 제거됨으로써 $cnt[x] == 2$ 가 된다면 조건을 만족하는 수의 종류가 하나 감소한다.

이를 유의하여 각 쿼리의 답을 채워주면 되겠다.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
struct _Q { int x, y, i; } Q[N];
int n, q, a[N], cnt[N], ans[N];
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i(1); i <= n; cin >> a[i++]);
    for (int i{}; i < q; i++)
        cin >> Q[i].x >> Q[i].y, Q[i].i = i;
 
    sort(Q, Q + q, [](_Q i, _Q j)
        {
            i.x /= 300, j.x /= 300;
            return i.x ^ j.x ? i.x < j.x : i.y < j.y;
        });
}
void Solve()
{
    int s(Q[0].x), e(s - 1), t{};
    for (int i{}; i < q; i++)
    {
        while (s > Q[i].x) t += ++cnt[a[--s]] == 3;
        while (s < Q[i].x) t -= --cnt[a[s++]] == 2;
        while (e > Q[i].y) t -= --cnt[a[e--]] == 2;
        while (e < Q[i].y) t += ++cnt[a[++e]] == 3;
        ans[Q[i].i] = t;
    }
    for (int i{}; i < q; cout << ans[i++] << '\n');
}
int main()
{
    Init();
    Solve();
}

comment

끝