[Codeforces Round #790 (Div. 4)] H2. Maximum Crossings (Hard Version)

 

 

---

https://st-lab.tistory.com/233

자바 [JAVA] - 합병정렬 / 병합정렬 (Merge Sort)

 

※. i < j 일 때 ai >= aj라면 교차되도록 선을 그을 수 있다.

 

※. ai == aj 라도 교차되도록 선을 그을 수 있다.

 

※. 배열을 탐색하며 정렬할 원소가 있다면(ai >= aj) 값을 추가하면서 정렬해준다.

(7 7 5 일 때 7과 5을 정렬한다. 이 때 5보다 큰 수가 2개가 있기 때문에(교차되는 선이 2개) 값에 += 2를 해줘야한다.)

(mid == l이 올 수 있는 마지막 수에서 l == 현재 탐색한 l의 수에서 +1 == (배열이 0부터 시작) 을 해주면 된다.)

(mid == 5, l == 4, r == 6 -> 5 - 4 + 1 = 2(교차되는 선이 2개가 있다.)

 

※. 병합정렬을 할 때 merge에서 복사하는 배열은 전역변수로 해줘야한다.(merge안에 하면 병합을 할 때 마다 배열을 생성해 시간초과가 발생)

 

※. 가장 많은 선이 교차되는 결과는 1 + 2 + 3...(n-1) 까지다. n이 200,000 만 이므로 최대 (200,000 * 100,000 - > 1 + 199999 + 2 + 199998...) 까지 나올 수 있으므로 long을 써준다.

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
	static long cnt = 0;
	static int[] temp;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T -- > 0) {
			int n = Integer.parseInt(br.readLine());
			int[] arr = new int[n];
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			cnt = 0;
			temp = new int[arr.length];
			mergeSort(arr, 0, n-1);
			sb.append(cnt).append('\n');
		}
		System.out.println(sb);
	}
	static void mergeSort(int[] a, int left, int right) {
		if(left == right) {
			return;
		}
		int mid = (left + right) / 2;
		
		mergeSort(a, left, mid);
		mergeSort(a, mid+1, right);
		merge(a, left , mid, right);
	}
	static void merge(int[] a, int left , int mid, int right) {
		int l = left;
		int r = mid+1;
		int idx = left;
		
		while(l <= mid && r <= right) {
			if(a[l] < a[r]) {
				temp[idx] = a[l];
				l++;
			}
			else {
				temp[idx] = a[r];
				cnt += mid-l+1;
				r++;
			}
			idx++;
		}
		
		while(l <= mid) {
			temp[idx] = a[l];
			l++;
			idx++;
		}
		while(r <= right) {
			temp[idx] = a[r];
			r++;
			idx++;
		}
		
		for(int i = left; i <= right; i++) {
			a[i] = temp[i];
		}
	}
}