백준 : 1395 (JAVA)

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

1395번: 스위치

늦은 전파 세그먼트트리 문제.

세그먼트트리를 구현하고 새로운값 갱신시에는 늦은전파를 활용한다.

문제에서 스위치 이기때문에 laze[n]  홀수면은 end-start+1 이 그구간의 최대 전구이므로 현재 tree[n]에서 빼준다. 짝수이면 두번누르는것이므로 아무일도 하지않고 종료한다.

package D0227;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B1395 {
    static int Tree[];
    static int laze[];
    static int N, M;
 
    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[N * 4];
        laze = new int[N * 4];
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int o = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
 
            if (o == 0) {
                // 반전
                update(1, N, s, t, 1);
            } else {
                // sum
                System.out.println(sum(1, N, s, t, 1));
            }
        }
    }
 
    public static int sum(int start, int end, int s, int t, int n) {
        lazeUpdate(start, end, n);
        if (t < start || end < s) {
            return 0;
        }
 
        if (s <= start && end <= t) {
            return Tree[n];
        }
 
        int mid = (start + end) / 2;
 
        return sum(start, mid, s, t, n * 2) + sum(mid + 1, end, s, t, n * 2 + 1);
 
    }
 
    public static void update(int start, int end, int s, int t, int n) {
        lazeUpdate(start, end, n);
        if (t < start || end < s)
            return;
 
        if (s <= start && end <= t) {
            // update
            laze[n] += 1;
            lazeUpdate(start, end, n);
            return;
        }
 
        int mid = (start + end) / 2;
        update(start, mid, s, t, n * 2);
        update(mid + 1, end, s, t, n * 2 + 1);
        Tree[n] = Tree[n * 2] + Tree[n * 2 + 1];
 
    }
 
    public static void lazeUpdate(int start, int end, int n) {
        if (laze[n] == 0)
            return;
        if (laze[n] % 2 == 1) {
            Tree[n] = (end-start + 1) - Tree[n];
        }
 
        if (start != end) {
            laze[n * 2] += laze[n];
            laze[n * 2 + 1] += laze[n];
        }
        laze[n] = 0;
 
    }
}