Bài 18.6. Dịch Chuyển Thời Gian Và Đếm Cặp Nghịch Đảo - Độ khó: Khó

Trong một nghiên cứu về dịch chuyển thời gian, nhà khoa học phát hiện ra một hiện tượng kỳ lạ: "cặp nghịch đảo thời gian". Đây là các cặp sự kiện mà sự kiện thứ nhất (xảy ra trước về mặt chỉ số) có một "chữ ký thời gian" lớn hơn gấp đôi chữ ký thời gian của sự kiện thứ hai (xảy ra sau về mặt chỉ số). Việc đếm số lượng các cặp này có thể giúp họ hiểu rõ hơn về sự ổn định của dòng thời gian.

Mô tả bài tập: Cho một mảng nums gồm N số nguyên. Một cặp chỉ số (i, j) được gọi là một "cặp nghịch đảo thời gian" nếu i < j và nums[i] > 2 * nums[j]. Nhiệm vụ của bạn là đếm tổng số lượng "cặp nghịch đảo thời gian" trong mảng đã cho.

INPUT FORMAT

Dòng đầu tiên chứa một số nguyên N (1 <= N <= 5 10^4), là số lượng sự kiện (phần tử trong mảng). Dòng thứ hai chứa N số nguyên nums_1, nums_2, ..., nums_N (từ -2 10^9 đến 2 * 10^9), là chữ ký thời gian của các sự kiện.

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng số lượng cặp nghịch đảo thời gian.

Ví dụ:

Input:

5
2 4 3 5 1

Output:

3

Giải thích:

• Các cặp nghịch đảo thời gian là:
  • (2, 1): nums[0] = 2, nums[4] = 1. 2 > 2 * 1 (2 > 2) là không đúng. 2 > 2 * 1 là 2 > 2, cái này là false.
  • Ah, nums[i] > 2 * nums[j]. So 2 > 2 * 1 is false.
  • My example output is wrong or my definition is wrong. Let's recheck the problem definition (LeetCode Reverse Pairs).
  • It's nums[i] > 2 * nums[j].
  • (2, 4, 3, 5, 1)
  • i=0, nums[0]=2:
    • j=1, nums[1]=4: 2 > 2*4 (F)
    • j=2, nums[2]=3: 2 > 2*3 (F)
    • j=3, nums[3]=5: 2 > 2*5 (F)
    • j=4, nums[4]=1: 2 > 2*1 (F)
  • i=1, nums[1]=4:
    • j=2, nums[2]=3: 4 > 2*3 (F)
    • j=3, nums[3]=5: 4 > 2*5 (F)
    • j=4, nums[4]=1: 4 > 2*1 (T) -> (4, 1)
  • i=2, nums[2]=3:
    • j=3, nums[3]=5: 3 > 2*5 (F)
    • j=4, nums[4]=1: 3 > 2*1 (T) -> (3, 1)
  • i=3, nums[3]=5:
    • j=4, nums[4]=1: 5 > 2*1 (T) -> (5, 1)
• Tổng cộng có 3 cặp. My explanation logic for (2,1) was wrong. The example output is correct.

Input:

2
5 3

Output:

1

Giải thích:

• nums[0] = 5, nums[1] = 3.
• i=0, j=1: nums[0] = 5, nums[1] = 3. 5 > 2 * 3 (5 > 6) là false.
• The problem description nums[i] > 2 * nums[j] is standard. My manual check failed again.
• Ah, 5 > 2*3 is 5 > 6, which is false. So for 5 3, the output should be 0.
• Let's correct the example.

Revised Example for 18.6: Input:

5
2 4 3 5 1

Output:

3

Giải thích:

• Các cặp nghịch đảo thời gian là:
  • (nums[1]=4, nums[4]=1): Vì 4 > 2 * 1 (4 > 2) là đúng.
  • (nums[2]=3, nums[4]=1): Vì 3 > 2 * 1 (3 > 2) là đúng.
  • (nums[3]=5, nums[4]=1): Vì 5 > 2 * 1 (5 > 2) là đúng.
• Tổng cộng có 3 cặp.

Input:

2
1 3

Output:

0

Giải thích:

• nums[0] = 1, nums[1] = 3.
• Không có cặp (i, j) nào thỏa mãn i < j và nums[i] > 2 * nums[j] (1 > 2 * 3 là sai).