BOJ 백준 16979 수열과 쿼리 23

 

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

 

[ 문제 요약 ]

• 배열과 그 원소가 주어집니다. 배열 원소는 1≤10억까지 범위입니다.
• 구간 쿼리들이 주어지는데, 구간 안에서 Ai > Aj인 (i, j) 쌍의 개수를 출력합니다.

 

[ 테스트 케이스 설명 ]

5 3			// 배열 수, 쿼리 수 (1<=100,000)
1 4 2 3 1		// 입력되는 숫자 (1<=1,000,000,000)
1 2			// 쿼리 범위
3 5
1 5
답
0
2
5

 

 

[ 알고리즘 분류 ]

• 세그먼트 트리, 펜윅 트리
• 오프라인 쿼리
• 값 / 좌표 압축
• Mo’s 알고리즘

 

[ 문제 해설 ]

 

배열에서 입력된 Ai > Aj인 쌍의 개수를 빠르게 구하는 방법은 세그먼트 트리의 구간합을 이용하는 것입니다.

 

세그먼트 트리 인덱스 자체는 해당 숫자들을 의미하고, 그 안에 저장되는 값은 그 숫자가 나온 횟수(cnt)를 저장합니다.

 

이렇게 하면, 숫자만 알면, 그 이하 or 이상 숫자가 지금까지 몇 번 나왔는지 빠르게 알 수 있습니다.

 

초기 배열의 값을 세그먼트 트리의 인덱스를 값 자체로 바로 만들면 배열의 크기가 엄청 커집니다.

 

배열 원소 범위가 1부터 10억까지이므로 이 값 자체를 세그먼트 트리로 만들 수는 없어서 값 압축을 진행해야 합니다.

 

그리고 쿼리에 update가 없으므로 오프라인 쿼리로 처리하고, 투포인터를 활용해 현재 Ai > Aj의 값을 실시간으로 구해가야 합니다.

 

투포인터를 활용할 때, 포인터의 최소 이동을 하기 위해 Mo’s 알고리즘으로 쿼리들을 정렬합니다.

 

Mo’s 알고리즘은 배열을 sqrt(N) 구간으로 나눠 투 포인터의 이동을 최소화하는 알고리즘입니다.

 

범위의 왼쪽을 L, 오른쪽을 R이라 할 때, L / sqrt(N)으로 먼저 정렬하고, 같으면 R을 기준으로 오름차순 정렬합니다.

 

이렇게 하면 연속한 두 쿼리 사이에서 L 과 R 이 한 번에 멀리 점프하는 일이 거의 사라져, 전체 이동 횟수가 O((N+Q)√ N)에 그치게 됩니다.

 

그리고 조금 더 빠른 연산을 위해 세그먼트 트리보다 펜윅 트리를 사용하는게 성능이 더 좋습니다.

 

아래 코드는 갑 압축 + 오프라인 쿼리 + 펜윅 트리 + 투포인터 + Mo’s 알고리즘을 사용한 풀이 코드입니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;

class Main{
	
	static int len;		// 값 압축을 위한 플레그
	static int sqrt;	// Mo's 알고리즘을 위한 블록
	static int N, Q;
	static int [] arr;
	static int [] fenwickTree;
	static long[] ans;
	static ArrayList<Query> query;
	
	public static void main(String[] args)throws Exception{
		inputAndComp();// 해당 함수에서 값의 입력과 좌표압축, 쿼리를 Mo's 알고리즘으로 정렬
		solve();	// 해당 함수에서 펜윅트리 + 투포인터 알고리즘을 이용해 각 쿼리당 연산 진행
		print();	// 해당 함수에서 결과 출력
	}
	
	static void inputAndComp()throws Exception {
		BufferedReader	br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N		= Integer.parseInt(st.nextToken());// 배열 수(1<=100,000)
		Q		= Integer.parseInt(st.nextToken());// 쿼리 수(1<=100,000)
		arr		= new int[N + 1];
		ans		= new long[Q + 1];
		query	= new ArrayList<>();
		sqrt	= (int)Math.sqrt(N);
		
		TreeSet<Integer> set = new TreeSet<>();
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
		{
			arr[i] = Integer.parseInt(st.nextToken());
			set.add(arr[i]);
		}
		
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int s: set)
			map.put(s, ++len);
		
		for(int i=1; i<=N; i++)
			arr[i] = map.get(arr[i]);
		
		for(int i=1; i<=Q; i++) {
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			query.add(new Query(l, r, i, l / sqrt));
		}
		
		Collections.sort(query);
	}
	static void solve() {
		fenwickTree = new int[len + 1];
		int L = 1;
		int R = 0;
		long cnt = 0;
		for(Query q : query)
		{
			while(R < q.right) {
				++R;
				update(arr[R], 1);
				// 현재 추가된 수 보다 큰 수가 몇개 있는지 카운팅
				cnt += query(arr[R] + 1, len);
			}
			
			while(q.right < R) {
				update(arr[R], -1);
				// 현재 제거된 수 보다 큰 수가 몇개 있는지 카운팅 해서 뺀다
				cnt -= query(arr[R] + 1, len);
				--R;
			}
			
			while(L < q.left) {
				update(arr[L], -1);
				// 현재 제거된 수 보다 작은 수가 몇개 있는지 카운팅 해서 뺀다
				cnt -= query(1, arr[L] - 1);
				++L;
			}
			
			while(q.left < L) {
				--L;
				update(arr[L], 1);
				// 현재 추가된 수 보다 작은 수가 몇개 있는지 카운팅
				cnt += query(1, arr[L] - 1);
			}
			
			ans[q.idx] = cnt; 
		}
	}
	static void print() {
		StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<=Q; i++)
			sb.append(ans[i]).append('\n');
		
		System.out.print(sb);
	}
	static int query(int l, int r) {
		return sum(r) - sum(l - 1);
	}
	static int sum(int i) {
		int sum = 0;
		
		while(i > 0)
		{
			sum += fenwickTree[i];
			i-= i & -i;
		}
		
		return sum;
	}
	static void update(int i, int value) {
		while(i <= len)
		{
			fenwickTree[i] += value;
			i += i & -i;
		}
	}
	static class Query implements Comparable<Query>{
		int left, right, idx, fac;
		Query(int l, int r, int i, int f){
			this.left = l;
			this.right = r;
			this.idx = i;
			this.fac = f;
		}
		@Override
		public int compareTo(Query o) {
			return fac == o.fac ? right - o.right : fac - o.fac;
		}
	}
}