문제 링크
- http://icpc.me/11934
문제 출처
- 2014 JOIOC 2번
사용 알고리즘
- 세그먼트 트리
시간복잡도
- $O(N log^2 N)$
풀이
일관성을 잃지 말고, $A_i ≤ B_i$라고 생각합시다. $A_i > B_i$인 경우에는 swap을 해주고 처음에 $B_i$가 보인다고 생각하면 됩니다.
각 연산마다 주어지는 수 $T_j$에 대해서, 각 카드는 아래 3가지의 경우 중 한 가지에 해당합니다.
- $T_j < A_i$ : 카드가 뒤집어지지 않는다. -> 무시해도 상관 없다.
- $A_i ≤ T_j < B_i$ : 현재 $A_i$가 보이는 경우에만 뒤집어진다. -> 큰 숫자를 보이게 한다.
- $B_i ≤ T_j$ : 항상 뒤집어진다. -> 뒤집으면 된다.
2번째 경우에는 앞에서 어떻게 조작을 했는지는 전혀 신경쓰지 않고, 큰 숫자가 보이도록 카드를 세팅합니다. 그러므로 2번째 경우가 나오기 이전의 조작들은 무시해도 됩니다.
결국 우리는 각 카드에 대해 $A_i ≤ T_j < B_i$가 되는 마지막 지점을 찾고, 그 이후로 $B_i ≤ T_j$인 경우가 몇 번 있었는지를 효율적으로 계산하면 됩니다.
$j$번째 조작에서 $T_j$가 주어졌다는 것을 merge sort tree에 저장해놓으면, 위에서 설명한 2가지를 모두 각 카드에 대해 $O(log^2 N)$, 총 $O(N log^2 N)$에 구할 수 있습니다.