요새 풀이

• 문제(알고스팟): https://algospot.com/judge/problem/read/MORDOR
• 제한시간: 5초

문제에서 주의할 점

• 표지판 수 N(1 <= N <= 100,000)
• 등산로 수 Q(1 <= Q <= 10,000)
• 테스트 케이스 수 C(1 <= C <= 30)
  • 최악의 경우, 30개의 테스트에, 새로 구해야 하는 등산로가 10,000, 표지판이 100,000
  • 새로 구해야 하는 등산로 1개 마다, 표지판 100,000 의 min, max을 구하는 식으로 하면, 100,000 * 10,000 * 1(tc1개) = 100억 100초가 넘음 따라서, 표지판의 범위를 잘라서 min, max을 구하면 타임오버

문제에서 주어진 힌트

• 처음 등산로에 대한 표지판을 순서대로 제공, 즉 처음 등산로로 0 ~ N 까지의 Item을 하나 저장 가능
• 새로운 등산로는 범위이고, 시작, 도착 (범위의 출발, 끝)을 줌, a,b (0<= a <= b <= N)
• 따라서, 전체 범위에서, 부분 범위에 대한 어떤계산을 해야 하는 문제임
  • 이 문제에서는 부분 범위의 min, max의 값을 구하고, 그 차(max - min)를 구하는 문제임

세그먼트 트리 알고리즘을 적용해서, 트리를 구성하고, 원하는 범위에 대한 답을 구하면 된다.

풀이코드

Java로 풀이함

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

class MordorMinMax {
    int min, max;

    public MordorMinMax(int min, int max) {
        super();
        this.min = min;
        this.max = max;
    }
}

public class Main {
    public static int N; // 표지판의 수
    public static int Q; // 새로운 등산로 수
    public static int UNKNOWN_MIN = 20001;
    public static int UNKNOWN_MAX = -1;
    public static int[] nList; // 첫 등산로 표지판 저장, index가 id(n), value는 고도(h)
    public static MordorMinMax[] tree; // 세그먼트 트리 저장, id는 level 순회

    public static int log2(int x) {
        Double result = Math.log(x) / Math.log(2);
        return result.intValue() + 1;
    }

    public static MordorMinMax createTree(int nodeId, int s, int e) {
        if (s == e) {
            tree[nodeId] = new MordorMinMax(nList[s], nList[s]);
            return tree[nodeId];
        } else {
            int mid = (s + e) / 2;
            MordorMinMax leftTree = createTree(nodeId * 2, s, mid);
            MordorMinMax rightTree = createTree(nodeId * 2 + 1, mid + 1, e);

            int min = Math.min(leftTree.min, rightTree.min);
            int max = Math.max(leftTree.max, rightTree.max);

            tree[nodeId] = new MordorMinMax(min, max);
            return tree[nodeId];
        }
    }

    public static MordorMinMax segmentTree(
            int L, int R,
            int nodeId,
            int currentNodeRangeL, int currentNodeRangeR) {
        // [], [0 - 3], []
        // 구하려는 범위가 현재 노드 범위 전체의 왼쪽 범위, 또는 오른쪽 범위로, 완전 벋어나져 있는 경우
        // 현재 노드에서는 구할 수 있는 값이 없음.
        if (R < currentNodeRangeL || L > currentNodeRangeR) {
            return new MordorMinMax(UNKNOWN_MIN, UNKNOWN_MAX);
        }

        // [..., [0 - 3], ...]
        // 현재 노드 범위 전체가, 구하려는 범위 안에 속하면, 현재 노드 범위의 값을 리턴
        if (L <= currentNodeRangeL && R >= currentNodeRangeR) {
            return tree[nodeId];
        }

        // 구하려는 범위 나머지를 구해야 함.
        int mid = (currentNodeRangeL + currentNodeRangeR)/2;
        MordorMinMax minmaxL = segmentTree(L, R, nodeId * 2, currentNodeRangeL, mid);
        MordorMinMax minmaxR = segmentTree(L, R, (nodeId * 2) + 1, mid + 1, currentNodeRangeR);

        int min = Math.min(minmaxL.min, minmaxR.min);
        int max = Math.max(minmaxL.max, minmaxR.max);
        return new MordorMinMax(min, max);
    }

    public static String getLevel(String newQStartEndIndexStr) {
        StringTokenizer st = new StringTokenizer(newQStartEndIndexStr);

        // start, end는 첫 등산로 표지판의 부분 범위
        int newQStart = Integer.parseInt(st.nextToken());  // 문제의 a
        int newQEnd = Integer.parseInt(st.nextToken());  // 문제의 b

        // 새로운 등산로 표지판 시작, 도악이 동일하면, 높이차가 없음, 따라서 답은 바로 0
        if (newQStart == newQEnd) {
            return "0";
        }

        // 값구하기
        MordorMinMax minmax = segmentTree(newQStart, newQEnd, 1, 0, N - 1);

        return (minmax.max - minmax.min) + "";
    }


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int totaltc = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < totaltc; tc++) {
            String inputNQ = br.readLine();
            StringTokenizer st = new StringTokenizer(inputNQ);

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

            // 주어진 첫 등산로 표지판 초기화
            st = new StringTokenizer(br.readLine());
            nList = new int[N];
            for (int n = 0; n < N; n++) {
                nList[n] = Integer.parseInt(st.nextToken());
            }

            // 트리 초기화 및 트리 생성
            Double len = Math.pow(2, log2(N) + 1) - 1;
            tree = new MordorMinMax[len.intValue()];

            // 트리 초기화 및 트리 생성시, 2^a 형태를 구할 필요 없이 항상, 2^a (2의 a승) 형태로 만드는 것도 가능
            // *4를 하면됨
            tree = new MordorMinMax[N * 4];
            createTree(1, 0, N - 1);

            // 새로운 등산로 Q개만큼 답을 구해야함. 답은 난이도==높이차(h)
            for (int q = 0; q < Q; q++) {
                String level = getLevel(br.readLine());
                bw.write(level);
                bw.newLine();
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}