[붕어빵 꼬리먼저 팀] 2회차 - 학습 마무리

2021/01/09 동계 모각코 2회차

오늘 공부하고자 했던 오프라인 쿼리에 대한 이해와 문제 풀이를 완료하였습니다.

확실히 하나의 주제만 잡고 공부하니 시간적으로도 여유롭고 더 깊이 생각하면서 문제를 풀이할 수 있었습니다.

 

오프라인 쿼리는 개념 자체는 간단했으나 문제가 풀이하기 오래 걸리는 편이라 다른 공부를 할 시간이 부족했습니다.

앞으로도 어렵고 오래 걸리는 문제에 관한 유형이나, 생소한 개념인 파트를 공부한다면 하나의 주제로만 공부하는 방법으로 방향을 잡았습니다.

 

---

[오프라인 쿼리] www.acmicpc.net/problem/16978

오프라인 쿼리를 사용하는 구간 합 세그먼트 트리 문제입니다.

 

오프라인 쿼리 문제는 쿼리를 처리하는 문제에서 특정한 쿼리까지 진행됐을 때 결과값이 어떻게 될지에 관한 유형입니다.

기존까지의 쿼리 문제들은 쿼리에 대한 정보를 입력받고 그 즉시 쿼리를 처리하였으나, 이 문제에서는 특정 쿼리까지만 진행됐다고 가정했을 때의 결과값을 출력해야 합니다.

 

그러므로 우선 1번과 2번 쿼리에 대한 입력값들을 서로 다른 두 리스트에 전부 저장합니다.

이 때, 출력해야 하는 2번 쿼리에 대한 저장은 입력이 들어온 순서까지 따로 저장합니다.

우리가 원하는대로 쿼리의 순서를 바꿔서 값을 얻어낼 생각이지만 문제에서 제시한 순서가 정해져 있기 때문입니다.

 

입력을 마친다면 2번 쿼리에 대한 리스트를 k에 대해서 오름차순 정렬합니다.

그리고 2번 쿼리를 진행하면서 k에 맞춰 1번 쿼리를 진행해주고 결과값을 저장합니다.

이때, 값은 배열에 저장하고 미리 저장해 놨던 입력이 들어온 순서를 배열의 인덱스로 두고 저장합니다.

그렇게 저장한다면 배열을 한 번에 순회하면서 출력이 용이해지기 때문입니다.

 

 

[소스 코드] / Java

 

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

public class Main {
    private static ArrayList<Sub> subq;
    private static ArrayList<Query> query;
    private static int[] arr;
    private static long[] tree;

	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N + 1]; tree = new long[4 * N];
        subq = new ArrayList<>(); query = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i < N + 1; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        init(1, N, 1);

        int M = Integer.parseInt(br.readLine());
        int qsize = 0;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            char c = st.nextToken().charAt(0);
            if (c == '1') {
                int i = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());
                subq.add(new Sub(i, v));
            } else {
                int k = Integer.parseInt(st.nextToken()), u = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());
                query.add(new Query(qsize++, k, u, v));
            }
        }

        Collections.sort(query);

        long[] dist = new long[qsize];

        int j = 0;
        for (int i = 0; i < qsize; i++) {
            Query cur = query.get(i);
            int o = cur.o, k = cur.k, u = cur.u, v = cur.v;
            
            for (; j < k; j++) {
                Sub temp = subq.get(j);
                int idx = temp.i, val = temp.v;
                update(1, N, 1, idx, val);
            }

            dist[o] = getSum(1, N, 1, u, v);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < qsize; i++) {
            sb.append(dist[i]).append('\n');
        }

        System.out.println(sb.toString());
        br.close();
    }

    private static long update(int left, int right, int node, int i, int v) {
        if (left <= i && i <= right) {
            if (left == right) return tree[node] = v;
            int mid = (left + right) / 2;
            tree[node] = update(left, mid, node * 2, i, v) + update(mid + 1, right, node * 2 + 1, i, v);
        }
        return tree[node];
    }

    private static long getSum(int left, int right, int node, int u, int v) {
        if (left > v || right < u) return 0;
        else if (u <= left && right <= v) return tree[node];
        int mid = (left + right) / 2;
        return getSum(left, mid, node * 2, u, v) + getSum(mid + 1, right, node * 2 + 1, u, v);
    }

    private static long init(int left, int right, int node) {
        if (left == right) return tree[node] = arr[left];
        int mid = (left + right) / 2;
        return tree[node] = init(left, mid, node * 2) + init(mid + 1, right, node * 2 + 1);
    }

    private static class Sub {
        int i, v;

        public Sub(int i, int v) {
            this.i = i;
            this.v = v;
        }
    }

    private static class Query implements Comparable<Query> {
        int o, k, u, v;

        public Query(int o, int k, int u, int v) {
            this.o = o;
            this.k = k;
            this.u = u;
            this.v = v;
        }

        @Override
        public int compareTo(Query q) {
            if (this.k == q.k) return 0;
            return this.k < q.k ? -1 : 1;
        }
    }
}