[백준] 15352 욱제와 그의 팬들

욱제의 팬클럽이 K개 있고 N명의 팬들이 있다

그리고 N명이 어떤 팬클럽에 있는지 주어진다

우리에게는 2가지 행동이 있다

1) 팬 X를 퇴출시키기

2) 팬 X를 골라 양 옆으로 연속적이게 같은 팬클럽 사람들에게 선물을 준다

이 문제는 유니온 파인드로 풀 수 있는데 추가적인게 또 필요하다..!

바로 List를 사용하는 것..! 진짜 list를 stl로 사용하진 않는다

삽입은 없지만 삭제를 해야하는 상황에는 O(1)만에 사용할 수 있게 배열로 만들 수 있다. 처음배웠따

L,R 배열을 잡아주고 L에는 나의 왼쪽, R에는 나의 오른쪽 값을 넣는다

그리고 1번과 N번에서는 각각 L[1] = -1 && R[n] = -1을 넣어준다

-1은 NULL값을 의미한다

그리고 x를 삭제하면 자료구조 시간에 과제 하듯이 L과 R을 이용해 L,R의 값들을 바꾸면 된다!

List를 이용해 퇴출 시킬 때 양 옆에 같은 팬카페인지 확인하면 된다!

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int MAXN = 1e6 + 5;
int k, n, q;
int L[MAXN], R[MAXN], p[MAXN], arr[MAXN],cnt[MAXN];
 
int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}
 
void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    p[y] = x;
    cnt[x] += cnt[y];
}
 
void del(int x) {
    cnt[find(x)]--;
    int l = L[x];
    int r = R[x];
    if (r != -1) L[r] = l;
    if (l != -1) R[l] = r;
    if (arr[l] == arr[r]) merge(l, r);
}
 
int main() {
    scanf(" %d %d", &k, &n);
    for (int i = 1; i <= n; i++) {
        cnt[i] = 1;
        p[i] = i;
        L[i] = i - 1;
        R[i] = i + 1;
    }
    L[1] = -1;
    R[n] = -1;
    for (int i = 1; i <= n; i++) {
        scanf(" %d", &arr[i]);
        if (arr[i] == arr[i - 1]) merge(i, i - 1);
    }
    ll ans = 0;
    scanf(" %d", &q);
    for (int i = 0; i < q; i++) {
        int a, b; scanf(" %d %d", &a, &b);
        if (a == 1) del(b);
        else ans += (ll)cnt[find(b)];
        
    }
    printf("%lld\n", ans);
}