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;
}
}
}