[JAVA] 백준 - 스위치 1395 (세그먼트트리 + lazy propagation)

www.acmicpc.net/problem/1395

1395번: 스위치

 

세그먼트트리를 풀기위한 기본 템플릿은 onejunu.tistory.com/119

[JAVA] 세그먼트 트리구현법과 lazy propagation (feat. 백준)

위 링크에도 설명했지만 init , update , query , updateLazy가 있다. 

그렇다면 어떻게 세그먼트트리를 이용하여 문제를 풀수 있는지 고민해보자.

 

"세그먼트트리의 노드의값을 무엇으로 정하는가?" 가 핵심이다.

정답부터 이야기하면 노드의 값은 켜져있는 전구의 수로 정하면 된다. 만약 노드의 값을 다르게 정하여 문제를 해매었다면 여기서 페이지를 나간뒤 노드의 값을 켜져있는 전구의수를 바탕으로 스스로 구현해보기 바란다.

 

 

 

init

노드의 값을 켜져있는 전구의 수로 구현해보자. 먼저 init을 따로 구현해야하지만 구현할 필요가 없다.

그냥 tree의 사이즈만 정해주면 된다. 왜냐하면 초기 전구의 상태는 모두 꺼져있는 상태로 노드의 값을 켜져있는 전구의 수로 먼저 정의를 했기 때문에 따로 노드의 값을 init할 필요가 없기 때문이다.

 

 

update

이제 업데이트하는 코드를 작성한다.

역시 파라미터는 (node,st,ed,left,right) 이다. st ~ ed 구간이 left~right 구간에 완벽하게 포함된다면 업데이트를 실행하면 된다.

본인은 update라는 함수의 이름대신에 문제와 맞게 toggle이라는 이름으로 명명하였다. 

 

    public static void toggle(int node,int st,int ed,int left,int right){
        updateLazy(node,st,ed);
        if(st > right || ed < left) return;
        if(left <= st && ed <= right) {
            tree[node] = (ed-st+1) - tree[node]; // toggle

            if( st != ed){
                lazy[node*2] ^= 1; // 전파 2번은 전파0번과 같음!
                lazy[node*2 + 1] ^= 1;
            }
            return;
        }

        toggle(node*2,st,(st+ed)/2,left,right);
        toggle(node*2+1,(st+ed)/2+1,ed,left,right);
        tree[node]  = tree[node*2] +  tree[node*2 + 1];
    }

updateLazy는 lazy값이 있다면 toggle해버리는 함수이며 

tree[node] = (ed -st +1 ) - tree[node] 의 의미는 예로 들어 설명하겠다.  현재 구간이 만약 (0~10) 이라고 가정하자. 여기서 켜져있는 전구의 개수(tree[node])값이 3 이라면 (10 - 0 + 1 ) - 3 = 8 이다. 즉 현재 구간에서 켜져있는 전구는 끄고 켜져있는 전구는 끄는 로직이다.

 

lazy 값에 ^= 연산을 하는 것이 매우 중요한데. 처음에 lazy 를 전파할때 항상 1을 대입했더니 이상하게 출력이 되었다. lazy 값에 ^= 연산을 하는 이유는 2번 토글하면 결국 전파를 안하는 것이므로 XOR연산을 한다.

 

update Lazy

st~ed 구간에 lazy값이 있다면 update를 하는 코드다.

 public static void updateLazy(int node,int st,int ed){
        if(lazy[node]!=0){
            tree[node] = (ed-st+1)-tree[node];

            if(st!= ed){
                lazy[node*2] ^=1;
                lazy[node*2 + 1] ^= 1;
            }
            lazy[node] = 0;
        }
    }

 

 

Query

이름을 sum으로 했으며 세그먼트트리의 템플릿과 다를게 없다.

    public static int sum(int node,int st,int ed,int left,int right){
        updateLazy(node,st,ed);
        if(st > right || ed < left) return 0;
        if(left <= st && ed <= right) return tree[node];

        return sum(node*2,st,(st+ed)/2,left,right)
                + sum(node*2+1,(st+ed)/2+1,ed,left,right);
    }

 

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
    static Fs fs = new Fs();
    static int n,m;
    static int[] tree;
    static int[] lazy;

    public static void updateLazy(int node,int st,int ed){
        if(lazy[node]!=0){
            tree[node] = (ed-st+1)-tree[node];

            if(st!= ed){
                lazy[node*2] ^=1;
                lazy[node*2 + 1] ^= 1;
            }
            lazy[node] = 0;
        }
    }

    public static void toggle(int node,int st,int ed,int left,int right){
        updateLazy(node,st,ed);
        if(st > right || ed < left) return;
        if(left <= st && ed <= right) {
            tree[node] = (ed-st+1) - tree[node];

            if( st != ed){
                lazy[node*2] ^= 1;
                lazy[node*2 + 1] ^= 1;
            }
            return;
        }

        toggle(node*2,st,(st+ed)/2,left,right);
        toggle(node*2+1,(st+ed)/2+1,ed,left,right);
        tree[node]  = tree[node*2] +  tree[node*2 + 1];
    }

    public static int sum(int node,int st,int ed,int left,int right){
        updateLazy(node,st,ed);
        if(st > right || ed < left) return 0;
        if(left <= st && ed <= right) return tree[node];

        return sum(node*2,st,(st+ed)/2,left,right)
                + sum(node*2+1,(st+ed)/2+1,ed,left,right);
    }

    public static void main(String[] args) throws IOException{
        n = fs.nInt(); m = fs.nInt();
        int size = 1;
        while(size < n) size<<=1;
        size<<= 1;

        tree = new int[size];
        lazy = new int[size];

        while(m-- != 0){
            int cond = fs.nInt();
            int t1 = fs.nInt();
            int t2 = fs.nInt();
            if(cond == 0){
                // toggle
                toggle(1,0,n-1,t1-1,t2-1);

            }
            else{
                // sum
                System.out.println(sum(1,0,n-1,t1-1,t2-1));
            }
        }


    }

    static class Fs{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public int nInt() throws IOException {
            if(!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return Integer.parseInt(st.nextToken());
        }
    }
}