22.3 นับคู่สลับด้วย merge sort

หน้า 13.3 เห็นแล้วว่าจำนวนครั้งที่ bubble sort สลับ เท่ากับจำนวน คู่ที่ผิดลำดับ คือคู่ i < j ที่ a_i > a_j คู่แบบนี้เรียกว่า inversion (คู่สลับ) โจทย์ค่าย 2 และ TOI ใช้มันบ่อยในหลายเรื่องราว เช่น ต้องสลับคนที่ยืนติดกันกี่ครั้งแถวจึงจะเรียง หรือกรรมการสองคนจัดอันดับผู้เข้าแข่งขันขัดกันกี่คู่ หน้า 18.2 นับด้วยลูปซ้อนซึ่งเป็น O(N²) แต่โจทย์มักให้ N ถึงสองแสน หน้านี้นับคู่สลับไปพร้อมกับ merge sort ได้ใน O(N log N) โดยเพิ่มโค้ดแค่บรรทัดเดียว

คู่สลับคืออะไร

นักเรียน 8 คนยืนเข้าแถว ส่วนสูงจากหัวแถวคือ 152 148 160 145 155 150 163 147 ถ้าให้สลับได้เฉพาะคนที่ยืนติดกัน ต้องสลับกี่ครั้งแถวจึงเรียงจากเตี้ยไปสูง การสลับคนติดกันหนึ่งครั้งแก้คู่ที่ผิดลำดับได้หนึ่งคู่พอดี และไม่ทำให้คู่อื่นเปลี่ยน คำตอบจึงเท่ากับจำนวนคู่สลับ ไล่ดูคนแรก 152 สูงกว่าคนที่ยืนหลังเขาอยู่สี่คน คือ 148 145 150 147 นับแบบนี้ครบทุกคนได้

รวมได้ 14 คู่ วิธีนี้คือลูปซ้อนในหน้า 18.2 ที่เทียบทุกคู่ ต่อไปจะใช้ merge sort ให้ได้ 14 เท่ากัน โดยไม่ต้องเทียบทุกคู่

แบ่งคู่เป็นสามแบบ

แบ่งแถวเป็นครึ่งซ้าย 152 148 160 145 กับครึ่งขวา 155 150 163 147 คู่สลับทุกคู่ตกอยู่ในแบบใดแบบหนึ่งพอดี

1. อยู่ในครึ่งซ้ายทั้งคู่ นับด้วยการเรียกตัวเองกับครึ่งซ้าย
2. อยู่ในครึ่งขวาทั้งคู่ นับด้วยการเรียกตัวเองกับครึ่งขวา
3. ข้ามครึ่ง ตัวหน้าอยู่ครึ่งซ้าย ตัวหลังอยู่ครึ่งขวา ต้องนับในขั้นรวม

สังเกตจุดสำคัญ คู่ข้ามครึ่งขึ้นกับแค่ว่าใครอยู่ครึ่งไหน ไม่ขึ้นกับลำดับภายในครึ่ง จะสลับคนในครึ่งซ้ายกันเองยังไง คนในครึ่งซ้ายก็ยังยืนหน้าทุกคนในครึ่งขวาอยู่ดี จำนวนคู่ข้ามครึ่งจึงไม่เปลี่ยน แปลว่าให้ merge sort เรียงสองครึ่งไปก่อนได้ แล้วค่อยนับตอนรวม หลังเรียงแล้วครึ่งซ้ายคือ 145 148 152 160 ครึ่งขวาคือ 147 150 155 163

ระหว่างรวม ทุกครั้งที่หยิบจากครึ่งขวา ตัวที่ยังเหลือในครึ่งซ้ายทั้งหมดมากกว่าตัวนั้น (ไม่อย่างนั้นต้องถูกหยิบไปก่อนแล้ว) และทั้งหมดเคยยืนหน้าตัวนั้น จึงเป็นคู่สลับข้ามครึ่งทุกตัว จำนวนที่เหลือในครึ่งซ้ายคือ mid - i

คู่ข้ามครึ่งในชั้นบนสุดมี 3 + 2 + 1 = 6 คู่ เช่น ตอนหยิบ 147 มีสามคนที่สูงกว่าและยืนหน้าเขา คือ 148 152 160 ตรงกับตารางแรกที่ 147 อยู่ท้ายแถวและมีคนเตี้ยกว่าอยู่ข้างหลังเป็นศูนย์ ส่วนอีก 8 คู่อยู่ภายในแต่ละครึ่ง ซึ่งการเรียกตัวเองนับให้แล้ว

เพิ่มบรรทัดเดียวใน merge sort

#include <bits/stdc++.h>
using namespace std;

