BOJ - 퀘스트 중인 모험가(15816)

문제(링크)

좌표 압축 + 세그먼트 트리를 사용해 오프라인으로 해결하는 문제였습니다.

문제에서 퀘스트의 번호가 -10억 ~ 10억이기 때문에 퀘스트의 번호를 모두 세그먼트 트리에 저장하기엔 무리가 있습니다.
하지만 퀘스트의 총 개수는 100만개이기 때문에 사용된 모든 퀘스트들을 따로 리스트에 담아 압축시키면 됩니다.
즉, 모든 쿼리를 쭉 받아 1번 질의에 해당하는 퀘스트(새롭게 업데이트되는 퀘스트)를 저장합니다.

다음과 같은 퀘스트 번호가 주어진다면

Q1 = -1000000 , Q2 = 1524421 , Q3 = 23 , Q4 = -999999999

리스트에 정렬하여 담으면 다음과 같이 됩니다.

list[0] = -999999999 (Q4) , list[1] = -1000000(Q1) , list[2] = 23(Q3) , list[3] = 1524421(Q2)

즉, list의 인덱스가 새로운 퀘스트 번호가 됩니다.
그리고 퀘스트의 원래 번호가 주어졌을 때 lowerBound or upperBound 를 이용하면 쉽게 인덱스를 찾을 수 있습니다.
ex) lowerBound(1524421) -> 3

다음엔 list를 가지고 세그먼트 트리를 만드는데, 푼 문제는 1, 안 푼 문제는 0으로 하여 구간합을 구하면 해당 구간의 푼 문제의 개수를 구할 수 있습니다.

막혔던 부분 :
1. 처음 쿼리를 받을 때 1,2번 질의에 대한 퀘스트를 모두 받아 시간 초과, 메모리 초과가 났습니다.(2번 질의는 해당 범위의 푼 문제만 카운트하면 되므로 따로 저장할 필요가 없었습니다.)
2. 2번 질의를 해결할 때 Left, Right 모두 lowerBound로 찾아서 틀렸습니다.(RIght는 upperBound - 1로 해야 항상 가장 가까운 값을 찾을 수 있습니다.)

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

public class Main {

    public static int N, Q;
    public static int[] tree;
    public static ArrayList<Integer> quest = new ArrayList<>();
    public static void main(String[] argc) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        Queue<String> query = new LinkedList<>();
        query.offer(br.readLine());
        st = new StringTokenizer(query.peek());

        for (int i = 0; i < N ; i++) {
            int Qu = Integer.parseInt(st.nextToken());
            quest.add(Qu);
        }
        Q = Integer.parseInt(br.readLine());
        for (int i = 0; i < Q ; i++) {
            String que = br.readLine();
            query.offer(que);
            st = new StringTokenizer(que);
            int o = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            if(o == 1){
                    quest.add(x);
            }
        }
        Collections.sort(quest);

        double H = Math.ceil(Math.log(quest.size()) / Math.log(2));
        tree = new int[(int)Math.pow(2, H + 1)];

        st = new StringTokenizer(query.poll());
        for (int i = 0; i < N ; i++) {
            int Qu = Integer.parseInt(st.nextToken());
            update(1, 0, quest.size() - 1, getIdx(Qu));
        }
        while(!query.isEmpty()){
            st = new StringTokenizer(query.poll());
            int o = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            if(o == 1){
                update(1, 0, quest.size() - 1, getIdx(x));
            }
            else{
                int y = Integer.parseInt(st.nextToken());
                int res = y - x + 1;

                bw.write((res - getSum(1, 0, quest.size() - 1, getIdx(x), getIdx_u(y))) + "\n");
            }
        }
        bw.flush();
        bw.close();
    }
    public static int getIdx(int v){
        return lowerBound(0, quest.size(), v);
    }
    public static int getIdx_u(int v){
        return upperBound(0, quest.size(), v) - 1;
    }
    public static int upperBound(int s, int e, int v){
        while(s < e){
            int mid = (s + e) / 2;
            if(quest.get(mid) > v)
                e = mid;
            else
                s = mid + 1;
        }
        return s;
    }
    public static int lowerBound(int s, int e, int v){
        while(s < e){
            int mid = (s + e) / 2;
            if(quest.get(mid) >= v)
                e = mid;
            else
                s = mid + 1;
        }
        return s;
    }
    public static int update(int now, int left, int right, int idx){
        if(idx < left || idx > right)   return tree[now];
        if(left == right)
            return tree[now] = 1;

        return tree[now] = update(now * 2, left, (left + right) / 2, idx) +  update(now * 2 + 1, (left + right) / 2 + 1, right, idx);
    }
    public static int getSum(int now, int left, int right, int start, int end){
        if(left > end || right < start) return 0;
        if(left >= start && right <= end)   return tree[now];

        return getSum(now * 2, left, (left + right) / 2 , start, end) + getSum(now * 2 + 1, (left + right) / 2 + 1, right , start, end);
    }
}