có thể xài set<pair<int, int>>
với custom comparator cho pair<int, int>
, mỗi pair đại diện cho 1 đoạn số [a, b]
. pair 1 < pair 2 khi b1 + 1 < a2
. Ví dụ khi insert 6,9,2,13,8,14,10,7,5 thì thực hiện như sau:
- ban đầu set rỗng
- insert 6: tìm [6,6] trong set, ko thấy, insert [6,6]
-> set chứa [6,6]
- insert 9: tìm [9,9] trong set, ko thấy, insert [9,9]
-> set chứa [6,6], [9,9]
- insert 2: tìm [2,2] trong set, ko thấy, insert [2,2]
-> set chứa [2,2], [6,6], [9,9]
- insert 13: tìm [13,13] trong set, ko thấy, insert [13,13]
-> set chứa [2,2], [6,6], [9,9], [13,13]
- insert 8: tìm [8,8] trong set, thấy [9,9], xóa [9,9] khỏi set, tìm tiếp [8,8] trong set, ko thấy, vậy merge [8,8] và [9,9] được [8,9], insert [8,9] lại vào set
-> set chứa [2,2], [6,6], [8,9], [13,13]
- insert 14: tìm [14,14] trong set, thấy [13,13], xóa [13,13] khỏi set, tìm tiếp [14,14] trong set, ko thấy, vậy merge [14,14] và [13,13] được [13,14], insert [13,14] lại vào set
-> set chứa [2,2], [6,6], [8,9], [13,14]
- insert 10: tìm [10,10] trong set, thấy [8,9], xóa [8,9] khỏi set, tìm tiếp [10,10] trong set, ko thấy, vậy merge [10,10] và [8,9] được [8,10], insert [8,10] lại vào set
-> set chứa [2,2], [6,6], [8,10], [13,14]
- insert 7: tìm [7,7] trong set, thấy [6,6], xóa [6,6] khỏi set, tìm tiếp [7,7] trong set, thấy [8,10], xóa [8,10] ra khỏi set, merge [7,7], [6,6] và [8,10] được [6,10], insert [6,10] lại vào set
-> set chứa [2,2], [6,10], [13,14]
- insert 5: tìm [5,5] trong set, thấy [6,10], xóa [6,10] khỏi set, tìm tiếp [5,5] trong set, ko thấy, vậy merge [5,5] và [6,10] được [5,10], insert [5,10] lại vào set
-> set chứa [2,2], [5,10], [13,14]
còn tìm số bé nhất thì xài 1 biến int m = 0, mỗi khi hỏi thì tìm [m,m] trong set (chỉ cần xét với set.begin()
là đủ), nếu ko thấy thì insert m. Nếu thấy m thuộc [a,b] thì gán m = b + 1 rồi insert m :V
bước insert tìm và xóa tối đa 2 lần, cộng thêm 1 lần insert, vậy là 5 operations, 5 * O(logn) vẫn là O(logn)
bước ? tìm m bé nhất là O(1) vì chỉ so sánh với set.begin()
:V sau đó insert thì O(logn).
tổng cộng n lần là O(nlogn). 10^6 thì hơi vật vã
code mẫu
#include <set>
struct MySet {
struct ClosedInterval {
int a;
int b;
ClosedInterval(int a, int b) : a{a}, b{b} {}
bool operator<(const ClosedInterval& rhs) const {
return b + 1 < rhs.a; //
}
void mergeWith(const ClosedInterval& other) {
if (b + 1 == other.a) b = other.b;
else /*if (other.b + 1 == a)*/ a = other.a;
}
};
std::set<ClosedInterval> s;
int m = 0;
void insert(int k) {
ClosedInterval kk{k, k};
if (auto it = s.find(kk); it != end(s)) {
kk.mergeWith(*it);
s.erase(it);
if ((it = s.find(kk)) != end(s)) {
kk.mergeWith(*it);
s.erase(it);
}
}
s.insert(kk);
}
int findMinNotInSet() {
if (!s.empty()) {
auto& [a, b] = *begin(s);
if (a <= m && m <= b) m = b + 1;
}
return m;
}
};
chôm ý tưởng từ https://web.engr.oregonstate.edu/~erwig/papers/Diet_JFP98.pdf