민호의 소원 (백준 13028)

안녕하세요. 오늘은 세개 이상을 찾을 거예요.

문제

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

아이디어

전형적인 모스 문제입니다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;

ll N, sqrt_N;
bool cmp(pair <pair <ll, ll>, ll> A, pair <pair <ll, ll>, ll> B)
{
    if (A.first.first / sqrt_N != B.first.first / sqrt_N) return A.first.first < B.first.first;
    return A.first.second < B.first.second;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll M, i, arr[101010] = { 0 }, a, b;
    vector <pair <pair <ll, ll>, ll> > query;
    cin >> N >> M; sqrt_N = sqrt(N);
    for (i = 1; i <= N; i++) cin >> arr[i];
    for (i = 1; i <= M; i++)
    {
        cin >> a >> b;
        query.push_back({ {a,b},i });
    }

    sort(query.begin(), query.end(), cmp);

    ll s = 0, e = 0, num[101010] = { 0 }, Ans[101010] = { 0 }, cnt = 0; num[0]++;
    for (i = 0; i < M; i++)
    {
        a = query[i].first.first; b = query[i].first.second;
        while (s < a)
        {
            if (num[arr[s]] == 3) //3미만이 되면
                cnt--;
            num[arr[s]]--;
            s++;
        }
        while (s > a)
        {
            s--;
            num[arr[s]]++;
            if (num[arr[s]] == 3) //3이상이 되면
                cnt++;
        }
        while (e < b)
        {
            e++;
            num[arr[e]]++;
            if (num[arr[e]] == 3) //3이상이 되면
                cnt++;
        }
        while (e > b)
        {
            if (num[arr[e]] == 3) //3미만이 되면
                cnt--;
            num[arr[e]]--;
            e--;
        }
        Ans[query[i].second] = cnt;
    }

    for (i = 1; i <= M; i++)
        cout << Ans[i] << "\n";
}

감사합니다.