[백준 14897] 서로 다른 수와 쿼리

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

 

총 N개의 정수로 이루어진 배열 A가 주어진다. 이때, 다음 쿼리를 총 Q번 반복 수행하는 프로그램을 작성하시오. 배열은 1번부터 시작한다.

• l r: l번째 수부터 r번째 수 중에서 서로 다른 수의 개수를 세고 출력한다.

N의 제한이 100만, 쿼리의 수가 100만이다. 일반적으로 쿼리 하나당 log N이 드는데 log2(1000000)은 대략 20 N이 100만, 쿼리 중 서로 다른 수의 개수를 카운팅하는데에도 추가 시간이 들어가니 일반적인 방법으로는 시간초과가 난다

 

쿼리의 결과가 다른 쿼리에 영향이 가지 않으니  offline 쿼리를 처리하는 방법인 mo's algorithm + segment tree를 이용하였다.

 

mo's algorithm을 간략하게 소개하자면 여러 쿼리에 들어있는 각 구간 l, r을 정렬하는데

정렬 할 때 각 좌표값을 √N으로 나눠서 정렬한다.(이 부분은 https://tamref.com/97 여기가 설명이 너무 잘 되어있다)

 

정렬 후 첫 쿼리의 s ~ e는 for문으로 naive하게 구한다

그 다음부터는 이전 s, e와 현재 ns, ne 간 대/소관계를 보면서 갯수를 count한다

처음에는 set을 사용해서 해당 수의 존재 여부를 계산했는데 100만 / 100만 데이터에서 시간초과가 계속 발생하였다

 

수의 존재 여부를 log(N)에 구하면 시간초과가 발생하니 log(1)만에 구하는 방법을 찾아야 했고 수의 범위가 10억까지라 경로압축을 이용하고, 수를 count 하는 배열을 이용해, 해당 수가 있으면 +1, 없으면 -1을 해서 수를 센다

counter가 증가 할 때 0이었으면 수가 새로 들어온거니 res에 1을 더하고,  counter가 감소할 때 0이었으면 수가 없어진 거니 res에 1을 빼고 쿼리의 원래 순서의 답에 저장한다.

 

#include "iostream"
#include "algorithm"
#include "vector"
#include "map"
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

using namespace std;
int arr[1000001], ans[1000001], counter[1000001], comp[1000001];
vector<tuple<int, int, int>> query;
vector<int> v;
int N, M, sqrtN;

bool compare(tuple<int, int, int> t1, tuple<int, int, int> t2) {
    int t1s = get<1>(t1) / sqrtN;
    int t2s = get<1>(t2) / sqrtN;
    if(t1s == t2s) {
        int t1e = get<2>(t1);
        int t2e = get<2>(t2);
        return t1e < t2e;
    }
    return t1s < t2s;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    sqrtN = 1500;
    for(int i = 1; i <= N; i++) {
        cin >> arr[i];
        v.push_back(arr[i]);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    // v = 경로압축된 벡터
    for(int i = 1; i<= N; i++) {
        comp[i] = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
    }
    cin >> M;
    for(int i = 1; i <= M; i++) {
        int s, e;
        cin >> s >> e;
        query.emplace_back(i, s, e);
    }
    sort(query.begin(), query.end(), compare);
    int idx = get<0>(query[0]);
    int s = get<1>(query[0]);
    int e = get<2>(query[0]);
    int res = 0;
    for(int i = s; i <= e; i++) {
        if(counter[comp[i]] == 0) {
            counter[comp[i]] = 1;
            res++;
        } else {
            counter[comp[i]]++;
        }
    }
    ans[idx] = res;
    for(int i = 1; i < M; i++) {
        auto &c = query[i];
        int aidx = get<0>(c);
        int ns = get<1>(c);
        int ne = get<2>(c);
        while(s < ns) {
            counter[comp[s]] -= 1;
            if(counter[comp[s]] == 0) {
                res--;
            }
            s += 1;
        }
        while(s > ns) {
            s -= 1;
            if(counter[comp[s]] == 0) {
                res++;
            }
            counter[comp[s]] += 1;
        }
        while(e < ne) {
            e += 1;
            if(counter[comp[e]] == 0) {
                res++;
            }
            counter[comp[e]] += 1;
        }
        while(e > ne) {
            counter[comp[e]] -= 1;
            if(counter[comp[e]] == 0) {
                res--;
            }
            e -= 1;
        }
        ans[aidx] = res;
    }

    for(int i = 1; i <= M; i++) {
        cout << ans[i] << '\n';
    }
}

 

N, Q가 10만 이하 배열의 값이 100만 이하인 동일한 문제는(https://www.acmicpc.net/problem/13547) 위 코드로 경로압축을 하지 않고 해결 할 수 있다