0%

0-20 set

問題

如果今天,我需要支援以下兩種操作:

  1. 插入一個數字
  2. 查詢比一個數字大的最小元素是什麼

一個簡單的想法是,就用一個陣列通通存起來,然後查詢時一個一個找。這樣對於第一種插入操作是 $O(1)$ ,第二種是 $O(N)$。

另一個是,插入時使用 insertion sort 方法,讓整個陣列維持排序好的狀態。搜尋時就能直接使用 upper_bound 函式。這樣對於第一種插入操作是 $O(N)$ ,第二種是 $O(logN)$。

在插入與查詢次數差不多的情況下,這兩種方法都無法快速的解決問題。

二元搜尋樹

雖然現在大家可能還沒有樹的概念,還是請大家看看這個教學。

二元搜尋樹

二元搜尋樹保證,一個節點左邊一定全部都比它小,右邊一定全部比它大。

可以發現,以上兩種操作都可以透過二元搜尋樹來完成。而複雜度則是以樹的深度(從一開始走到沒路可走時的最長距離)來決定。

在一般的二元搜尋樹中,深度並沒有保證(想像插入的數字一直遞增),最高與元素數量 $N$ 相等。

但,若現在有一種二元搜尋樹,可以透過旋轉、換根等操作,保證在任何時刻,深度都是 $O(logN)$,這個題目就可以很好的解決了。

而 set 就可以做到這樣的事情!set 的內部,正是平衡二元搜尋樹之一的紅黑樹

不同於之前的 queue 與 stack,這超難實作的,所以就直接進用法。

set 語法

set,意為集合,集合內不會存在兩個相同元素。

宣告一個 set 名為 s。

1
set<int> s;

插入元素,若 set 內部已存在該元素,則無任何動作。

1
s.insert(5);

移除元素,若 set 內部無該元素,則無任何動作。也可以移除一個 iterator 所指向的元素,程式會自動判斷傳入型態。

1
2
s.erase(5);
s.erase(s.begin())

回傳該元素的 iterator,若 set 內部無該元素,則回傳 end()。

1
s.find(5);

依照順序輸出內部所有元素,複雜度 $O(N)$。

1
for(int i:s) cout << i << '\n';

問一個元素在不在 set 裡。可透過 find 的 return 值,或使用 s.count。

1
2
if(s.find(10) != s.end()) cout << "In!\n";
if(s.count(10)) cout << "In!\n";

得到 set 的第一項,可使用 *s.begin(),最後一項使用 *s.rbegin()。

1
2
cout << *s.begin() << '\n';
cout << *s.rbegin() << '\n';

那,可以輸出 set 中第 K 小的數字嗎?答案是不行的,set 沒有辦法做到這點。因此,set 中是沒有 s[k] 這樣的語法的。

但是,set 的 iterator,可以支援 ++, – 的運算,而且是 $O(1)$ 的。所以,若能以一個變數將 begin() 存下來,之後將其 ++,便可以得到第 2 大的數字。

要怎麼儲存呢?用變數。那型態是什麼?是:

1
set<int>::iterator iter = s.begin();

這名稱實在太長,因此我們使用 C++11 後出現的新功能:自動判斷型態!

1
2
auto iter = s.begin();
cout << *(++iter) << '\n';

因此,遍歷 set 也可以寫成:

1
2
3
for(auto iter = s.begin(); iter != s.end(); iter++){
cout << *iter << '\n';
}

此外,若要得到一個 iterator 的前/後一項,可以使用 prev/next,這樣不會改到本身,常見於得到 set 中最大的數。

1
cout << *prev(s.end()) << '\n';

回來看看

原來的問題,要如何用 set 去做呢?

操作一很簡單,就是 insert 而已。

操作二呢?恩…好像還是沒辦法,如果 set 中存在要被查詢的那個數,可以寫:

1
2
auto iter = s.find(x);
cout << *(++iter) << '\n';

但若不存在,find 函式回傳 end,就沒辦法了。

若是有一個類似 upper_bound 的函式就好了…

對,沒錯,set 的成員函式有 upper_bound()!

1
cout << *s.upper_bound(5) << '\n';

順帶一提,upper_bound(s.begin(), s.end(), 5)這種寫法也能輸出正確答案,但是複雜度是糟糕的 $O(size)$。請忘記這種用法,記住 s.upper_bound() 就好!

連續刪除 a 到 b 區間內元素

1
2
3
for(auto iter = s.find(5); iter != s.end() && *iter < 10; iter++){
s.erase(iter);
}

這是對的嗎?看起來好像是,但其實不是,而且會導致 RE。為什麼呢?

當 iter 被 erase 後,它就不存在了,因此將其++後會發生什麼事?沒有人知道。

怎麼辦呢?

s.erase() 這個函式,其實不是 void,它會回傳被刪除的元素的下一個 iterator。

因此可以利用這個性質:

1
for(auto iter = s.find(5); iter != s.end() && *iter < 10; iter = s.erase(iter));

我需要有多個相同元素的 set

set 在 insert 時,遇到相同元素會忽略,常常會因為這樣產生許多 bug。比如,插入 5 個 1 後刪除 1 個 1,在 set 中就不存在 1 了,但你真正想做的事,可能是跟剩下的 4 個 4 有關。

那要怎麼讓 set 中有多個元素呢?

第一個辦法是,多紀錄一個變數 cnt,代表每個元素的個數。只在 cnt 從 0 變為 1 時將其加入 set,從 1 變為 0 時將其移除。

但是,其實,STL 中有個東西叫 multiset,可以同時存在多個相同元素!

