[백준] 5676번 음주 코딩 (java)

문제 설명

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

문제 풀이

• 기본적인 세그먼트 트리 문제이다.
• 곱 연산은 Long 자료형으로 저장하더라도 오버플로우가 날 수 있기 때문에 결과에 필요한 부호만 저장하는 로직을 사용해야 한다.

소스 코드 (JAVA)

import javax.swing.text.Segment;
import java.io.*;
import java.util.*;

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;

    public static int N, K;
    public static int[] arr;

    public static long changeResult(long num) {
        if (num == 0) return 0L;
        else if (num > 0) return 1L;
        else return -1L;
    }

    public static class SegmentTree {
        public long[] tree;

        public SegmentTree(int n) {
            double height = Math.ceil(Math.log(n) / Math.log(2)) + 1;
            long count = Math.round(Math.pow(2, height));
            tree = new long[Math.toIntExact(count)];
        }

        public long init(int node, int s, int e) {
            int mid = (s + e) / 2;
            if (s == e) return tree[node] = changeResult(arr[s]);
            else return tree[node] = changeResult(init(node * 2, s, mid) *
                    init(node * 2 + 1, mid+1, e));
        }

        public long cal(int node, int s, int e, int l, int r) {
            int mid = (s + e) / 2;
            if (e < l || r < s) return 1L;
            else if (l <= s && e <= r) return tree[node];
            else return cal(node * 2, s, mid, l, r) * cal(node*2+1, mid+1, e, l, r);
        }

        public long update(int node, int s, int e, int ind, int value) {
            int mid = (s + e) / 2;
            if (ind < s || e < ind) return tree[node];
            else if (s == ind && e == ind) return changeResult(tree[node] = value);
            else return tree[node] = changeResult(update(node * 2, s, mid, ind, value) *
                        update(node*2+1, mid+1, e, ind, value));
        }
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        while(true) {
            String input = br.readLine();
            if (Objects.isNull(input)) break;
            StringTokenizer st = new StringTokenizer(input);
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            arr = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++)
                arr[i] = Integer.parseInt(st.nextToken());
            SegmentTree segTree = new SegmentTree(N);
            segTree.init(1, 0, N - 1);
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                String op = st.nextToken();
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                if ("C".equals(op)) {
                    segTree.update(1, 0, N - 1, a - 1, b);
                } else {
                    long result = segTree.cal(1, 0, N - 1, a - 1, b - 1);
                    if (result == 0) bw.write("0");
                    else if (result > 0) bw.write("+");
                    else bw.write("-");
                }
            }
            bw.write("\n");
        }
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        input();
    }
}