long long count_inversions(vector<int> &a, vector<int> &temp, int lo, int hi)
{
    if (hi - lo <= 1) {
        return 0;
    }
    int mid = (lo + hi) / 2;
    long long count = count_inversions(a, temp, lo, mid) + count_inversions(a, temp, mid, hi); // (1)!
    long long cross = 0;
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (a[i] <= a[j]) { // (2)!
            temp[k] = a[i];
            i++;
        } else {
            temp[k] = a[j];
            j++;
            cross += mid - i; // (3)!
        }
        k++;
    }
    while (i < mid) {
        temp[k] = a[i];
        i++;
        k++;
    }
    while (j < hi) {
        temp[k] = a[j];
        j++;
        k++;
    }
    for (int t = lo; t < hi; t++) {
        a[t] = temp[t];
    }
    cout << "[" << lo << ", " << mid << ") + [" << mid << ", " << hi << ") cross = " << cross << '\n';
    return count + cross;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> height(n);
    for (int i = 0; i < n; i++) {
        cin >> height[i];
    }
    vector<int> temp(n);
    long long swaps = count_inversions(height, temp, 0, n);
    cout << "swaps = " << swaps << '\n';
    return 0;
}

1. คู่สลับแบบที่ 1 กับแบบที่ 2 ได้จากการเรียกตัวเอง หลังสองบรรทัดนี้ทั้งสองครึ่งเรียงแล้ว
2. สูงเท่ากันต้องหยิบจากซ้ายก่อน คนสูงเท่ากันไม่ใช่คู่สลับ ดูส่วนลองทำให้พัง
3. บรรทัดเดียวที่เพิ่มจาก merge sort ในหน้า 22.2 ส่วนที่เหลือเหมือนเดิมทุกบรรทัด

8
152 148 160 145 155 150 163 147

[0, 1) + [1, 2) cross = 1
[2, 3) + [3, 4) cross = 1
[0, 2) + [2, 4) cross = 2
[4, 5) + [5, 6) cross = 1
[6, 7) + [7, 8) cross = 1
[4, 6) + [6, 8) cross = 2
[0, 4) + [4, 8) cross = 6
swaps = 14

ได้ 14 ตรงกับที่นับด้วยมือ บรรทัดสุดท้ายก่อนคำตอบคือหกคู่ที่ไล่ในตาราง ตอนเทส่วนที่เหลือไม่ต้องนับอะไร ฝั่งขวาที่เหลือไม่มีใครในฝั่งซ้ายเหลือให้จับคู่แล้ว ส่วนฝั่งซ้ายที่เหลือ คู่ของมันกับฝั่งขวาถูกนับไปแล้วตอนที่ฝั่งขวาแต่ละตัวถูกหยิบ

เวลาเท่ากับ merge sort คือ O(N log N) เพราะบรรทัดที่เพิ่มทำงานคงที่ทุกครั้งที่หยิบ คำตอบมีได้ถึง N(N - 1)/2 ซึ่งที่ N เป็นแสนคือราว 5 × 10⁹ เกิน int ตัวนับและค่าที่ฟังก์ชันคืนจึงต้องเป็น long long

เร็วขึ้นแค่ไหน

ข้อมูลสุ่มจาก mt19937 แบบหน้า 22.2 นับด้วยลูปซ้อนแบบหน้า 18.2 กับ merge sort จับเวลาเฉพาะช่วงนับ วัดแบบเดียวกับหน้า 22.1

ที่ N เป็นแสนทั้งสองวิธีได้ 2494295369 คู่เท่ากัน ซึ่งเกิน int ไปแล้วจริงๆ ลูปซ้อนใช้เวลาเกือบสิบวินาทีแม้เปิด -O2 ส่วน merge sort นับล้านตัวได้ในหนึ่งในสิบวินาที แถวลูปซ้อนวัดใหม่พร้อมกับหน้า 18.2 ที่ N = 10⁴ ได้ใกล้กัน แต่ที่ N = 10⁵ หน้า 18.2 ได้ราว 13 วินาที เพราะหน้านั้นสร้างข้อมูลด้วย rand() ซึ่งมีค่าซ้ำกันมาก ข้อมูลต่างกัน เวลาของโปรแกรมเดียวกันก็ต่างกันได้

นับเงื่อนไขอื่นข้ามครึ่ง

วิธีนี้ใช้ได้กว้างกว่าคู่สลับ ข้อเท็จจริงที่ใช้มีแค่สองข้อ ข้อแรก คู่ข้ามครึ่งไม่เปลี่ยนแม้เรียงแต่ละครึ่งแล้ว ข้อสอง พอสองครึ่งเรียงแล้ว นับคู่ข้ามครึ่งที่ผ่านเงื่อนไขได้ด้วยตัวชี้ที่เดินทางเดียว เช่น ถ้าต้องการคู่ i < j ที่ a_i > a_j + D ให้ไล่ j ในครึ่งขวาจากน้อยไปมาก แล้วเลื่อนตัวชี้ในครึ่งซ้ายข้ามทุกตัวที่ไม่เกิน a_j + D ตัวที่เหลือในครึ่งซ้ายผ่านเงื่อนไขทั้งหมด พอ j ถัดไปมีค่ามากขึ้น ตัวชี้ก็ไม่ต้องถอยกลับ งานจึงเป็น O(n) ต่อการรวมหนึ่งครั้งเหมือนเดิม เงื่อนไขแบบนี้ไม่ตรงกับการเทียบที่ใช้รวม จึงต้องนับเป็นลูปแยก ก่อน รวม แบบฝึกหัดข้อ 6 และข้อ 7 ใช้วิธีนี้

