BOJ 백준 25462 Inverzije
문제 : https://www.acmicpc.net/problem/25462
[ 문제 요약 ]
- 배열이 주어지고 해당 배열의 범위가 주어집니다.
- 배열의 인덱스 i, j가 주어지면, arr[i] > arr[j]( 단, i < j )인 모든 쌍의 개수를 출력합니다.
[ 테스트 케이스 설명 ]
5 5 // 원소 수(1<=100,000), 쿼리 수(1<=100,000)
4 3 5 1 2 // 1부터 N까지 서로다른 자연수가 주어짐
2 3
1 5
4 4
1 4
2 4
답
0
7
0
4
2
[ 알고리즘 분류 ]
- 자료구조
- 오프라인 쿼리
- Mo’s 알고리즘
- 세그먼트 트리, 펜윅 트리
[ 문제 해설 ]
주어지는 원소의 수가 최대 10만 개이고, 쿼리의 수도 10만 개이기 때문에 하나씩 완전 탐색한다면 시간 초과입니다.
한 쿼리를 실행할 때마다, 그 실행 결과를 다음 쿼리에도 활용할 수 있어야 합니다.
방법은 Mo’s 알고리즘으로 정렬하고, 투 포인터로 구간을 최소한으로 이동하며 탐색합니다. 자기보다 큰 수 카운팅은 세그먼트 트리(or 펜윅 트리)로 진행합니다.
먼저, 배열 왼쪽에서 오른쪽으로 탐색 시, 탐색하는 현재 숫자 이전에 나온 큰 수들을 빠르게 셀 수 있는 방법이 있어야 합니다.
이를 위해 세그먼트 트리를 이용합니다. 세그먼트 트리의 인덱스 자체를 해당 원소의 값으로 놓고, 그 안에 저장되는 value를 해당 숫자가 나온 횟수로 두면 됩니다.
그렇게 하면 타겟 숫자가 10일 경우, 세그먼트 트리 쿼리 질의를 query(11, MAX_LEN) 까지로 질의했을 때 자기보다 큰 숫자가 몇 번 나왔는지 바로 알 수 있습니다.
세그먼트 트리는 재귀 오버헤드가 있어 성능상 좋지 않습니다. 단순 구간 합 쿼리와 업데이트만 하면 되기 때문에 저는 펜윅 트리를 사용했습니다.
그리고 Mo’s 알고리즘은 오프라인 쿼리로 처리 시 포인터의 이동을 최소화하기 위해 정렬할 때 사용합니다. 배열의 길이가 N 이라면, 배열의 구간을 sqrt(N)으로 나눠 정렬하는 방법입니다.
구간이 같을 때는 그냥 놔두거나, 성능을 위해 디테일한 정렬을 추가할 수도 있습니다. 저는 성능을 높이기 위해 별도 정렬을 추가했습니다.
쿼리는 [ L, R ] 형식으로 주어지기 때문에, L 또는 R을 기준으로 sqrt(N) 개의 구간으로 나눕니다.
저는 L을 기준으로 sqrt(N) 구간으로 나누었습니다. 만약 L / sqrt(N)의 값이 같다면, 나눈 결과 값이 짝수일 경우는 R 기준 오름차순 정렬, 홀수일 경우 R 기준 내림차순으로 정렬했습니다.
이렇게 R 기준 오름차순, 내림차순 정렬 시 R 포인터의 이동이 한 방향으로만 가게 되어 좀 더 효율적입니다(ex. 1 3 5 7 9 8 6 4 2 )
이렇게 하면 연속한 두 쿼리 사이에서 포인터 L 과 R 이 한 번에 멀리 점프하는 일이 거의 사라져, 전체 이동 횟수가 O((N+Q)√ N)에 그치게 됩니다.
정렬된 쿼리를 순서대로 처리하면, [L, R]에서 몇 칸씩만 포인터를 늘리거나 줄이게 되어 거의 상수 시간으로 배열을 탐색해 최빈도·합계·고유값 등 원하는 통계를 빠르게 구할 수 있습니다.
결국 정렬에 O(Q log Q) , 쿼리 처리에 O((N+Q)√N) 이 걸려 총 시간 복잡도는 O((N+Q)√N)가 됩니다.
메모리는 카운트 배열과 쿼리 리스트를 합해 O(N+Q)입니다.
[ 정답 코드 ]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
class Main{
static int N, Q;
static int[] arr; // 입력을 받을 배열
static long[] ans; // 최종 결과를 담을 배열
static int[] fenwickTree; // 구간합을 구할 펜윅 트리
static ArrayList<Query> query;
public static void main(String[] args)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];
fenwickTree = new int[N + 1];
query = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++)
arr[i] = Integer.parseInt(st.nextToken());// 1부터 N까지 서로 다른 자연수가 주어짐
for(int i=1, sqrt = (int)Math.sqrt(N); 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);
int L = 1;
int R = 0;
long cnt = 0;
for(Query q : query)
{
// 현재 R보다 범위가 크면, 현재 숫자를 펜윅트리에 넣고 현재 숫자보다 큰 숫자들의 개수를 더함
while(R < q.right)
cnt += rightCal(arr[++R], 1);
// 현재 범위보다 R이 크다면, 현재 숫자를 펜윅트리에서 빼고, 현재 숫자보다 큰 숫자들의 개수를 뺀다.
while(q.right < R)
cnt -= rightCal(arr[R--], -1);
// 현재 L보다 범위가 크다면, 현재 숫자를 펜윅트리에서 빼고, 현재 숫자보다 작은 숫자들의 개수를 뺀다.
while(L < q.left)
cnt -= leftCal(arr[L++], -1);
// 현재 범위보다 L이 크다면, 현재 숫자를 펜윅트리에 넣고, 현재 숫자보다 작은 숫자들의 개수를 더함
while(q.left < L)
cnt += leftCal(arr[--L], 1);
ans[q.idx] = cnt;
}
StringBuilder sb = new StringBuilder();
for(int i=1; i<=Q; i++)
sb.append(ans[i]).append('\n');
System.out.print(sb);
}
static int rightCal(int num, int value) {
update(num, value);
return query(num + 1, N);
}
static int leftCal(int num, int value) {
update(num, value);
return query(1, num - 1);
}
static int query(int l, int r) {
return sum(r) - sum(l - 1);
}
static int sum(int idx) {
int ans = 0;
while(idx > 0)
{
ans += fenwickTree[idx];
idx -= idx & -idx;
}
return ans;
}
static void update(int idx, int value) {
while(idx <= N)
{
fenwickTree[idx] += value;
idx += idx & -idx;
}
}
static class Query implements Comparable<Query>{
int left, right, idx, fac;
Query(int l, int r, int i, int f){
left = l;
right= r;
idx = i;
fac = f;
}
@Override
public int compareTo(Query o) {
// 구간이 같지 않을 경우 구간 기준 오름차순 정렬
if(fac != o.fac)
return fac - o.fac;
// 구간이 짝수인 경우 오른쪽 기준 오름차순 정렬
if((fac&1) == 0)
return right - o.right;
// 구간이 홀수인 경우 오른쪽 기준 내림차순 정렬
return o.right - right;
}
}
}