19.2 lower_bound upper_bound และ equal_range

หน้า 16.5 สอนวิธีใช้ lower_bound กับ upper_bound ไปแล้ว ทั้งความหมายของสองตัวและกฎนับจำนวนค่าด้วยการลบตำแหน่ง หน้านี้ไม่ทวนซ้ำ แต่เปิดดูข้างใน lower_bound คือฟังก์ชัน first_at_least ในหน้า 19.1 ทุกประการ upper_bound คือ first_greater ส่วน equal_range คืนทั้งสองค่าพร้อมกัน พอรู้ว่าแต่ละตัวหารอยต่อของเงื่อนไขอะไร ก็เลือกใช้ได้ถูกตัว ไม่ต้องลองผิดลองถูกว่าต้องบวกหรือลบหนึ่ง แล้วเอาไปใช้นับค่าในช่วง และค้นบนผลรวมสะสมได้

ข้างในคือรอยต่อ

ทั้งสามตัวค้นแบบแบ่งครึ่งเหมือนลูปในหน้า 19.1 จึงเป็น O(log n) และใช้ได้กับข้อมูลที่เรียงจากน้อยไปมากแล้วเท่านั้น สิ่งที่คืนมาเป็น iterator ตามบทที่ 16 ไม่ใช่ตัวเลข เอาไปลบด้วย begin() จะได้ index ถ้าไม่มีช่องไหนผ่านเงื่อนไข จะได้ end() ซึ่งลบแล้วได้ n เหมือนที่ฟังก์ชันของเราตอบ n

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

int main()
{
    vector<int> scores = {45, 52, 52, 52, 60, 71, 71, 88};
    vector<int> queries = {52, 53, 71, 10, 100};
    for (int k = 0; k < (int)queries.size(); k++) {
        int x = queries[k];
        int lower = lower_bound(scores.begin(), scores.end(), x) - scores.begin();
        int upper = upper_bound(scores.begin(), scores.end(), x) - scores.begin();
        cout << "x=" << x << " lower=" << lower << " upper=" << upper << " count=" << upper - lower << '\n';
    }
    return 0;
}

x=52 lower=1 upper=4 count=3
x=53 lower=4 upper=4 count=0
x=71 lower=5 upper=7 count=2
x=10 lower=0 upper=0 count=0
x=100 lower=8 upper=8 count=0

เทียบกับโปรแกรม count-bounds ในหน้า 19.1 ที่ใช้คะแนนชุดเดียวกัน lower ตรงกับ less และ upper ตรงกับ at_most ทุกบรรทัด ชื่อฟังก์ชันจำง่ายถ้านึกถึงการแทรก lower_bound คือตำแหน่งซ้ายสุดที่แทรก x ได้โดยข้อมูลยังเรียงอยู่ upper_bound คือตำแหน่งขวาสุด ช่องระหว่างสองตำแหน่งนี้คือ x ทุกตัวที่มีอยู่แล้ว

equal_range

ถ้าต้องการทั้งสองค่า equal_range คืน pair ของ iterator ตัวแรกคือผลของ lower_bound ตัวที่สองคือผลของ upper_bound ชนิดของ pair นี้ยาวมาก จึงประกาศด้วย auto ให้ compiler ใส่ชนิดให้เอง

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

int main()
{
    vector<int> scores = {45, 52, 52, 52, 60, 71, 71, 88};
    auto range = equal_range(scores.begin(), scores.end(), 52);
    cout << "first 52 at " << range.first - scores.begin() << '\n';
    cout << "after last 52 at " << range.second - scores.begin() << '\n';
    cout << "count = " << range.second - range.first << '\n';
    return 0;
}

first 52 at 1
after last 52 at 4
count = 3

range.second ชี้ช่อง ถัดจาก 52 ตัวสุดท้าย ไม่ใช่ตัวสุดท้ายเอง แบบเดียวกับ end() ที่ชี้เลยช่องสุดท้ายไปหนึ่งช่อง ลบสอง iterator กันจึงได้จำนวนพอดีโดยไม่ต้องบวกหนึ่ง

นับค่าในช่วง

ร้านค้ามีสินค้า N ชิ้น ลูกค้าถามว่ามีสินค้าราคาตั้งแต่ a ถึง b บาทกี่ชิ้น ราคาสูงได้ถึง 10⁹ จึงใช้อาเรย์นับแบบหน้า 5.3 ไม่ได้ ให้เรียงราคาก่อนครั้งเดียว แล้วตอบแต่ละคำถามด้วยรอยต่อสองจุด

