山姆的競程日記

從綠牌開始的旅途

0%

分塊法與莫隊算法

發表於 更新於 Disqus：

今天不知道要學什麼
所以就找了一個還沒學過的演算法
而分塊法和莫隊算法是我還沒有碰過的演算法
所以就來學一下這兩個演算法吧

分塊算法 Square Root Decomposition (又稱根號算法）

分塊法是個什麼樣的演算法呢？

其實他跟線段樹的概念非常相似
線段樹的作法是將一個陣列劃分為 $2^n$ 的長度去詢問

而分塊法則是分為 $\sqrt{n}$ 塊

由於線段樹分為 $2^n$ 的長度 因此詢問時則是 $O(logn)$
而分為 $\sqrt{n}$ 的分塊法則是在 $O(\sqrt{n})$ 的時間完成詢問

一般的線段樹會需要 $2n$ 或 $4n$ 的空間儲存區間的值
而分塊則是需要額外的 $\sqrt{n}$ 的空間儲存
如何建立分塊呢？

1
2
3
for(int i = 0;i < n;i++){
    block[i/k] = //想要儲存的東西
}

而在詢問時 我們會有兩個步驟

(一) 將不再分塊範圍的值用暴力法詢問
(二) 詢問區間的分塊

1
2
3
4
5
6
7
8
9
10
11
for(int i = l;i <= r;i++){
    if(i/k!=l/k) break;
    //暴力詢問區間左段的值
}
for(int i = r;i >= l;i--){
    if(i/k!=r/k) break;
    //暴力詢問區間右段的值
}
for(int i = l/k+1;i < r/k;i++){
    //詢問分塊的值
}

可能看完程式碼還是不太懂
現在就讓我們來看看例題吧

分塊法 例題

一、區間最小值 Range Minimum Query (RMQ)

給予 $n$ 個數字的陣列 以及 $q$ 個詢問

每次詢問 $[l,r]$

請輸出 $[l,r]$ 中的最小值

線段樹 (Segment Tree) 與稀疏表（Sparse Table) 的經典題
而我們也可以嘗試使用分塊法來完成這樣的題目

可以去 Zerojudge d539 丟丟看自己的解（不過是區間最大值）

程式碼

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
42
#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 5e5+5;
int k;

int a[N];
int block[N];

int query(int l, int r){
	int ans = INT_MAX;
	for(int i = l;i <= r;i++){
		if(i/k!=l/k) break;
		ans = min(ans,a[i]);
	}
	for(int i = r;i >= l;i--){
		if(i/k!=r/k) break;
		ans = min(ans,a[i]);
	}
	for(int i = l/k+1;i < r/k;i++) ans = min(ans,block[i]);
	return ans;
}

signed main(){
	fastio
	int n;
	cin >> n;
    k = sqrt(n);
	for(int i = 0;i < n;i++) cin >> a[i]; 
	for(int i = 0;i <= n;i++) block[i/k] = min(block[i/k],a[i]);
	int m;
	cin >> m;
	while(m--){
		int l, r;
		cin >> l >> r;
		l--,r--;
		cout << query(l,r) << "\n";
	}
}

二、帶修改的區間最小值

前面做過區間最小值的題目了
但是題目不可能那麼單純只出區間最小值吧
線段樹能做到的修改 分塊當然也行

如果是單點修改 修改 $i$ 位置的值
我們就直接修改陣列中 $i$ 位置和他所在的分塊的值 複雜度 $O(1)$

1
2
3
4
void modify(int i, int x){
	arr[i] += x;
	block[i/k] += x;
}

但是如果是區間修改呢 我們直接修改區間的值呢？
僅僅是修改一次 整個複雜度會被提高到 $O(n)$
所以我們又要利用到線段樹用過的概念 「懶惰標記」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void modify(int l, int r, int x){
	for(int i = l/k+1;i < r/k;i++){
		block[i] += k*x, lz_tag[i] += x;
	}
	for(int i = l;i <= r;i++){
		if(i/k!=l/k) break;
		a[i] += x;
	}
        if(l/k==r/k) return; //如果l和r在同一塊裡面 執行兩次會造成數值加了兩次
	for(int i = r;i >= l;i--){
		if(i/k!=r/k) break;
		a[i] += x;
	}
}

