2025-04-14  /2025/04/14/alogrithm/ 99+   17 分钟   2.5 k0次访问

alogrithm

一辈子能坚持一件事情就很伟大了！

本文章是 基于 左神课程 + 牛客课程 进行算法系统式学习的模版，用于比赛时候的板子。

任务安排（📑） 完成情况（✅）
线性基 136 + 137
基础算法汇总

基础算法

类并查集

如果是分联通块进行计算，我们可以不使用并查集，使用一个简单的思路，给每一个联通块编号，从而来考虑每一个联通块之间的关系。

  • E. Graph Composition(div3)

    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
    #include<bits/stdc++.h>
    using namespace std;

    #define int long long

    void __(){
    	int n, m1, m2;
    	cin >> n >> m1 >> m2;
    	vector<vector<int>> a1(n + 1);
    	vector<vector<int>> a2(n + 1);
    	
    	for(int i = 0; i < m1; i++){
    		int u, v;
    		cin >> u >> v;
    		a1[u].push_back(v);
    		a1[v].push_back(u);
    	}
    	
    	for(int i = 0; i < m2; i++){
    		int u, v;
    		cin >> u >> v;
    		a2[u].push_back(v);
    		a2[v].push_back(u);
    	}
    	// 进行编号
    	vector<int> col1(n + 1,0);
    	vector<int> col2(n + 1, 0);
    	auto dfs2 = [&](auto f,int u, int k) -> void{
    		col2[u] = k;
    		for(auto x : a2[u]){
    			if(col2[x] == 0){
    				f(f,x,k);
    			}
    		}
    	};
    	auto dfs1 = [&](auto f, int u, int k) -> int{
    		int cnt = 0;
    		col1[u] = k;
    		for(auto x : a1[u]){
    			if(col1[x] == 0){
    			if(col2[x] != k) cnt++;
    			else cnt += f(f,x,k);}
    		}
    		return cnt;
    	};
    	int ans = 0;
    	for(int i = 1; i <= n; i++){
    		if(col2[i] == 0){
    			dfs2(dfs2,i,i);
    		}
    		if(col1[i] == 0){
    			ans += dfs1(dfs1,i,col2[i]);
    			if(col2[i] < i) ans ++; // 在前面有代表节点的时候便已经访问过这个节点，但是在F图中这个 i 节点并没有被 初始化，说明前面的代表节点和这个节点之间应该要增加一条边
    		}
    	}
    	cout << ans << endl;
    }
    signed main(){
    	int _;
    	cin >> _;
    	while(_--) __();
    }

数据结构

线段树

基础线段树

区间查询，区间变化，区间重置

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
#define fr first
#define sc second