ของใหม่คือขอบสองข้างเป็นคนละค่า ใช้กฎนับจากหน้า 16.5 คนละข้อ index ของ lower_bound(a) คือจำนวนชิ้นที่ราคาน้อยกว่า a และ index ของ upper_bound(b) คือจำนวนชิ้นที่ราคาไม่เกิน b ลบกันได้จำนวนชิ้นที่ราคาตั้งแต่ a ถึง b รวมทั้งสองขอบ

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> prices(n);
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
    }
    sort(prices.begin(), prices.end());
    for (int k = 0; k < q; k++) {
        int low, high;
        cin >> low >> high;
        int from = lower_bound(prices.begin(), prices.end(), low) - prices.begin();
        int to = upper_bound(prices.begin(), prices.end(), high) - prices.begin();
        cout << to - from << '\n';
    }
    return 0;
}

9 4
2590 18900 990 4500 990 12000 7490 4500 35000
1000 5000
990 4500
20000 30000
0 100000

3
5
0
9

เรียงแล้วราคาเป็น 990 990 2590 4500 4500 7490 12000 18900 35000 คำถามแรกได้ 2590 กับ 4500 สองชิ้น รวมสาม คำถามที่สองมีราคาที่ตรงขอบพอดีทั้งสองข้าง ได้ทั้ง 990 สองชิ้นและ 4500 สองชิ้น เพราะ lower_bound นับตั้งแต่ตัวแรกที่เท่ากับ a และ upper_bound เลยตัวสุดท้ายที่เท่ากับ b ไปแล้ว ถ้าสลับกันใช้ จะตกขอบ ซึ่งเป็นจุดที่ชุดทดสอบชอบดัก งานทั้งหมดคือเรียง O(N log N) กับตอบ Q ข้อข้อละ O(log N)

ค้นบนผลรวมสะสม

binary search ไม่ได้ใช้ได้แค่กับข้อมูลที่โจทย์ให้มาเรียงแล้ว อาเรย์อะไรก็ตามที่ เรียงอยู่แล้วโดยธรรมชาติ ก็ใช้ได้ ตัวอย่างที่เจอบ่อยที่สุดคือผลรวมสะสมของจำนวนที่ไม่ติดลบ ซึ่งไม่มีทางลดลง

น้องวางแผนอ่านหนังสือ N วัน วันที่ i อ่าน a_i หน้า บางวันไม่ได้อ่านเลย มีคำถามว่า ถ้าต้องอ่านให้ครบ t หน้า จะครบในวันที่เท่าไร คำตอบคือวันแรกที่ผลรวมสะสมถึง t ซึ่งก็คือ lower_bound บนอาเรย์ prefix ของหน้า 5.4

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> prefix(n + 1, 0);
    for (int day = 1; day <= n; day++) {
        int pages;
        cin >> pages;
        prefix[day] = prefix[day - 1] + pages;
    }
    for (int k = 0; k < q; k++) {
        long long target;
        cin >> target;
        int day = lower_bound(prefix.begin() + 1, prefix.end(), target) - prefix.begin(); // (1)!
        if (day > n) { // (2)!
            cout << "never" << '\n';
        } else {
            cout << "day " << day << '\n';
        }
    }
    return 0;
}

1. เริ่มค้นที่ prefix.begin() + 1 เพราะช่อง 0 คือผลรวมของศูนย์วัน ไม่ใช่วันจริง แต่ยังลบด้วย prefix.begin() เพื่อให้ได้เลขวันตรงกับ index ของ prefix
2. ไม่เจอได้ end() ซึ่งลบแล้วคือ n + 1 แปลว่าอ่านครบทุกวันแล้วก็ยังไม่ถึง

7 5
30 45 0 0 60 25 40
30
31
75
76
201

day 1
day 2
day 2
day 5
never

ผลรวมสะสมคือ 30 75 75 75 135 160 200 วันที่ 3 กับ 4 ไม่ได้อ่าน ค่าจึงซ้ำกันสามช่อง ถาม 75 ได้วันที่ 2 ซึ่งเป็นวันแรกที่ถึง ถูกต้องเพราะ lower_bound ให้ตัวแรกเสมอ ถ้าเขียน binary search แบบหน้า 9.4 ที่หยุดเมื่อเจอ อาจได้วันที่ 3 หรือ 4 ก็ได้

วิธีนี้ใช้ได้เพราะจำนวนหน้าไม่ติดลบ ถ้าข้อมูลมีค่าติดลบได้ เช่น กำไรขาดทุนรายวัน ผลรวมสะสมขึ้นๆ ลงๆ ไม่เรียง binary search ใช้ตรงๆ ไม่ได้ หน้า 19.5 จะแสดงวิธีรับมือกับกรณีนั้น

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