อีกแบบที่เจอบ่อยคือกรรมการสองคนจัดอันดับผู้เข้าแข่งขัน N คน อยากรู้ว่ามีกี่คู่ที่สองคนเห็นไม่ตรงกันว่าใครดีกว่า ให้เรียงผู้เข้าแข่งขันตามอันดับของกรรมการคนแรก แล้วเขียนอันดับของกรรมการคนที่สองตามลำดับนั้น คู่ที่ขัดกันก็คือคู่สลับของลำดับที่ได้

ลองทำให้พัง

แบบที่ 1 นับด้วย int

เขียนตัวนับและค่าที่คืนเป็น int แล้วทดสอบกับแถวที่เรียงจากสูงไปเตี้ย ซึ่งทุกคู่เป็นคู่สลับ คำตอบที่ถูกคือ N(N - 1)/2 โปรแกรมนี้สร้างแถวเองจาก N

#include <bits/stdc++.h>
using namespace std;

int count_inversions(vector<int> &a, vector<int> &temp, int lo, int hi)
{
    if (hi - lo <= 1) {
        return 0;
    }
    int mid = (lo + hi) / 2;
    int count = count_inversions(a, temp, lo, mid) + count_inversions(a, temp, mid, hi);
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (a[i] <= a[j]) {
            temp[k] = a[i];
            i++;
        } else {
            temp[k] = a[j];
            j++;
            count += mid - i;
        }
        k++;
    }
    while (i < mid) {
        temp[k] = a[i];
        i++;
        k++;
    }
    while (j < hi) {
        temp[k] = a[j];
        j++;
        k++;
    }
    for (int t = lo; t < hi; t++) {
        a[t] = temp[t];
    }
    return count;
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = n - i;
    }
    vector<int> temp(n);
    int count = count_inversions(a, temp, 0, n);
    cout << "inversions = " << count << '\n';
    return 0;
}

100000

inversions = 704982704

คำตอบที่ถูกคือ 100000 × 99999 / 2 = 4999950000 แต่ได้ 704982704 ซึ่งเป็นเลขบวกที่ดูปกติ ไม่มีอะไรบอกว่าผิด ป้อน 65536 ยังได้ 2147450880 ถูกต้อง แต่ 65537 ได้ -2147450880 ชุดทดสอบเล็กผ่านหมด แล้วไปตกเฉพาะชุดใหญ่ แบบเดียวกับที่หน้า 1.3 เตือนไว้ ก่อนเขียนให้คำนวณคำตอบที่มากที่สุดจากขอบเขตเสมอ

แบบที่ 2 ใช้ < แทน <=

ในโปรแกรม count-swaps เปลี่ยนเงื่อนไขของการรวมเป็น

if (a[i] < a[j]) {

ข้อมูลเข้าชุดเดิมยังได้ swaps = 14 เพราะไม่มีใครสูงเท่ากัน แต่ป้อนห้าคนที่สูง 150 เท่ากันหมด ได้ swaps = 10 แทนที่จะเป็น 0 และ 140 140 135 140 ได้ 5 แทนที่จะเป็น 2 เมื่อสองตัวเท่ากัน < หยิบตัวขวาก่อน แล้วนับตัวที่เท่ากันในฝั่งซ้ายเป็นคู่สลับไปด้วย ผลของการเรียงยังถูกทุกตัว จึงมองไม่ออกจากการพิมพ์อาเรย์ ชุดทดสอบของโจทย์นับคู่ต้องมีค่าซ้ำเสมอ

สรุป

• คู่สลับคือคู่ i < j ที่ a_i > a_j เท่ากับจำนวนครั้งที่ต้องสลับตัวที่อยู่ติดกันจนเรียง
• คู่ทั้งหมดแบ่งเป็นคู่ในครึ่งซ้าย คู่ในครึ่งขวา และคู่ข้ามครึ่ง การเรียงแต่ละครึ่งไม่ทำให้จำนวนคู่ข้ามครึ่งเปลี่ยน
• ระหว่างรวม ทุกครั้งที่หยิบจากครึ่งขวา บวก mid - i ได้ O(N log N) แทน O(N²) บนเครื่องที่วัด แสนตัวใช้ 0.009 วินาทีแทน 14.5 วินาที
• ตัวนับต้องเป็น long long และค่าที่เท่ากันต้องหยิบจากซ้ายก่อนด้วย <=
• เงื่อนไขอื่นที่นับด้วยตัวชี้ทางเดียวบนสองครึ่งที่เรียงแล้วได้ ให้นับเป็นลูปแยกก่อนรวม