const int N = 1e5 + 10;
int sum[4 * N];
int ad[4 * N];
int a[N];
int change[4 *N];
bool vis[4 * N];
/*
  区间查询，区间变化，区间重置
*/
void build(int l, int r, int i){
	if(l == r){
	   sum[i] = a[r];
	   return;
	}
	int mod = (l + r) >> 1;
	build(l, mod, i << 1);
	build(mod + 1, r, i << 1 | 1);
	sum[i] = sum[i << 1] + sum[i << 1 | 1];
	ad[i] = 0;
	change[i] = 0;
	vis[i] = false;
}
void down(int i, int ln, int rn){
	if(vis[i]){
	  sum[i << 1] = change[i] * ln;
	  change[i << 1] = change[i];
	  vis[i << 1] = true;
	  sum[i << 1 | 1] = change[i] * rn; 	
	  change[i << 1 | 1] = change[i];
	  vis[i << 1 | 1] = true;
	  vis[i] = false;
	}
	if(ad[i] != 0){
		sum[i << 1] += (ln * ad[i]);
		ad[i << 1] += ad[i];
		sum[i << 1 | 1] += (rn * ad[i]);
		ad[i << 1 | 1] += ad[i];
		ad[i] = 0;
	}
}
void add(int wol, int wor, int wov, int l, int r, int i){
	if(l >= wol && r <= wor){
		sum[i] += (r - l + 1) * wov;
		ad[i] += wov;
		return;
	}
	
	int mid = (l + r) >> 1;
	/*
	  l -> mid mid + 1-> r
	*/
	down(i, (mid - l + 1), (r - mid));
	if(wol <= mid){
		add(wol, wor, wov, l, mid, i << 1);
	}
	if(wor >= mid + 1){
		add(wol, wor, wov, mid + 1, r, i << 1 | 1);
	}
	sum[i] = sum[i << 1] + sum[i << 1 | 1];
}
void cha(int wol, int wor, int wov, int l, int r, int i){
	if(l >= wol && r <= wor){
		sum[i] = (r - l + 1) * wov;
	    change[i] = wov;
	    vis[i] = true;
	    return;
	}
	int mid = (l + r) >> 1;
	down(i, (mid - l + 1), (r - mid));
	if(wol <= mid){
		cha(wol, wor, wov, l, mid, i << 1);
	}
	if(wor >= mid + 1){
		cha(wol, wor, wov, mid + 1, r, i << 1 | 1);
	}
	sum[i] = sum[i << 1] + sum[i << 1 | 1];
}
int query(int wol, int wor, int l, int r, int i){
	if(wol <= l && r <= wor){
		return sum[i];
	}
	int mid = (l + r) >> 1;
	down(i, (mid - l + 1), (r - mid));
	int ans = 0;
	if(wol <= mid){
		ans += query(wol, wor, l, mid, i << 1);
	}
	if(wor >= mid + 1){
		ans += query(wol, wor, mid + 1, r, i << 1 | 1);
	}
	return ans;
}
signed main(){
	/*
	  1 1 1 1 6
	*/
       int n;
       cin >> n;
       for(int i = 1; i <= n; i++) cin >> a[i];
       build(1, n, 1);
       int q1,q2;
       cin >> q1;
       while(q1--){
       	int t1, t2, t3;
       	cin >> t1 >> t2 >> t3;
       	add(t1, t2, t3,1,n,1);
       }
       int chl, chr, chv;
       cin >> chl >> chr >> chv;
       cha(chl, chr, chv, 1, n, 1);
       cin >> q2;
       while(q2--){
       	int l,r;
       	cin >> l >> r;
       	cout << query(l , r, 1, n, 1) << endl; 
       }
}

区间重置 + 范围查询

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
#define PII pair<int,int>
#define fr first
#define sc second
/*
  范围重置 + 范围查询（线段树）

*/
const int N = 1e5 + 10;
int Max[4 * N]; // 需要 4 * N
int a[N];
// 懒更新 (访问才往下推)
int change[4 * N];
bool update[4 * N];

/*
  ad 表示当前需要下发的信息，当前节点已经修正
*/
// O(n)
void build(int l, int r, int i){
	if(l == r){
		Max[i] = a[r];
		return;
	}
	int mid = (l + r) >> 1; // 最后一定会达到相等，不会出现越界情况
	build(l, mid, i << 1);
	build(mid + 1, r, i << 1 | 1);
	Max[i] =max( Max[i << 1],Max[i << 1 | 1]);
	change[i] = 0, update[i] = false;
}
// 懒信息下发

void down(int i, int ln, int rn){
	if(update[i]){
		update[i << 1] = true;
		change[i << 1] = change[i];
		Max[i << 1] = change[i];
		update[i << 1 | 1] = true;
		change[i << 1 | 1] = change[i]; 
		Max[i << 1 | 1] = change[i];
		update[i] = false;
	}
}

// O(nlog(n)) 范围查询
int query(int wol, int wor, int l, int r, int i){
	if(l >= wol && r <= wor){
	   return Max[i];	
	}
	int ans = 0;
	int mid = (l + r) >> 1;
	down(i, mid - l + 1, r - mid);
	if(mid >=wol){
		ans =max(ans,query(wol, wor, l, mid, i << 1));
	}
	if(mid + 1<= wor){
		ans = max(ans,query(wol, wor, mid + 1, r, i << 1 | 1));
	}
	return ans;
}

// 范围i增加


