PS 시나브로

문제 : https://www.acmicpc.net/problem/13547

문제 요약 : 주어진 구간에서 서로 다른 개수의 숫자 개수를 출력

JAVA

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

public class Main {

	static class Query implements Comparable<Query> {
		int s, e, index;
		
		Query(int s, int e, int index) {
			this.s = s;
			this.e = e;
			this.index = index;
		}
		
        //이문제의 핵심 쿼리를 평방분할 후 정렬
        //우선순위 (s-1)/sz -> e
		@Override
		public int compareTo(Query o) {
			if ((s - 1) / sz != (o.s - 1) / sz)
				return (s - 1) / sz - (o.s - 1) / sz;
			return e - o.e;
		}
	}
	
	static int n,m,sz;
	static int[] ans, cnt;
	static int sum = 0;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int i;

		n = Integer.parseInt(br.readLine());
		int[] arr = new int[n+1];
		sz = (int)Math.sqrt(n);
		cnt = new int[1000001];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(i=1;i<=n;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		m = Integer.parseInt(br.readLine());
		Query[] q = new Query[m];
		for(i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			q[i] = new Query(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),i);
		}
		Arrays.sort(q);
		
		ans = new int[m];
		int s = 1;
		int e = 0;
        
        //문제의 핵심인 중복되는 구간을 다음 쿼리에도 이용하는 방법
	    for(i=0;i<m;i++) {
	    	while(q[i].s > s) if(--cnt[arr[s++]]==0) sum--;
	    	while(q[i].s < s) if(++cnt[arr[--s]]==1) sum++;
	    	while(e < q[i].e) if(++cnt[arr[++e]]==1) sum++;
	        while(e > q[i].e) if(--cnt[arr[e--]]==0) sum--;
	        ans[q[i].index] = sum;
	    }
	    for (int k : ans) {
	    	sb.append(k+"\n");
	    }
		System.out.println(sb.toString());
		br.close();
	}
}

평방 분할의 경우 낯설지 않게 접근할 수 있었지만 Mo's의 알고리즘은 처음엔 이해하기도 어려웠다.

모스알고리즘을 이용하면 많은 쿼리를 구간 단위로 관리할 때 유용하게 이용 할 수 있을 것 같다.