語法大致與 set 相同,但有一些東西要注意:

  1. 可用 .count() 函式回傳 multiset 中元素數量。
  2. s.erase(10) 代表的意思是:刪除 multiset 中所有的 10,若只刪除一個要用 s.erase(s.find(10))

我不需要排序,我只需要知道哪些東西在裡面

STL 中,有個東西叫 unordered_set,底層以 hash 實作。插入與刪除的複雜度皆為常數稍大的 $O(1)$,一般來說會比 set 的 $O(logN)$ 快。

unordered_set 失去 lower_bound 與 upper_bound 功能,遍歷時也不會照大小輸出,其餘功能與 set 相同。

自訂比較函式

這裡的比較函式跟 sort 的不一樣,是一個 struct,裡面有一個 operator(),所以要這樣寫:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;

int sum_of_digits(int x){
int ans = 0;
while(x){
ans += x%10;
x/=10;
}
return ans;
}

struct cmp{
bool operator()(int a, int b){
return sum_of_digits(a) < sum_of_digits(b);
}
};

set<int, cmp> s;

int main(){
ios::sync_with_stdio(0), cin.tie(0);
s.insert(56);
s.insert(11);
s.insert(7);
for(auto i:s) cout << i << '\n';
}

預設的比較函式是 less<>,有另一個定義好的比較函式是 greater<>,所以如果要從大排到小,可以這樣寫。

1
set<int, greater<int>> s;

練習

TIOJ 1911

85 分解:
ZJ b938

★★★ TOJ 275

★★★★ TIOJ 1161

★★★★★ TOJ 512

★★★★★★★★ TIOJ 1941

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// TIOJ 1911
#include<bits/stdc++.h>
using namespace std;
#define ll long long
multiset<ll> m;
int n;

int main() {
ios::sync_with_stdio(0), cin.tie(0);
while(cin >> n){
if(n == 0) break;
if(n > 0) m.insert(n);
else{
if(m.empty()) continue;
if(n == -1){
cout << *m.begin() << ' ';
m.erase(m.begin());
}
else{
auto iter = m.end();
iter--; // end 的前一個才是真正最大的
cout << *iter << ' ';
m.erase(iter);
}
}
}
cout << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// ZJ b938 85 分解
#include<bits/stdc++.h>
using namespace std;
int n, m;
set<int> s;
bool dead[1000005];

int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++) s.insert(i);
for(int i=1,x;i<=m;i++){
cin >> x;
if(dead[x]) cout << "0u0 ...... ?\n";
else{
auto iter = s.upper_bound(x);
if(iter == s.end()) cout << "0u0 ...... ?\n";
else{
cout << *iter << '\n';
dead[*iter] = 1;
s.erase(iter);
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// TOJ 275
// 分成小的堆跟大的堆,保持兩邊的個數差異在1以內。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
multiset<ll> small, big;

void pop_big(){
ll x = *big.begin();
small.insert(x);
big.erase(big.begin());
}

void pop_small(){
ll x = *small.rbegin();
big.insert(x);
small.erase(prev(small.end()));
}

int main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(6);
cin >> n;
for(int i=1,x;i<=n;i++){
cin >> x;

if(i == 1 || x < *small.rbegin()) small.insert(x);
else big.insert(x);

while(big.size() > i/2) pop_big();
while(big.size() < i/2) pop_small();

double ans;
if(i&1) ans = *small.rbegin();
else ans = (*small.rbegin() + *big.begin()) * 1.0 / 2;
cout << ans << '\n';
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 枚舉其中一個點數
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

multiset<int,greater<int>> s;
int n, k;
pii arr[1000005];

void solve(){
s.clear();
cin >> n >> k;
for(int i=1;i<=n;i++) cin >> arr[i].first >> arr[i].second;
sort(arr+1, arr+n+1);
int ans = 1e9;
for(int i=1;i<=n;i++){
s.insert(arr[i].second);
if(s.size() > k) s.erase(s.begin());
if(s.size() == k) ans = min(ans, arr[i].first + *s.begin());
}
cout << ans << '\n';
}

int main(){
int t; cin >> t; while(t--) solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// TOJ 512
// 每次操作 1 最多增加 2 個錯誤位置,以 set 維護錯誤位置,使你在 log 時間內能夠刪除 1 個錯誤位置
#include<bits/stdc++.h>
using namespace std;

set<int> s;
int n, q;
int arr[1000005], pos[1000005];

void change(int x, int y){
s.erase(x);
s.erase(y);
swap(arr[x], arr[y]);
pos[arr[x]] = x;
pos[arr[y]] = y;
//cout << x << " " << y << " " << arr[x] << " " << arr[y] << '\n';
if(arr[x] != x) s.insert(x);
if(arr[y] != y) s.insert(y);
}

int recover(int x, int y){
int ans = 0;
while(1){
auto iter = s.lower_bound(x);
if(iter == s.end() || *iter > y) break;
ans++;
change(pos[*iter], *iter);
}
return ans;
}

int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
for(int i=1;i<=n;i++) pos[i] = arr[i] = i;
for(int i=1,ope,a,b;i<=q;i++){
cin >> ope >> a >> b;
if(ope == 1) change(a, b);
else cout << recover(a, b) << '\n';
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// TIOJ 1941
// 建議先了解 LIS 以後再來
// 注意加入一隻寶可夢時,LIS表格的變化
// 以set儲存LIS改變的位置即可
#include<bits/stdc++.h>
using namespace std;
multiset<int> s;
int n;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=1,l,r;i<=n;i++){
cin >> l >> r;
s.insert(l);
auto iter = s.upper_bound(r);
if(iter != s.end()) s.erase(iter);
}
cout << s.size() << '\n';
}