void up(int wol, int wor, int wov, int l, int r, int i){
   	if(wol <=  l && r <= wor){
   		change[i] = wov;
   		update[i] = true;
   		Max[i] = wov; 
   		return;
   	}
   	int mid = (l + r) >> 1;
   	down(i, mid - l + 1, r - mid);
   	if(wol <= mid){
   		up(wol, wor, wov, l, mid, i << 1);
   	}
   	if(wor >= mid + 1){
   		up(wol, wor, wov, mid + 1, r, i << 1 | 1);
   	}
   	Max[i] = max(Max[i << 1], Max[i << 1 | 1]);
   	// cout << i << " " << Max[i] << endl;
}
signed main(){
       int n;
       cin >> n;
       for(int i = 1; i <= n; i++) cin >> a[i];
       build(1, n, 1);
       int q1;
       cin >> q1;
       while(q1--){
       	int l, r, v;
       	cin >> l >> r >> v;
       	up(l, r, v, 1, n, 1);
       }
       int q;
       cin >> q;
       while(q --){
       	int l, r;
       	cin >> l >> r;
       	cout << query(l, r, 1, n, 1) << endl;
       }
}

范围修改 + 范围查询

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
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
#define PII pair<int,int>
#define fr first
#define sc second
/*
  范围修改 + 范围查询（线段树）

*/
const int N = 1e5 + 10;
int sum[4 * N]; // 需要 4 * N
int a[N];
int ad[4 * N]; // 懒更新 (访问才往下推)
/*
  ad 表示当前需要下发的信息，当前节点已经修正
*/
// O(n)
void build(int l, int r, int i){
	if(l == r){
		sum[i] = a[r];
		return;
	}
	int mid = (l + r) >> 1; // 最后一定会达到相等，不会出现越界情况
	build(l, mid, i << 1);
	build(mid + 1, r, i << 1 | 1);
	sum[i] = sum[i << 1] + sum[i << 1 | 1];
	ad[i] = 0;
}

// 懒信息下发

void down(int i, int ln, int rn){
	if(ad[i] != 0){
		sum[i << 1] += ln * ad[i];
		ad[i << 1] += ad[i];
		sum[i << 1 | 1] += rn * ad[i];
		ad[i << 1 | 1] += ad[i];
		ad[i] = 0;
	}
}


// O(nlog(n)) 范围查询
int query(int wol, int wor, int l, int r, int i){
	if(l >= wol && r <= wor){
	   return sum[i];	
	}
	int ans = 0;
	int mid = (l + r) >> 1;
	down(i, mid - l + 1, r - mid);
	if(mid >=wol){
		ans += query(wol, wor, l, mid, i << 1);
	}
	if(mid + 1<= wor){
		ans += query(wol, wor, mid + 1, r, i << 1 | 1);
	}
	return ans;
}

// 范围i增加

void add(int wol, int wor, int wov, int l, int r, int i){
   	if(wol <=  l && r <= wor){
   		ad[i] += wov; // 往下传递
   		sum[i] += wov*(r - l + 1); 
   		return;
   	}
   	int mid = (l + r) >> 1;
   	down(i, mid - l + 1, r - mid);
   	if(wol <= mid){
   		add(wol, wor, wov, l, mid, i << 1);
   	}
   	if(wor >= mid + 1){
   		add(wol, wor, wov, mid + 1, r, i << 1 | 1);
   	}
   	sum[i] = sum[i << 1] + sum[i << 1 | 1];
}
signed main(){
       int n;
       cin >> n;
       for(int i = 1; i <= n; i++) cin >> a[i];
       build(1, n, 1);
       int q1;
       cin >> q1;
       while(q1--){
       	int l, r, v;
       	cin >> l >> r >> v;
       	add(l, r, v, 1, n, 1);
       }
       int q;
       cin >> q;
       while(q --){
       	int l, r;
       	cin >> l >> r;
       	cout << query(l, r, 1, n, 1) << endl;
       }
}

线段树的势能分析

线段树合并

处理 子串 子数组(相互连接) 的信息

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define fr first
#define sc second
using PII = pair<int, int>;

const int N = 1e5;

int a[N];
int sum[N << 2];
int tree0[N << 2];
int pre0[N << 2];
int la0[N << 2];
int tree1[N << 2];
int pre1[N << 2];
int la1[N << 2];
bool update[N << 2];
int up_data[N << 2];
bool reversed[N << 2];