分析上面的程式碼
我們在區間加值時 最多會執行 $\sqrt{n}$ 次 （區間內不完全包住的塊總和最多兩塊）
因此時間複雜度為 $O(\sqrt{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
27
28
int query(int l, int r){
	int ans = INT_MAX;
	if(lz_tag[l/k]){
		for(int i = (l/k)*k; i < (l/k+1)*k;i++){
			a[i] += lz_tag[l/k];
		}
		lz_tag[l/k] = 0;
	}

	if(lz_tag[r/k]){
		for(int i = (r/k)*k; i < (r/k+1)*k;i++){
			a[i] += lz_tag[r/k];
		}
		lz_tag[r/k] = 0;
	}

	for(int i = l;i <= r;i++){
		if(i/k!=l/k) break;
		ans = min(ans,a[i]);
	}

	for(int i = r;i >= l;i--){
		if(i/k!=r/k) break;
		ans = min(ans,a[i]);
	}
	for(int i = l/k+1;i < r/k;i++) ans = min(ans,block[i]);
	return ans;
}

這樣我們就完成區間加值了

複雜度: $O(n\sqrt{n})$

三、更多例題代補

代補

莫隊算法 Mo’s Algorithm

莫隊算法是由2009年中國國家代表隊的隊長「莫濤」所提出來的
一種處理區間問題的離線處理演算法 時間複雜度也非常好

什麼是莫隊算法

首先，我們先來看看一個問題

給予 $n$ 項的陣列以及 $q$ 個詢問
每次詢問 $[l,r]$ 問在區間內 共有幾個不同的數字
$1 \leq n \leq 10^5，1 \leq q \leq n$

我們如何去思考這個問題呢

如果我們用暴力的方式去處理這個問題 詢問的複雜度會是 $O(n)$

如果我們有 $q$ 次詢問 複雜度就會是 $O(qn)$

這樣子的時間無法過這個題目

那我們換個想法 我們有兩個指針 $l,r$

我們知道 $[l,r]$ 這個區間的答案

我們可以在 $O(1)$或 $O(logn)$ 的時間找到 $[l-1,r],[l+1,r],[l,r-1],[l,r+1]$答案

我們用這兩個指針加加減減去找到詢問的區間的答案：
用一個陣列 $cnt$ 紀錄每個數字的出現次數

當 $cnt[val] = 1$ 的時候 就代表多了一個數字

利用這個想法 我們可以寫出下面這樣的程式

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
const int N = 1e5+5;

int arr[N], cnt[N], tmp;

void add(int pos){
	if(!cnt[arr[pos]]) tmp++;
	cnt[arr[pos]]++;
}

void sub(int pos){
	cnt[arr[pos]]--;
	if(!cnt[arr[pos]]) tmp--;
}

signed main(){
	fastio
	int n;
	cin >> n;
	for(int i = 0;i < n;i++) cin >> arr[i];
	int q;
	cin >> q;
	int l = 0, r = -1;
	for(int i = 0;i < q;i++){
		int ql,qr;
		cin >> ql >> qr;
		while(l < ql) sub(l++);
		while(l > ql) add(--l);
		while(r < qr) add(++r);
		while(r > qr) sub(r--);
		cout << tmp << "\n";
	}
}

不過你會發現 這樣子的程式
當詢問很多時 指針會一直來來回回的
時間複雜度也不會很好 大概是 $O(n^2)$ 吧

因此 莫隊算法就是建立在這個的基礎上去優化這種解法

我們可以經由排序來使這個演算法在 $O(n\sqrt{n})$ 的時間完成所有詢問

如何使用莫隊算法

我們將 $q$ 筆詢問 分別依照 $l$ 所在的分塊進行排序
如果 $l$ 所在的分塊相等 則依照 $r$ 進行排序
只要這樣做之後就能使原本 $O(n^2)$ 的解法降低為 $O(n\sqrt{n})$ 了

因為每一個分塊的詢問都依照 $r$ 進行排序了

因此最多只要 $O(n\sqrt{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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
const int N = 1e6+5;
int k;


int a[N], cnt[N], bid[N], l = 1, r = 0, tmp= 0;
	
struct query{
	int l,r, id;
	bool operator < (const query b){
		return (l/k == b.l/k ? r < b.r : l/k < b.l/k);
	}
};

void add(int pos){
	if(!cnt[a[pos]]) tmp++;
	cnt[a[pos]]++;
}

void sub(int pos){
	--cnt[a[pos]];
	if(!cnt[a[pos]]) tmp--;
}

signed main(){
	fastio
	int n;
	cin >> n;
	k = sqrt(n)+1;
	for(int i = 1;i <= n;i++) cin >> a[i];
	int m;
	cin >> m;
	vector<query> Q;
	int ans[m];
	for(int i = 0;i < m;i++){
		int ql, qr;
		cin >> ql >> qr;
		Q.push_back({ql,qr,i});
	}
	sort(Q.begin(),Q.end());
	for(auto q : Q){
		while(l < q.l) sub(l++);
		while(l > q.l) add(--l);
		while(r < q.r) add(++r);
		while(r > q.r) sub(r--);
		ans[q.id] = tmp;
	}
	for(auto x : ans) cout << x << "\n";
}

這樣就完成區間共幾個不同數字的詢問了

可以去SPOJ-DQUERY解解看這題

莫隊算法 例題

一、區間眾數

Zerojudge題目連結

這題要知道的是眾數的出現次數以及眾數有幾個
我們可以用一個陣列 $cnt$ 紀錄每個數字的出現次數
然後再用另外一個陣列紀錄出現次數的次數
這樣我們就可以在 $O(1)$ 時間維護我們的答案了

程式碼

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e5+5;
int k;
struct query{
	int l,r,id;
	bool operator < (query b){
		return (l/k == b.l/k ? r < b.r : l/k < b.l/k);
	}
};
int a[N], cnt[N], cntcnt[N], ans;

void add(int val){
	cntcnt[cnt[val]]--;
	cnt[val]++;
	cntcnt[cnt[val]]++;
	if(cntcnt[cnt[val]] == 1) ans = max(cnt[val],ans);
}

void sub(int val){
	cntcnt[cnt[val]]--;
	cnt[val]--;
	cntcnt[cnt[val]]++;
	if(ans==cnt[val]+1&&cntcnt[cnt[val]+1]==0) ans = cnt[val];
}

signed main(){
	fastio
	int n,m;
	cin >> n >> m;
	k = sqrt(n);
	for(int i = 1;i <= n;i++) cin >> a[i];
	vector<query> Q;
	for(int i = 0;i < m;i++){
		int l,r;
		cin >> l >> r;
		Q.push_back({l,r,i});
	}
	int ans1[m], ans2[m];
	sort(Q.begin(),Q.end());
	int l = 1, r = 0;
	cntcnt[0] = n;
	for(query q : Q){
		while(l < q.l) sub(a[l++]);
		while(l > q.l) add(a[--l]);
		while(r < q.r) add(a[++r]);
		while(r > q.r) sub(a[r--]);
		ans1[q.id] = ans, ans2[q.id] = cntcnt[ans];
	}
	for(int i = 0;i < m;i++) cout << ans1[i] << " " << ans2[i] << "\n";
}

二、Codeforces 617E - XOR and Favorite Number

題目連結

這題要維護的是區間的XOR值為他所給的數字

我們都知道XOR的性質是 $a \oplus b = c$ 則 $c \oplus b = a$

然後XOR和加法一樣 求區間和我們會使用前綴和 要求區間XOR也可以使用前綴XOR來求解

程式碼

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e5+5;
int k;
struct query{
	int l, r, id;
	bool operator < (query b){
		return (l/k == b.l/k ? r < b.r : l/k < b.l/k); 
	}
};

int arr[N], pref[N], cnt[1<<20], tmp, num;

void add(int val){
	tmp += cnt[val ^ num];
	cnt[val]++;
}

void sub(int val){
	cnt[val]--;
	tmp -= cnt[val ^ num];
}

signed main(){
	fastio
	int n,m;
	cin >> n >> m >> num;
	k = sqrt(n);
	for(int i = 1;i <= n;i++){
		cin >> arr[i];
		pref[i] = pref[i-1]^arr[i];
	}
	vector<query> Q;
	int ans[m];
	for(int i = 0;i < m;i++){
		int l,r;
		cin >> l >> r;
		l--; //由於我們做的是前綴XOR 所以區間XOR = pref[r] ^ pref[l-1]
		Q.push_back({l,r,i});
	}
	sort(Q.begin(),Q.end());
	int l = 1, r = 0;
	for(auto q : Q){
		while(l < q.l) sub(pref[l++]);
		while(l > q.l) add(pref[--l]);
		while(r < q.r) add(pref[++r]);
		while(r > q.r) sub(pref[r--]);
		ans[q.id] = tmp;
	}
	for(auto x : ans) cout << x << "\n";
}

Codeforces 877F - Ann and Books

題目連結

給予 $n$ 本書（數學或經濟）以及一個 $k$ 值

問一個區間有幾個子區間的數學書比經濟多 $k$ 本

這題跟上面那題XOR有異曲同工之妙
基本兩題就差在XOR與加法而已

這題我們可以把經濟的書以負的做計算去做前綴和
左界的更新與右界的更新也有點不同
然後剩下的作法與上一題一模一樣
不過這題不同點是 $k$ 的值很大 沒有辦法使用陣列來維護
如果使用 map 來維護 還是會因為 $O(q\sqrt{n}\log{n})$ 太大而TLE

因此 這題我們要用到離散化的技巧

程式碼

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#pragma GCC optimize(2)
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 3e5+5;
int k;
struct query{
	int l,r,id;
	bool operator < (query b){
		return (l/k == b.l/k ? r < b.r : l/k < b.l/k); 
	}
};

int arr[N], pref[N], tmp, num, up[N], down[N];
int cnt[N];

void addl(int i){
	tmp += cnt[up[i]];
	cnt[arr[i]]++;
}

void addr(int i){
	tmp += cnt[down[i]];
	cnt[arr[i]]++;
}

void subl(int i){
	cnt[arr[i]]--;
	tmp -= cnt[up[i]];
}

void subr(int i){
	cnt[arr[i]]--;
	tmp -= cnt[down[i]];
}

signed main(){
	fastio
	int n;
	cin >> n >> num;
	k = sqrt(n);
	for(int i = 1;i <= n;i++){
		cin >> arr[i];
		if(arr[i]==2) arr[i] = -1;
	}
	for(int i = 1, a; i <= n;i++){
		cin >> a;
		arr[i]*=a;
	}
	for(int i = 1;i <= n;i++){
		pref[i] = pref[i-1] + arr[i];
	}
	vector<int> v;
	for(int i = 0;i <= n;i++){
		v.push_back(pref[i]);
		v.push_back(pref[i]+num);
		v.push_back(pref[i]-num);
	}
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());
	for(int i = 0;i <= n;i++){
		arr[i] = lower_bound(v.begin(),v.end(),pref[i]) - v.begin() + 1;
		up[i] = lower_bound(v.begin(),v.end(),pref[i]+num) - v.begin() + 1;
		down[i] = lower_bound(v.begin(),v.end(),pref[i]-num) - v.begin() + 1;
	}
	int m;
	cin >> m;
	int ans[m];
	vector<query> Q;
	for(int i = 0;i < m;i++){
		int l,r;
		cin >> l >> r;
		l--;
		Q.push_back({l,r,i});
	}
	sort(Q.begin(),Q.end());
	int l = 0, r = -1;
	for(auto q : Q){
		while(l < q.l) subl(l++);
		while(l > q.l) addl(--l);
		while(r < q.r) addr(++r);
		while(r > q.r) subr(r--);
		ans[q.id] = tmp;
	}
	for(auto x : ans) cout << x << "\n";
}

四、更多例題代補

代補

帶修改莫隊 (10/4更)

既然有區間詢問 那我們當然也需要區間更新阿

莫隊算法當然也能夠做到區間更新

我們將上面的題目做一點小修改

給予 $n$ 項的陣列以及 $q$ 個詢問或操作

每次詢問 $[l,r]$ 問在區間內 共有幾個不同的數字

每次操作給予 $x,v$ 將陣列第 $x$ 個位置的數字改為 $v$

$1 \leq n \leq 10^5，1 \leq q \leq n$

如何做到這一點呢

當莫隊將詢問做排序之後 我們該如何考慮到修改呢？

這裡 我們可以將原本的 Query 增加一個變數 $t$ 表示時間

在排序時 這個 $t$ 也會是我們要考慮的一部分

我們會依照詢問的 $l$ 所在的分塊做排序 若相同 則用 $r$ 所在的分塊排序

若 $r$ 所在的分塊相同 我們則依照 $t$ 去做排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct query{
	int l, r, t, id;
	bool operator < (query b){
	    if(l/k==b.l/k){
                //l的分塊相同
                if(r/k==b.r/k){
                    //r的分塊相同
                    return t < b.t;
                }
                return r/k < b.r/k;
            }
            return l/k < b.l/k;
	}
};

就像上面那樣做 然後我們在詢問時 也要多一個 $t$ 的指針
1
2
3
4
5
6
while(l < q.l) sub(arr[l++]);
while(l > q.l) add(arr[--l]);
while(r < q.r) add(arr[++r]);
while(r > q.r) sub(arr[r--]);
while(t < q.t) modify(Q[i],M[++t]);
while(t > q.t) modify(Q[i],M[t--]);

然後修改時 如果修改的位置在 $[l,r]$ 以內

我們就要修改答案的值 不然就直接修改陣列中的值就可以了

這邊有個很重要的一點 就是分塊的大小不在是 $\sqrt{n}$ 了

我們必須將分塊的大小設為 $\sqrt[3]{n^2}$ 才會有最佳的複雜度

而帶修改莫隊的複雜度為 $O(\sqrt[3]{n^5})$ 也是已經把 $O(n^2)$ 的複雜度降低非常多了

而上面例題的程式碼我附在這裡 題目可以去 洛谷P1903 解解看

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 2e5+5e4;
const int S = 1e6+5;
int k;

struct query{
	int l, r, t, id;
	bool operator < (query b){
		return (l/k==b.l/k  ? (r/k == b.r/k ? t < b.t : r/k < b.r/k) : l/k < b.l/k);
	}
} Q[N];


struct upd{
	int pos,x;
} M[N];	

int arr[N], cnt[S], ans[N], tmp;

void add(int val){
	if(!cnt[val]) tmp++;
	cnt[val]++;
}

void sub(int val){
	cnt[val]--;
	if(!cnt[val]) tmp--;
}

void modify(query x, upd &y){
	if(x.l <= y.pos && y.pos <= x.r){
		sub(arr[y.pos]);
		add(y.x);
	}
	swap(arr[y.pos],y.x);
}

signed main(){
	fastio
	int n, m;
	cin >> n >> m;
	k = pow(n,(double)2/(double)3);
	for(int i = 1;i <= n;i++) cin >> arr[i];
	int tid = 0, qid = 0;
	for(int i = 0;i < m;i++){
		char q;
		cin >> q;
		if(q=='Q'){
			int l, r;
			cin >> l >> r;
			Q[qid] = {l,r,tid,qid};
			qid++;
		}else{
			int x, val;
			cin >> x >> val;
			++tid;
			M[tid] = {x,val};
		}
	}
	sort(Q,Q+qid);
	int l = 1, r = 0, t = 0;
	for(int i = 0;i < qid;i++){
		auto q = Q[i];
		while(l < q.l) sub(arr[l++]);
		while(l > q.l) add(arr[--l]);
		while(r < q.r) add(arr[++r]);
		while(r > q.r) sub(arr[r--]);
		while(t < q.t) modify(Q[i],M[++t]);
		while(t > q.t) modify(Q[i],M[t--]);
		ans[q.id] = tmp;
	}
	for(int i = 0;i < qid;i++) cout << ans[i] << "\n";
}

帶修改莫隊 例題

一、Codeforces 940F - Machine Learning

題目連結

給一個 $n$ 項的陣列 以及 $q$ 行 Query

有兩種 Query

（一）區間詢問 $Mex$ 值 ($Mex$ 是一陣列中最小未出現的非負整數)

（二）單點修改

$1 \leq n,q \leq 10^5$

這題也是很裸的帶修改莫隊 可以自己解看看

時間複雜度: $O(n^{\frac{5}{3}})$

二、更多例題代補

代補

樹上莫隊

代補

心得

今天學了莫隊算法之後 覺得這個演算法真的很厲害

不但很好使用 也有很多應用：樹上莫隊、帶修改莫隊之類的

不過自己還沒學到那麼多

這篇文章也會持續隨著自己的學習更新