[Baekjoon - 14897] 서로 다른 수와 쿼리 1

난이도: Platinum II

 

태그

• Offline Query
• Sweeping
• Segment Tree
• Value Compression

 

풀이

1. \( l \)이 고정되어있다면, 쿼리를 어떻게 처리할까?

\( l \)번째 항부터 오른쪽으로 한 칸씩 가면서, 새로운 수가 나온다면 1을, 아니면 0을 적어봅시다.

그럼, \( [l, r] \) 쿼리의 답은 \( [l, r] \) 구간에 적힌 1의 개수 = \( [l, r] \) 구간의 합 이 됩니다.

 

만약 모든 쿼리의 \( l \)이 동일하다면, 위 과정을 전처리한 뒤 \( O(\log N) \)으로 구간합을 처리해주면 되겠죠.

 

2. 왼쪽 끝점이 \( l \)에서 \( l+1 \)로 이동한다면, 쿼리를 어떻게 처리할까?

\( l \)에서 \( l+1 \)로 이동한다면, \( A_l \)의 첫 등장 위치가 바뀌지만, 그 외에는 바뀌는 것이 없습니다.

그러니, \( A_l \)의 새로운 첫 등장 위치를 찾아서 그 부분만 1로 바꾸면 새로운 \( l \) 값에 대해서도 빠르게 풀 수 있겠죠.

 

다르게 말하자면, \( l \)에서 했던 전처리의 대부분을 그대로 가져와서 \( l+1 \)에 적용시킬 수 있다는 것을 의미합니다.

 

3. 그럼, 어떻게 하면 될까?

쿼리를 \( l \)의 오름차순이 되도록 정렬해봅시다.

 

그 뒤로, \( l = 1 \)부터 시작해서 [1] (\( l \)에 대해 쿼리 처리)과 [2] (\( l \)을 \( l+1 \)로 변경)를 번갈아가면서 해주면

모든 쿼리를 처리할 수 있게 됩니다.

 

구현할 때는 \( A_i \)에 대해 값 압축을 하는 게 좋습니다.

 

4. 코드

map<int, int> cvt; set<int> cs;
int arr[1000020];
pi3 qrr[1000020]; int ans[1000020];
 
vector<int> pos[1000020]; int ptr[1000020];
 
const int N = 1048576;
int fen[1048580];
void upd(int pos, int val){
    for (int i = pos; i < N; i+=i&-i){ fen[i] += val; }
}
int qry(int pos){
    int res = 0;
    for (int i = pos; i > 0; i-=i&-i){ res += fen[i]; }
    return res;
}
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){ cin >> arr[i]; cs.insert(arr[i]); }
    int m = 0; for (int x : cs){ cvt[x] = ++m; }
    for (int i = 1; i <= n; i++){
        arr[i] = cvt[ arr[i] ];
        pos[ arr[i] ].push_back(i);
    }
    int q; cin >> q;
    for (int i = 1; i <= q; i++){ cin >> qrr[i].fr.fr >> qrr[i].fr.sc; qrr[i].sc = i; }
    sort(qrr+1, qrr+q+1);
    int p1 = 1;
    for (int l = 1; l <= n; l++){
        int p2 = p1; while (p2 <= q){
            if (qrr[p2].fr.fr == l){ p2 += 1; } else{ break; }
        }
        if (l == 1){
            for (int i = 1; i <= m; i++){ upd(pos[i][0], +1); }
        }
        else{
            int x = arr[l-1];
            upd(pos[x][ ptr[x] ], -1); ptr[x] += 1;
            if (pos[x].size() > ptr[x]){ upd(pos[x][ ptr[x] ], +1); }
        }
        for (int p = p1; p < p2; p++){
            int st = qrr[p].fr.fr, ed = qrr[p].fr.sc;
            int idx = qrr[p].sc;
            ans[idx] = qry(ed);
        }
        p1 = p2;
    }
    for (int i = 1; i <= q; i++){ cout << ans[i] << endl; }
}