void up(int i, int ln, int rn) {
    pre0[i] = (pre0[i << 1] == ln) ? (pre0[i << 1] + pre0[i << 1 | 1]) : pre0[i << 1];
    pre1[i] = (pre1[i << 1] == ln) ? (pre1[i << 1] + pre1[i << 1 | 1]) : pre1[i << 1];
    la0[i] = (pre0[i << 1 | 1] == rn) ? (la0[i << 1] + pre0[i << 1 | 1]) : la0[i << 1 | 1];
    la1[i] = (pre1[i << 1 | 1] == rn) ? (la1[i << 1] + pre1[i << 1 | 1]) : la1[i << 1 | 1];
    tree0[i] = max({tree0[i << 1], tree0[i << 1 | 1], la0[i << 1] + pre0[i << 1 | 1]});
    tree1[i] = max({tree1[i << 1], tree1[i << 1 | 1], la1[i << 1] + pre1[i << 1 | 1]});
    sum[i] = sum[i << 1] + sum[i << 1 | 1];
}

void build(int l, int r, int i) {
    reversed[i] = false;
    update[i] = false;
    if (l == r) {
        tree0[i] = (a[r] == 0) ? 1 : 0;
        tree1[i] = (a[r] == 1) ? 1 : 0;
        sum[i] = a[r];
        la0[i] = pre0[i] = tree0[i];
        la1[i] = pre1[i] = tree1[i];
        return;
    }
    int mid = (r + l) >> 1;
    build(l, mid, i << 1);
    build(mid + 1, r, (i << 1 | 1));
    up(i, mid - l + 1, r - mid);
}

void down(int i, int ln, int rn) {
    if (update[i]) {
        if (up_data[i] == 1) {
            pre1[i << 1] = la1[i << 1] = tree1[i << 1] = ln;
            pre0[i << 1] = la0[i << 1] = tree0[i << 1] = 0;
            pre1[i << 1 | 1] = la1[i << 1 | 1] = tree1[i << 1 | 1] = rn;
            pre0[i << 1 | 1] = la0[i << 1 | 1] = tree0[i << 1 | 1] = 0;
            sum[i << 1] = ln;
            sum[i << 1 | 1] = rn;
            update[i] = false;
            update[i << 1] = update[i << 1 | 1] = true;
            up_data[i << 1] = up_data[i << 1 | 1] = 1;
        } else {
            pre0[i << 1] = la0[i << 1] = tree0[i << 1] = ln;
            pre1[i << 1] = la1[i << 1] = tree1[i << 1] = 0;
            pre0[i << 1 | 1] = la0[i << 1 | 1] = tree0[i << 1 | 1] = rn;
            pre1[i << 1 | 1] = la1[i << 1 | 1] = tree1[i << 1 | 1] = 0;
            sum[i << 1] = 0;
            sum[i << 1 | 1] = 0;
            update[i] = false;
            update[i << 1] = update[i << 1 | 1] = true;
            up_data[i << 1] = up_data[i << 1 | 1] = 0;
        }
        reversed[i << 1] = reversed[i << 1 | 1] = false;
    }
    if (reversed[i]) {
        swap(pre1[i << 1], pre0[i << 1]);
        swap(la1[i << 1], la0[i << 1]);
        swap(tree0[i << 1], tree1[i << 1]);
        swap(pre1[i << 1 | 1], pre0[i << 1 | 1]);
        swap(la1[i << 1 | 1], la0[i << 1 | 1]);
        swap(tree0[i << 1 | 1], tree1[i << 1 | 1]);
        sum[i << 1] = ln - sum[i << 1];
        sum[i << 1 | 1] = rn - sum[i << 1 | 1];
        reversed[i << 1] = !reversed[i << 1];
        reversed[i << 1 | 1] = !reversed[i << 1 | 1];
        reversed[i] = false;
    }
}

void change(int jobl, int jobr, int w, int l, int r, int i) {
    if (jobl <= l && r <= jobr) {
        if (w == 0) {
            pre0[i] = la0[i] = tree0[i] = (r - l + 1);
            sum[i] = 0;
            pre1[i] = la1[i] = tree1[i] = 0;
            update[i] = true;
            up_data[i] = w;
        } else {
            pre1[i] = la1[i] = tree1[i] = (r - l + 1);
            sum[i] = (r - l + 1);
            pre0[i] = la0[i] = tree0[i] = 0;
            update[i] = true;
            up_data[i] = w;
        }
        reversed[i] = false;
        return;
    }
    int mid = (l + r) >> 1;
    down(i, mid - l + 1, r - mid);
    if (jobl <= mid) {
        change(jobl, jobr, w, l, mid, i << 1);
    }
    if (jobr >= mid + 1) {
        change(jobl, jobr, w, mid + 1, r, i << 1 | 1);
    }
    up(i, mid - l + 1, r - mid);
}

