[Java | 세그먼트 트리| 1395번 | 플3] 스위치

☑️ 문제

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

준규네 집에는 총 N개의 스위치가 있고 이를 편하게 1번부터 N번까지 차례대로 번호를 매겼다. 그리고 준규의 취미는 이 스위치들을 켜고 끄는 것이다.

준규가 하는 스위치를 갖고 노는 일은 크게 두 가지이다. 하나는 A번부터 B번 사이의 스위치 상태를 반전시키는 것이고 다른 하나는 C번부터 D번 사이의 스위치 중 켜져 있는 상태의 스위치의 개수를 세는 것이다.

하지만 준규가 싫증을 느껴 우리가 이 귀찮은 일을 떠맡게 되었고 프로그래밍을 통해 일을 처리하도록 결정하였다.

 

입력

첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O가 0이면 Si번 스위치부터 Ti번 스위치까지 스위치 상태를 반전시키는 일이고 1이면 Si번 스위치부터 Ti번 스위치까지 중 켜져 있는 상태의 스위치 개수를 묻는 일이다. 단, 초기에는 모든 스위치의 상태는 꺼져있는 상태로 되어있다.

 

출력

입력에서 켜진 스위치 개수에 대한 답을 한 줄에 하나씩 출력한다.

 

예제 입력1

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

 

예제 출력1

1
2

 

☄️ 정답코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[] tree, lazy;

    static void update(int node, int start, int end, int left, int right) {
        propagate(node, start, end);

        if (left > end || right < start) return;
        if (left <= start && end <= right) {
            lazy[node] ^= 1;
            propagate(node, start, end);
            return;
        }

        int mid = (start + end) / 2;
        update(node * 2, start, mid, left, right);
        update(node * 2 + 1, mid + 1, end, left, right);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    static void propagate(int node, int start, int end) {
        if (lazy[node] == 1) {
            tree[node] = (end - start + 1) - tree[node];
            if (start != end) {
                lazy[node * 2] ^= 1;
                lazy[node * 2 + 1] ^= 1;
            }
            lazy[node] = 0;
        }
    }

    static int query(int node, int start, int end, int left, int right) {
        propagate(node, start, end);

        if (left > end || right < start) return 0;
        if (left <= start && end <= right) return tree[node];

        int mid = (start + end) / 2;
        int lsum = query(node * 2, start, mid, left, right);
        int rsum = query(node * 2 + 1, mid + 1, end, left, right);
        return lsum + rsum;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        tree = new int[4 * N];
        lazy = new int[4 * N];

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;

            if (type == 0) {
                update(1, 0, N - 1, a, b);
            } else {
                sb.append(query(1, 0, N - 1, a, b)).append("\n");
            }
        }

        System.out.print(sb);
    }
}

🪐 풀이

세그먼트 트리 with 느리게 갱신

https://book.acmicpc.net/ds/segment-tree-lazy-propagation

여기를 참고했는데, 느리게 갱신되는 세그먼트 트리가 뭔지 모르 참고!!!!

 

update나 query를 실행하는 방식은 기존의 세그먼트 트리 기본 문제들과 같기 때문에,

propagate함수에 대해서만 설명하겠다!

 

✅ propagate

lazy[node]가 1이라면, 반영해야 할 게 있다는 의미라, 값을 반영해 줍니다. 

static void propagate(int node, int start, int end) {
    if (lazy[node] == 1) {
        tree[node] = (end - start + 1) - tree[node];
        
        // 리프노드가 아니라면
        if (start != end) {
            lazy[node * 2] ^= 1;		// ^는 XOR 연산자 
            lazy[node * 2 + 1] ^= 1;		// 같으면 0, 다르면 1 반환
        }
        
        lazy[node] = 0;
    }
}