[자바] 백준 8462 - 배열의 힘 (boj java)

문제 : boj8462

 

  가장 간단한 방법으로, 각 쿼리마다 직접 해당 범위를 순회하면서 가장 많은 등장 수를 찾는 것은 당연히 간단하다. 하지만 그러면 O(TN)이 될 것이므로 시간초과가 나게 된다.

 

  그러니 이번엔 이전 쿼리의 결과를 이용할 방법을 생각해보자. 첫 번째 쿼리가 i=3, j=10이고 두 번째 쿼리가 i=5, j=11 이라고 해보자. 그림으로 나타내면 아래와 같다.

  이 경우 만약 위에서 말한 방법대로 매번 직접 순회하며 볼 경우 첫 번째 쿼리는 8번, 두 번재 쿼리는 7번을 봐야하므로 총 15번을 봐야한다. 하지만 첫 번째 쿼리에서 i가 +2가 됬으므로 주황색으로 빗금친 부분을 빼면 2번을 빼면 되고, 마찬가지 방식으로 파란 빗금부븐을 1번 더해줄 수 있다. 그럼 총 15번 필요했던게 3번으로 줄어든다!

 

  다만 이 때 쿼리가 여러개 이므로, 쿼리가 입력으로 들어온 순서를 따로 기억해둔다면 쿼리의 순서를 바꿔서 더 효율적으로 연산되게 할 수 있다. 이 때 쿼리의 순서를 임의로 변경하기 보다는, 최대한 효율적인 방식으로 이전의 결과를 사용하도록 변경하기 위한 알고리즘이 mo's algorithm이다. 이 글 등을 참고해보자. 대략의 방식은 n개의 원소가 있는 경우, [i, j] 범위를 i/sqrt(n) ASC, j ASC 순서로 정렬하는 것이다.

 

----

 

  이 문제의 경우 cnt라는 배열을 생각해보자. 위에서 얘기한 것 처럼 각 쿼리의 범위를 추가하고 제거하면서 cnt[i]는 임의의 i번째 자연수들에 대해(1<=i<=n) 현재 보고 있는 범위내에 존재하는 i의 개수를 의미한다. 그리고 answer이 현재 쿼리의 답이라고 해보자. 그럼 s라는 자연수가 추가될 경우 answer에서 Ks*Ks*s를 빼주고, (Ks+1)*(Ks+1)*s 을 더해주면 될 것이다. 마찬가지로 s가 제외될 경우 Ks*Ks*s를 answer에서 빼주고, (Ks-1)*(Ks-1)*s를 더해주면 될 것이다. 이하 코드의 push, pop이 해당 역할을 한다. 그리고 매번 answer을 출력해주면 된다. answer을 구하는 과정이 매우 간단해서, mo's 알고리즘 기본형태 연습용으로 딱 좋아보이는 수준의 문제이다.

 

코드 : github

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

class Query implements Comparable<Query> {
    int a, b, idx, compFactor;
    static int sqrtN;
    public static void setSqrtN(int n) { sqrtN = (int)Math.sqrt(n); }
    public Query(int a, int b, int idx) {
        this.a = a;
        this.b = b;
        this.idx = idx;
        this.compFactor = this.a/sqrtN;
    }
    @Override
    public int compareTo(Query o) {
        if (this.compFactor == o.compFactor)
            return this.b-o.b;
        return this.compFactor-o.compFactor;
    }
}
public class Main {
    int[] cnt = new int[1000001];
    long answer = 0;
    private void push(int num) {
        answer-=1l*num*cnt[num]*cnt[num];
        answer+=1l*num*++cnt[num]*cnt[num];
    }
    private void pop(int num) {
        answer-=1l*num*cnt[num]*cnt[num];
        answer+=1l*num*--cnt[num]*cnt[num];
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 2<<17);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        Query.setSqrtN(n);
        int[] arr = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(st.nextToken());
        Query[] queries = new Query[t];
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            queries[i] = new Query(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), i);
        }
        Arrays.sort(queries);
        for (int i = queries[0].a; i <= queries[0].b; i++) push(arr[i]);
        long[] ansArr = new long[t];
        ansArr[queries[0].idx] = answer;
        int a = queries[0].a;
        int b = queries[0].b;
        for (int i = 1; i < t; i++) {
            Query q = queries[i];
            for (int x = q.a; x < a; x++) push(arr[x]);
            for (int x = b+1; x <= q.b; x++) push(arr[x]);
            for (int x = a; x < q.a; x++) pop(arr[x]);
            for (int x = q.b+1; x <= b; x++) pop(arr[x]);
            a = q.a;
            b = q.b;
            ansArr[q.idx] = answer;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++) sb.append(ansArr[i]).append('\n');
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}