วัดบนเครื่องเดียวกับหน้า 19.1 ราคาสินค้า N = 100000 ชิ้น สุ่มตั้งแต่ 1 ถึง 10⁹ ไม่ได้เรียงมา คำถาม Q = 100000 ข้อ ช่วงสุ่ม วิธีตรงไปตรงมาไล่ดูสินค้าทุกชิ้นทุกคำถามแบบหน้า 5.3 เป็น O(NQ) อีกวิธีคือโปรแกรม price-range ข้างบน เป็น O((N + Q) log N) รันแต่ละแบบ 5 รอบ

วิธีไล่ต้องเทียบ 10¹⁰ ครั้งเต็มๆ เพราะต้องดูครบทุกชิ้นทุกคำถาม ช้ากว่าการไล่ในหน้า 19.1 ที่หยุดได้กลางทาง ส่วนวิธีเรียงแล้วค้น เวลาเกือบทั้งหมดคือการอ่านข้อมูลกับการเรียงครั้งเดียว

ลองทำให้พัง

แบบที่ 1 ลืมเรียง

ในโปรแกรม price-range ลบบรรทัด sort ออก แล้วใช้ข้อมูลเข้าชุดเดิม

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> prices(n);
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
    }
    for (int k = 0; k < q; k++) {
        int low, high;
        cin >> low >> high;
        int from = lower_bound(prices.begin(), prices.end(), low) - prices.begin();
        int to = upper_bound(prices.begin(), prices.end(), high) - prices.begin();
        cout << to - from << '\n';
    }
    return 0;
}

9 4
2590 18900 990 4500 990 12000 7490 4500 35000
1000 5000
990 4500
20000 30000
0 100000

3
8
0
9

ไม่มี error ไม่มี warning คำตอบแรกบังเอิญถูก แต่คำตอบที่สองได้ 8 แทนที่จะเป็น 5 lower_bound ไม่ได้ตรวจว่าข้อมูลเรียงหรือยัง มันแค่ทิ้งครึ่งหนึ่งตามที่เห็นช่องกลาง ถ้าข้อมูลไม่เรียง ครึ่งที่ทิ้งอาจมีคำตอบอยู่ อันตรายตรงที่ตัวอย่างในโจทย์บางข้อบังเอิญเรียงมาให้ หรือบังเอิญได้คำตอบถูก แล้วไปตกในชุดทดสอบที่ซ่อนไว้

แบบที่ 2 อ่านค่าที่ end()

อยากรู้ว่าสินค้าที่ถูกที่สุดในบรรดาชิ้นที่ราคาอย่างน้อย budget ราคาเท่าไร จึงเขียน * หน้าผลของ lower_bound เพื่ออ่านค่าที่ iterator ชี้

int cheapest = *lower_bound(prices.begin(), prices.end(), budget);
cout << "cheapest at least " << budget << " is " << cheapest << '\n';

ราคาสินค้าห้าชิ้นคือ 2590 990 4500 7490 12000 ป้อน budget เป็น 4000 ได้ cheapest at least 4000 is 4500 ถูกต้อง แต่ป้อน 50000 ซึ่งแพงกว่าทุกชิ้น บนเครื่องที่เขียนเอกสารนี้ได้

cheapest at least 50000 is 0

lower_bound คืน end() ซึ่งชี้เลยช่องสุดท้ายไป ไม่มีข้อมูลจริงอยู่ตรงนั้น การอ่านค่าที่ end() คืออ่านนอก vector เหมือนอ่านเกินอาเรย์ในหน้า 5.5 ผลที่ได้ขึ้นกับว่าหน่วยความจำตรงนั้นมีอะไรค้างอยู่ ครั้งนี้บังเอิญได้ 0 ซึ่งดูเหมือนคำตอบปกติ จึงจับยากกว่าโปรแกรมที่พังทันที ต้องเช็กก่อนอ่านทุกครั้ง

auto it = lower_bound(prices.begin(), prices.end(), budget);
if (it == prices.end()) {
    cout << "none" << '\n';
} else {
    cout << *it << '\n';
}

สรุป

• lower_bound ให้ช่องแรกที่ >= x upper_bound ให้ช่องแรกที่ > x ทั้งคู่เป็น O(log n) ลบด้วย begin() ได้ index
• จำนวน x คือ upper_bound ลบ lower_bound หรือ equal_range ส่วน count ไล่ทุกช่อง
• จำนวนค่าตั้งแต่ a ถึง b คือ upper_bound(b) ลบ lower_bound(a)
• ผลรวมสะสมของจำนวนที่ไม่ติดลบเรียงอยู่แล้ว ใช้ lower_bound หาวันแรกที่ยอดสะสมถึงเป้าได้
• ต้องเรียงข้อมูลก่อนเสมอ และต้องเช็ก end() ก่อนอ่านค่าที่ iterator ชี้