從零開始的演算法競賽入門教學
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';
}