Lời dẫn

Một bài toán QHĐ bao lồi thường phải giải quyết hai truy vấn có dạng:

1. Cho hai số ~a,b~, thêm vào tập đường thẳng ~S~ một đường thẳng ~y=ax+b~.
2. Cho số ~x~, tìm đường thẳng ~y=ax+b~ thuộc ~S~ sao cho ~y~ lớn nhất (với ~y~ nhỏ nhất, ta chỉ việc đảo dấu tất cả các ~a~ và ~b~ cùng kết quả)

(tránh nhầm lẫn với bài toán tìm bao lồi của một tập điểm trong không gian)

Ở đây, ta định nghĩa một cấu trúc bao lồi là một cấu trúc dữ liệu giải quyết các truy vấn này.

Một cấu trúc bao lồi thông dụng (có trong link ở trên) sẽ dựng nên một tập con ~S'~ của ~S~ mà mỗi đường thẳng thành phần sẽ chứa các giá trị ~y~ lớn nhất trong một khoảng nhất định (nếu ta chỉ xem xét các khoảng đó thì nó được gọi là một hình bao dưới) với các khả năng như sau:

• Xử lý bài toán với ~a~ và ~x~ được thêm vào theo thứ tự không giảm trong thời gian ~O(n+q)~
• Xử lý bài toán với ~a~ được thêm vào theo thứ tự không giảm trong thời gian ~O(n+q \log n)~

với ~n~ và ~q~ lần lượt là số các truy vấn loại 1 và 2.

Cấu trúc trên sử dụng một stack lưu ~S'~ theo thứ tự ~a~ tăng dần. Vì các ~a~ được cho cũng không giảm nên:

• mỗi đường thẳng mới sẽ được đưa vào cuối stack, và
• các đường thẳng bị loại bỏ (nếu có) cũng theo thứ tự từ cuối stack về trước,

do đó mỗi truy vấn loại 1 chỉ sử dụng trung bình ~O(1)~ phép tính.

Tuy nhiên, nếu các ~a~ được cho ngẫu nhiên thì không thể đảm bảo những điều ở trên. Để giải quyết vấn đề này, có thể sử dụng cây Li Chao. Tuy nhiên, cây Li Chao bản chất là một Segment Tree nên sẽ mang những nhược điểm cố hữu của cấu trúc đó, tiêu biểu là:

• Với các tọa độ ~x~ lớn, sẽ phải rời rạc hóa hoặc sử dụng cây Segment Tree động.
• Có hằng số tính toán đáng kể (được biểu diễn ở cuối bài).

Ở đây, tác giả xin được giới thiệu một cấu trúc bao lồi khác, cải tiến từ cấu trúc ban đầu, bằng cách chuyển từ stack thành std::multiset. Cấu trúc này được sáng tác bởi Simon Lindholm, cựu sinh viên Viện công nghệ Hoàng gia Thụy Điển, có huy chương IOI từ năm lớp 8.

Chi tiết

