c807 - 一維凸包問題
題目描述
題目要求維護一個一維點集，並支援插入點和移除區間內的點兩種操作。每次操作後，輸出該點集的一維凸包的頂點數和頂點座標（由小到大排列）。一維凸包即為點集的最左邊和最右邊的點。
解題思路
使用 set 資料結構來儲存點集。set 能夠自動排序，並且提供高效的插入、刪除和查找操作。
- 插入操作：直接將點插入
set中。 - 移除操作：使用
set的lower_bound方法找到區間的起始和結束迭代器，然後使用erase方法移除區間內的點。 - 凸包計算：如果
set的大小小於 2，則輸出set的大小。如果大小等於 1，則輸出該點。如果大小大於 1，則輸出 2 以及set的第一個和最後一個元素。
複雜度分析
- 時間複雜度: O(N log N)，其中 N 是操作次數。插入和刪除操作在
set中都是 O(log N)，而遍歷所有操作是 O(N)。 - 空間複雜度: O(N)，
set最多儲存 N 個點。
程式碼
#include <iostream>
#include <set>
using namespace std;
int n,is,k,l;
set <int> st;
set <int> :: iterator it,it2;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
while(n--){
cin >> is;
if(is==1){
cin >> k;
st.insert(k);
}
else{
cin >> k >> l;
it = st.lower_bound(k);
it2 = st.lower_bound(l+1);
st.erase(it,it2);
}
if(st.size()<2)cout << st.size() << " ";
if(st.size()==1)cout << *st.begin();
else if(st.size()>1)cout << "2 " << *st.begin() << " " << *(--st.end());
cout << "\n";
}
}