int query1(int jobl, int jobr, int l, int r, int i) {
    if (jobl <= l && r <= jobr) {
        return sum[i];
    }
    int ans = 0;
    int mid = (l + r) >> 1;
    down(i, mid - l + 1, r - mid);
    if (jobl <= mid) {
        ans += query1(jobl, jobr, l, mid, i << 1);
    }
    if (jobr >= mid + 1) {
        ans += query1(jobl, jobr, mid + 1, r, i << 1 | 1);
    }
    return ans;
}
//  返回 [l, r] 范围上 被 [jobl, jobr] 影响的区域 的 信息
vector<int> query2(int jobl, int jobr, int l, int r, int i) {
    if (jobl <= l && r <= jobr) {
        return {tree1[i], pre1[i], la1[i]};
    }
    int mid = (l + r) >> 1;
    down(i, mid - l + 1, r - mid);
    vector<int> a1 = {0, 0, 0};
    vector<int> a2 = {0, 0, 0};
    if (jobl <= mid) {
        a1 = query2(jobl, jobr, l, mid, i << 1);
    }
    if (jobr >= mid + 1) {
        a2 = query2(jobl, jobr, mid + 1, r, i << 1 | 1);
    }
    int max_len = max(a1[0], a2[0]);
    if (jobl <= mid && jobr >= mid + 1) {
        max_len = max(max_len, a1[2] + a2[1]);
    }
    int prefix_len = (jobl <= l) ? a1[1] : 0;
    /*
      [l, r]
      [jobl,jobr]
      返回 [l, r] 范围上 被 [jobl, jobr] 影响的区域 的 信息
    */
    if (jobl <= l && a1[1] == (mid - l + 1) && jobr >= mid + 1) {
        prefix_len += a2[1];
    }
    int suffix_len = (jobr >= r) ? a2[2] : 0;
    if (jobr >= r && a2[1] == (r - mid) && jobl <= mid) {
        suffix_len += a1[2];
    }
    return {max_len, prefix_len, suffix_len};
}

void reverse(int jobl, int jobr, int l, int r, int i) {
    if (jobl <= l && r <= jobr) {
        reversed[i] = !reversed[i];
        swap(pre1[i], pre0[i]);
        swap(la1[i], la0[i]);
        swap(tree0[i], tree1[i]);
        sum[i] = (r - l + 1) - sum[i];
        return;
    }
    int mid = (l + r) >> 1;
    down(i, mid - l + 1, r - mid);
    if (jobl <= mid) {
        reverse(jobl, jobr, l, mid, i << 1);
    }
    if (jobr >= mid + 1) {
        reverse(jobl, jobr, mid + 1, r, i << 1 | 1);
    }
    up(i, mid - l + 1, r - mid);
}

signed main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, n, 1);
    while (m--) {
        int pos, l, r;
        cin >> pos >> l >> r;
        l++; r++;
        if (pos == 0) {
            change(l, r, 0, 1, n, 1);
        } else if (pos == 1) {
            change(l, r, 1, 1, n, 1);
        } else if (pos == 2) {
            reverse(l, r, 1, n, 1);
        } else if (pos == 3) {
            cout << query1(l, r, 1, n, 1) << endl;
        } else if (pos == 4) {
            cout << query2(l, r, 1, n, 1)[0] << endl;
        }
    }
    return 0;
}


开点线段树

  1. 问题
  • 支持很大的范围，但是查询区间不需要这么大的范围

图论

数学

动态规划

计算几何

博弈论

杂项

最大公约数 和 最小公倍数 的关系

lcm(a, b) * gcd(a, b) = a * b

a * b = 质数 → (a = 1, b 为 质数)

alogrithm

http://example.com/2025/04/14/alogrithm/

作者

Jiely

发布于

2025-04-14

更新于

2025-04-17

许可协议

# 相关文章
  1.算法之美
  2.ACM集训题
  3.老算法笔记
  4.PYTHON 算法学习
评论

:D 一言句子获取中...

×