Trong cấu trúc này, với mỗi đường thẳng ~d: y_d=a_dx+b_d~, ngoài việc lưu hệ số góc ~a_d~ và giao điểm với trục Oy ~b_d~, ta sẽ lưu số ~x_d~ là hoành độ của giao điểm giữa đường thẳng này và đường thẳng liền sau nó trong hình bao dưới. Nói cách khác, với mọi ~x~ trong khoảng ~[x_{d'},x_d]~ (với ~d'~ là đường thẳng liền trước ~d~ trong hình bao dưới) thì kết quả cho truy vấn loại 2 tại ~x~ sẽ là ~y_d~:

struct line {
    int a, b;
    mutable int x;  // x-intersect with the next line in the hull
    bool operator<(const line& other) const { return a < other.a; }
    bool operator<(const int& other_x) const { return x < other_x; }
};

(trong cấu trúc đường thẳng có sử dụng kiểu dữ liệu mutable, cho phép thay đổi tùy ý một dữ liệu thành phần mà không phải xóa đi thêm lại cả cấu trúc)

Với tập ~S'~, ta sẽ lưu nó theo thứ tự ~a~ tăng dần như sau:

class convex_hull : private multiset<line, less<>> {
    static const int inf = 1e18;
   public:
    int div(int a, int b) {  // floored division
        return a / b - ((a * b) < 0 && a % b);
    }
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    bool overtake(iterator l1, iterator l2) {
        if (l2 == end()) return l1->x = inf, false;
        // if l2 is NULL, set l1->x and return immediately
        if (l1->a == l2->a) l1->x = l1->b > l2->b ? inf : -inf;
        // if the two line share the same slope, simply retain the one with the
        // higher y-intercept
        else l1->x = div(l2->b - l1->b, l1->a - l2->a);
        // x-intersect satisfies (l1->a)*x + l1->b = (l2->a)*x + l2->b
        return l1->x >= l2->x;
    }
...

Hàm overtake() tính xem đường thẳng ~l_1~ có thể hoàn toàn thay thế đường thẳng ~l_2~ hay không; nếu có thì chỉ số ~x~ của ~l_1~ sau này sẽ phải tính lại; nếu không, chỉ số ~x~ của ~l_1~ chính là hoành độ giao điểm của hai đường thẳng liên tiếp ~l_1~ và ~l_2~ trong ~S'~. Độc giả nên xem các ứng dụng của hàm này ở dưới để có hiểu biết sâu sắc về hàm này.

Thêm một đường thẳng

Ta nhận thấy rằng, khi thêm một đường thẳng mới, sẽ có hai trường hợp xảy ra:

• đường thẳng này nằm ngoài hình bao dưới hiện có:
• đường thẳng này cắt ngang đường bao dưới, được thêm vào ~S'~, và có thể sẽ thay thế một vài đường thẳng khác:

Gọi đường thẳng này là ~C~, trước hết, chúng ta cần kiểm tra xem: ~C~ có cắt đường bao dưới hay không. Việc này rất đơn giản:

• gọi ~P~ là đường thẳng có hệ số góc lớn nhất mà không vượt quá hệ số góc của ~C~ trong ~S'~
• gọi ~N~ là đường thẳng có hệ số góc nhỏ nhất mà không nhỏ hơn hệ số góc của ~C~ trong ~S'~

Dễ dàng nhận ra rằng việc ~C~ cắt đường bao dưới tương đương với việc hoành độ của giao điểm giữa ~P~ và ~C~ bé hơn hoành độ của giao điểm giữa ~N~ và ~C~. Chú ý là, nếu hệ số góc của ~C~ nhỏ hơn tất cả các hệ số góc trong ~S'~ thì ~C~ chắc chắn nằm trong hình bao dưới, vì khi đi về âm vô cực thì ~y_c~ sẽ vượt lên đầu:

auto C = insert({a, b, 0}), N = C, P = C;

overtake(C, ++N);// calculating the x-intersect of C and N

if (C != begin()) {
    int backup_p = (--P)->x;
    if (overtake(P, C)) {  // calculating the x-intersect of C and P
        erase(C);
        P->x = backup_p;
        return;
    }
}

Bây giờ, với ~C~ đã nằm trong ~S'~, việc của ta sẽ là tìm và xóa các đường thẳng thừa thãi khỏi ~S'~. Ta sẽ chia các đường thẳng này thành hai tập:

• tập ~A~: có hệ số góc lớn hơn hoặc bằng hệ số góc của ~C~ (phần màu tím trong hình)
• tập ~B~: có hệ số góc bé hơn hệ số góc của ~C~ (phần màu xanh bạc hà trong hình)

Có thể nhận ra rằng, mỗi đường thẳng thuộc tập ~A~ khi và chỉ khi:

• có hệ số góc thỏa mãn
• chỉ số ~x~ của nó bé hơn hoặc bằng hoành độ của giao điểm của nó với ~C~

while (overtake(C, N))
    N = erase(N);

Đường thẳng ~N~ đầu tiên không thỏa mãn hai điều kiện trên cũng chính là đường thẳng nối tiếp ~N~ trong đường bao dưới, và do đó, khi thực hiện xong hàm overtake(C, N) cuối cùng thì chỉ số ~x~ của ~C~ cũng đã được xác định.

Với tập ~B~, chúng ta sẽ làm khác đi một chút. Vì trong cấu trúc thì tập các chỉ số ~x~ phải tăng ngặt nên ta sẽ xóa đi các đường thẳng mà chỉ số ~x~ của nó bé hơn chỉ số ~x~ của đường thẳng liền trước. Chú ý là xóa xong thì ta phải tính lại chỉ số ~x~ của đường thẳng liền trước.

while (1) {
    C = P; if (C == begin()) break;
    P--; if (P->x < C->x) break;
    overtake(P, erase(C));
    // Since every invalid lines after and including C have been removed,
    // erase(C) is actually the originally added line, 
    // and we recompute line P's p-index using that exact line.
}

Tìm ~y~ lớn nhất

Có lẽ là phần dễ thở nhất của cấu trúc này. Vì ta đã có danh sách các ~p~ nên chỉ cần tìm đường thẳng ~d~ có ~p~ nhỏ nhất mà không nhỏ hơn ~x~, vậy kết quả sẽ là ~y_d~:

int query(int x) {
    if (empty()) return -inf;
    auto d = lower_bound(x);
    return d->a * x + d->b;
}

Phân tích thời gian

Cả hai loại truy vấn đều diễn ra trong ~O(\log n)~ phép tính. Vậy, cấu trúc này có thể xử lý ~n~ truy vấn loại 1 và ~q~ truy vấn loại 2 trong ~O((n+q)\log n)~ phép tính.

So sánh với cây Li Chao

Cả hai cấu trúc đều có những điểm đặc biệt riêng:

• Cây Li Chao: xử lý được cả đoạn thẳng, dễ nhớ với người đã hiểu về Segment Tree
• Cấu trúc trong bài: xử lý được với ~a,b,x~ bất kỳ, trong khoảng lớn

Trên thực tế, nếu muốn sử dụng cấu trúc trong bài (hay cấu trúc dùng stack được nhắc đến đầu bài) để quản lý các đoạn thẳng, ta chỉ việc lồng thêm một Segment Tree, mà mỗi nút ~[l,r]~ sẽ chứa tất cả các đoạn thẳng chứa cả đoạn ~[l,r]~. Nếu làm thế này, độ phức tạp của cả hai cấu trúc sẽ tăng thêm ~O(\log C)~ lần, với ~C~ là độ dài khoảng giới hạn của các ~x~.

Với cấu trúc trong bài, độ phức tạp đó là ~O((n+q) \log n \log C)~, ngang với độ phức tạp của cây Li Chao quản lý đoạn thẳng.

Về thời gian xử lý:

Cấu hình phần cứng:

• AMD Ryzen 9 5900HS, 4650 MHz
• 32GB RAM, 3200 MHz

Cấu hình phần mềm:

• Windows Subsystem for Linux 1.3.14.0
• GCC 13.1.1 20230714
• Lệnh biên dịch: g++ ~1.cpp -o ~1 -O2 -pipe

Tổng thời gian thực hiện 32 test với ~a,b,x~ ngẫu nhiên trong khoảng ~[-10^6,10^6]~:

Như vậy, có thể thấy rằng:

• Với trường hợp ít chênh lệch nhất (chỉ có truy vấn loại 1) thì cấu trúc trong bài nhanh hơn cây Li Chao khoảng 126%.
• Với số truy vấn của 2 loại ngang nhau, cấu trúc trong bài nhanh hơn khoảng 360%.
• Với trường hợp chênh lệch nhiều nhất (gần như chỉ có truy vấn loại 2) thì cấu trúc trong bài nhanh hơn đến 1150%.
• Với cùng số truy vấn hai loại:
  • càng ít truy vấn loại 1 thì cấu trúc trong bài càng nhanh (lên đến 200%)
  • càng ít truy vấn loại 2 thì cây Li Chao càng nhanh (lên đến 85%)

Đọc thêm

Lời giải của tác giả cho bài Acquire (USACO 3/2008) sử dụng cấu trúc được mô tả.

Header mẫu của tác giả Simon Lindholm.

Bài viết giới thiệu về QHĐ bao lồi. Tác giả: Phan Minh Hoàng, Lê Anh Đức.

Mẫu so sánh.