https://www.acmicpc.net/problem/23833
문제요약
- N개의 수가 주어짐(10만, 1~100)
- 두 가지 명령이 주어짐
- A ~ B까지 서로 다른 그룹의 개수 : 2 2 3 3 3 2 2 1 => 4그룹
- A를 B로 바꿈
- 명령의 개수는 10만개
접근법
- A ~ B 서로 다른 숫자를 세는 방법인줄 알았으나 아니었음(만약 그런 것이었으면 모스 알고리즘 또는 세그먼트 트리 100개를 사용하려고 했음)
- 그룹을 연결시키는 방법을 고민해야하는데..
- 숫자가 하나 바뀌면 이런 것은 알겠음
- 그 숫자때문에 그룹이 분리되거나 : 2 2 2 2 2 => 2 2 1 2 2
- 그 숫자때문에 그룹이 연결되거나 : 양쪽이 연결되거나, 한쪽만 연결되거나 : 3 2 1 2 4 => 3 2 2 2 4
- 구간트리를 구현한다면 어떻게 될까?
- 구간에서 서로 다른 그룹의 개수를 갖고 있음
- 병합할때(합을 구하든, 업데이트를 하든, 초기화를 하든) 왼쪽과 오른쪽을 병합할 것임 : 양쪽 값을 합할 것임
- 왼쪽구간(.......오른쪽끝) + 오른쪽(왼쪽끝........) 이런 상황일때 : 양쪽 값을 합해 나갈 것인데
- 오른쪽 끝과 왼쪽 끝을 비교해볼 수 있음
- 서로 다르면 : 그냥 합함
- 서로 같으면 : 합하고 - 1, 같은 것은 하나의 그룹이니까
- 이런 방식으로 합, 업데이트 초기화 진행
주의점
- 합을 구할때 구간이 범위에 포함되는지 체크해야함
- 왼쪽(포함안됨), 오른쪽(포함됨) 일때 병합하면서 양쪽 끝을 비교해주는 부분이 들어가면 흐름이 꼬임. 적절히 처리하면 좋겠지만..
newbieski