2025-05-06  /2025/05/06/alogrithm/ 99+   38 分钟   5.7 k0次访问

alogrithm

ALOGRITHM

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

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

基础算法

单调队列

[!NOTE]
这是一次尝试

单调栈

逆序对

  1. 树状数组

使用树状数组来求逆序队，主要要进行离散化，应为可以 a[i] 的值很大，但是 数组大小有限，不离散化的话，可能树状数组的 tree数组存不下。

思路：
从数组的右边开始便利，访问到当前元素的时候，检查树状数组中求和（比当前元素小的元素），因为是从右往左便利，如果有比当前元素小的，肯定在数组中是在当前元素的右边。

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int tree[N];
int lowbit(int i){
	return i & -i;
}
void add(int i, int w){
	while(i <= n){
		tree[i] += w;
		i += lowbit(i);
	}
}
// 1 - r
int sum(int r){
	int ans = 0;
	while(r > 0){
		ans += tree[r];
		r-= lowbit(r);
	}
	return ans;
}

signed main(){
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++)	cin >> a[i];
	// 离散化
    vector<int> b(n);
	b = a
	sort(b.begin(), b.end());
	map<int, int> mp;
	for(int i = 0; i < n; i++) mp[b[i]] = i + 1;
    // 求逆序队
	int ans = 0;
	for(int i = n - 1; i >= 0; i--){
		int r = sum(mp[a[i]] - 1);
		ans += r;
		add(mp[a[i]], 1);
	}
	cout << ans << endl;
	return 0;
}

归并分治

分治的含义是 整体的答案 $?=$ 左边的答案 + 右边的答案

  1. 归并排序

归并排序是一个稳定的排序

  • 整体的有序 是 左边有序 + 右边有序 + 合并过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void merge(int l, int r){
	int mid = (l + r) >> 1;
	int i = l, j = mid + 1, t1 = 0;
	while(i <= mid && j <= r){
		help[t1++] = (a[i] <= a[j]) ? a[i++] :a[j++];
	}
	while(i <= mid) help[t1++] = a[i++];
	while(j <= r) help[t1++] = a[j++];
	for(int i = r; i >= l; i--){
		a[i] = help[--t1];
	}
}

void guibin(int l, int r){
	if(l >= r) return;
	int mid = (l + r) >> 1;
	guibin(l, mid);
	guibin(mid + 1, r);
	merge(l, r);
}

分治题目：
leetcode-分治

随机快排

$$

$$

离散化

如果数据规模大，但是数据量小的话，我们可以进行离散化处理。

  • 给每一个值一个编号
  • 法一
1
2
3
4
5
6
vector<int> b(n);
b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
map<int, int> mp;
for(int i = 0; i < b.size(); i++){mp[b[i]] = i;}

类并查集

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

  • 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(_--) __();
    }

快速幂

无 mod

1
2
3
4
5
6
7
8
9
int fpw(int a, int b){
	int res = 1;
	while(b){
		if(b & 1) res *= a;
		a *= a;
		b >>= 1;
	}
	return res;
}

有mod

1
2
3
4
5
6
7
8
9
10
11
int fpw(int a, int b, int mod){
	int res = 1;
	while(b){
		if(b & 1){
			res = res * a % mod;
		}
		a = a * a % mod;
		b >>= 1;
	}
	return res % mod;
}

乘法逆元

线性

1
2
3
4
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}

扩展欧几里得

费马小

$$
ax \equiv 1(mod ; b) \
x = a^{b - 2}(mod ; b)
$$

1
x = fpw(a, b-2,b)

数据结构

折半搜索

OI WIKI - Meet in the middle

并查集

基础并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int father[N];
void init(){ for(int i = 0; i < N; i++) father[i] = i; }
int find(int x){
	if(x != father[x]){
		father[x] = find(father[x]);
	}
	return x;
}
void un(int x, int y){
	int fx = find(x), fy = find(y);
	if(fx != fy){
		father[fx] = fy;
	}
}

带权并查集

个人感觉带权并查集有点类似于 树形DP，后续补充

‘hello’

前缀和 + 差分

前缀和

一维

$$
sum[i] = sum[i - 1] + a[i]
$$

二维

$$
sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]
$$

树上前缀和

  • 点权

$$
x\rightarrow y 的路径 = sum_x + sum_y - sum_{lca} - sum_{f_{alca}}
$$

  • 边权

$$
x \rightarrow y 的路径 = sum_x + sum_y - 2 * sum_{lca}
$$

差分

用于快速解决区间修改问题

一维

$$
b_i = a_i - a_{i - 1}
$$

如果存在 [l, r] 区间内的值进行范围修改,在差分数组上面 $b_l + d,b_{r + 1} - d$

二维

$$
diff[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]
$$

$$
a[i][j] = \sum_{t1 = 1}^{i}\sum_{t2 = 1}^{j} diff[t1][t2]
$$

树上差分

  • 点差分

如查询一棵树上 节点被访问的次数

Ex: s 到 t 路径节点的访问修改
$$
d_s = d_s + 1 \
d_{lca} = d_{lca} - 1\
d_t = d_t + 1\
d_{f(lca)} = d_{f(lca)} - 1
$$
当前节点的权重,由于当前节点的权重与子节点有关，便可以很好的解释 上面这个差分访问修改
$$
a[i] = \sum^{i的子节点}diff[t]
$$

  • 边差分

Ex: s 到 t 路径的边的访问修改
$$
d_s = d_s + 1\
d_t = d_t + 1\
d_{lca} = d_{lca} - 1
$$
当前节点的权重,由于当前节点的权重与子节点有关，便可以很好的解释 上面这个差分访问修改
$$
a[i] = \sum^{i的子节点}diff[t]
$$

线段树

基础线段树

懒更新的意义是，如果这个大区间进行了修改，当访问到这个大区间的子区间时我们再去下发大区间的修改信息。

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

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. 问题
  • 支持很大的范围，但是查询次数少，查询区间小

时间复杂度 2 * m * log(n)，用 cnt 来记录编号，看节点分支是否访问过。

线段树历史最值操作

标签回收 → 进行剪枝

图论

最短路问题

遇见过很多 最短路 问题，题目的意思一般都指向明确，就是(i $\rightarrow$ j)的路径最小。

[!NOTE]
但是一般都是 最短路的扩展， ex：到达终点时候需要满足什么样的状态

题目链接：

  • 扩展迷宫问题

    个人认为这道题非常的典，题中还应用了一类 自定义点，来管理相同类别的点之间的跳转。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define endl '\n'
using PII = pair<int,int>;

void slove(){
int n, m, x;
cin >> n >> m >> x;
vector<int> a(n + 1, 0);
vector<array<int, 3>> g[2 * n + 1];
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
	g[a[i] + n].push_back({i,0,0});
	g[i].push_back({a[i] + n, x, 1 });
}
for(int i = 0; i < m; i++){
	int u, v, w;
	cin >> u >> v >> w;
	g[u].push_back({v,w,1});
}

priority_queue< array<int,3>, vector<array<int,3>>, greater<array<int,3>>> q;
q.push({0,1,0});
vector<vector<int>> dist(2 * n + 1, vector<int>(3, INT_MAX));
vector<vector<bool>> vis(2 * n + 1,vector<bool>(3,false));
dist[1][0] = 0;
while(!q.empty()){
	auto temp = q.top();
	q.pop();
	int v = temp[1],step = temp[2];
	if(vis[v][step]) continue;
	// cout << v << " " << w << endl;
	vis[v][step] = 1;
	for(auto[u, w, l] : g[v]){
	// cout << u << " " << w << endl;
	int op = (step + l) % 3;
	if(dist[u][op] > dist[v][step] + w){
		dist[u][op] = dist[v][step] + w;
		q.push({dist[u][op],u, op});}}
	}
	if(dist[n][0] == INT_MAX){
	cout << "-1" << endl;
	}else{
	cout << dist[n][0] << endl;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cout.tie(0);
	int t;
	cin >> t;
	while(t--) slove();
	return 0;
}

拓扑排序

适用于那些 节点状态有先后性的问题。

  • 如果需要求 最大/最小的拓扑排序的话，可以将存储的 deque 改成 优先队列
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
signed main(){
	int n;
	cin >> n;
	vector<vector<int>> a(n + 1);
	vector<int> in(n + 1);
	for(int i = 0; i < n; i++){
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		in[v]++;
	}
	deque<int> q;
	for(int i = 1; i <= n; i++){
		if(in[i] == 0){q.push_back(i);}
	}
	while(!q.empty()){
		int x = q.front(); q.pop_front();
		cout << x << endl;
		for(auto t : a[x]){
			in[t]--;
			if(in[t] == 0) q.push_back(t);
		}
	}
	return 0;
}

负环 差分约束

形式

  1. $$
    x_i - x_j \leq C_i \quad \text{($C_i$ 为常数)}\
    找到一组满足这种式子的解
    $$

根据 小于号 的不等式来建图

$$
x_i \leq x_j + C_i
$$

将这个式子应用到 图中,如果图中存在负环就不存在满足的解。

  • 负环判断： 如果这个节点进队列 $\geq$ 所有节点的 个数 - 1
  • 如果队列为空，dist[n] 便是一组解

数学

基础数论

  • 任何一个整数 都可以分解为 有限个质数的乘积

$$
N = p_1^{c_1} * p_2^{c_2} \dots p_x^{c_x}
$$

则 N 的约数集合为
$$
约数集合 = {p_1^{b_1} * p_2 ^ {b_2} \dots p_x^{b_x}} \
0\le b_i \le c_i
$$
正约数的个数 :$\prod_{i=1}^{m}{(c_i +1)}$

  • 质数筛的算法只需要 $log{(n)}$

高斯消元

高斯消元 有三种类别，我们会逐一补充，目前先补充 异或消元，但是其实本质是不变的。

线性基

给出一个数组，请找出这个 数组的任意元素进行异或，可以得到多少种情况。

线性基的大小便决定了 能异或的多少种情况 （2 ^ n - 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
#include<bits/stdc++.h>
using namespace std;

#define int long long 
#define fr first
#define sc second
#define endl '\n'
using PII = pair<int,int>;
/*
  线性基
*/
void _1(){
	int n;
	cin >> n;
	vector<int> a(n + 1, 0);
	for(int i = 1; i <= n; i++) cin >> a[i];
	/*
	  查找每一位的 基
	  首先 从 每一个数 开始遍历，然后枚举 每一个位置，如果这个位置有 基，将这个数 变成 两者的异或值
	*/
	int h = 61;
	bool zero = false;
	vector<int> ans;
	vector<int> base(h + 1, 0);
	for(int i = 1; i <= n; i++){
		for(int j = h; j >= 0; j--){
			if(((a[i] >> j) & 1) == 1){
				if(base[j] == 0){
					base[j] = a[i];
					ans.push_back(a[i]);
					break;
				}else a[i] = a[i] ^ base[j];
			}
			if(a[i] == 0) zero = true;
		}
	}
	
	for(auto x : ans) cout << x << " ";
	cout << endl;
	if(zero) cout << "yes" << endl;
	else cout << "no" << 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

void _2(){
	int n;
	cin >> n;
	vector<int> a(n + 1, 0);
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	int len = 1, h = 61; // 上面是确定的
	bool zero = false;
	vector<int> base(1,0);
	for(int i = h; i >= 0; i--){
		for(int j = len; j <= n; j++){
			if(((a[j] >> i) & 1) == 1){
				swap(a[len],a[j]);
				break;
			}
		}
		if(((a[len] >> i) & 1) == 1){ 
		for(int k = 1; k <= n; k++){
			if(k != len && ((a[k] >> i) & 1) == 1){
				a[k] = a[k] ^ a[len];
			}
		}
		len++;
		}
	}
	len --;
	if(len != n) zero = true;
	for(int i = 1; i <= len; i++) cout << a[i] << " ";
	cout << endl;
	if(zero) cout << "yes" << endl;
	else cout << "no" << 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
#include<bits/stdc++.h>
using namespace std;

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

signed main(){
	int n;
	cin >> n;
	vector<int> a(n + 1, 0);
	for(int i = 1; i <= n; i++) cin >> a[i];
	vector<int> base(53,0);
	for(int i = 1; i <= n; i++){
		for(int k = 52; k >= 0; k--){
			if(((a[i] >> k) & 1) == 1){
				if(base[k] == 0){
					base[k] = a[i];
					break;
				}else{
					a[i] ^= base[k];
				}
			}
		}
	}
	
	int mx = 0;
	for(int i = 52; i >= 0; i--){
		mx = max(mx, mx ^ base[i]);
	}
	cout << mx << endl;
	return 0;
}

求 异或 第 k 小值

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

#define int long long 
#define fr first
#define sc second
#define endl '\n'
using PII = pair<int,int>;
/*
  线性基
*/



signed main(){
	int n;
	cin >> n;
	vector<int> a(n + 1,0);
	for(int i = 1; i <= n; i++) cin >> a[i];
	auto swp = [&](int i, int j) -> void{
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
	};
	int len = 1;
	for(int i = 53; i >= 0; i--){
		for(int j = len; j <= n; j++){
			if(((a[j] >> i) & 1) == 1){
				swp(j, len);
				break;
			}
		}
		if(((a[len] >> i) & 1) == 1){
		for(int j = 1; j <= n; j++){
			if(j != len && (((a[j] >> i) & 1) == 1)){
				a[j] ^= a[len];
			}
		}
		len ++;
	}
	}
	len --;
	// for(int i = 1; i <= len; i++) cout << a[i] << " ";
	// cout << endl;
	bool zero = (len != n);
	int m;
	cin >> m;
	int mx = (1 << len);
	// cout << mx << endl;
	for(int i = 0; i < m; i++){
		int t;
		cin >> t;
		if(zero) t--;
		if(t == 0 && zero) cout << "0" << "\n";
		else if(t == 0 || t >= mx) cout << "-1" << "\n";
		else{
			int ans = 0;
			// cout << t << endl;
			for (int i = len, j = 0; i >= 1; i--, j++) {
			if ((t & (1L << j)) != 0) {
				ans ^= a[i];
			}
		}
			cout << ans << "\n";
			// cout << endl;
		}
		
	}
	return 0;
}

扩展欧几里得

中国剩余定理

由扩展欧几里得算法（后续填完扩展欧几里得会补充）

动态规划

区间DP

当实现 区间DP 的时候，如何将递归该迭代

  1. 首先枚举每一个长度的区间，然后在枚举每一个区间的开头（这样可以避免判断边界条件），然后判断这个区间的扩展，因为当你枚举到这个长度的区间的时候，你是一定枚举完这个区间的子区间的。
  2. 注意 子区间中存在一些特判的情况！

计算几何

博弈论

杂项

数据

通过数据量的给出，可以大概的估计是一个什么时间复杂度的算法，从而来推演这个算法的类型。

或( | ) 和 与( & )

对于或和与的一些讨论

  • 或 是只要有一个 1，或值 中这个位置就一定会存在一个 1

可以考虑 这个位置的 一是否需要存在来进行按位判断

  • 与 是需要全部都是1，与值 中这个位置就一定存在 1

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

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

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

  • 在进行 GCD 的过程中，随着 不断进行 GCD，GCD的值只可能不变或者变小

异或值

  1. 遇到异或值可以考虑 枚举每一个位置，看是不是每一个位置的变化会对答案有影响（规律性）

2094E

二进制

  • 在二进制的位移中 1是会被默认当作 (int)类型的

需要 (1ll << j) 防止溢出

如 （1 << j) 会被默认为 int 类型

图的创新知识

  • 存在多个 起点的时候，可以设置虚点。
  • 遇到中位数（对顶堆）
  • 树上的 两个节点之间 只存在一条最短路径

二分

  • 二分是 x 值成立 $\leq or \geq$ x 的值都成立
  • 二分具有单调性：
  • 当 x 成立的 时候， 小于 x 的值都是一定成立的。

对于数组中 不同位置的值 能否相互抵消，变成全是 0 的数组

如果当前 元素的个数大于了 数组的和的一半肯定是不成立的

区间异或问题

对于一个区间 [l, r] 来说, l ^ r 中的 最高位的 1，相当于 最高位后面的 1都可以由 [l, r] 中的值异或得到。

1

在计算机中会自动被默认设置为 int 型，所以如果有long long 的话，需要 改变 1 的类型, (long long)

矩阵问题

矩阵 行列异或

矩阵构造

  • 通用思考：找一下 总的异或 的值的关系
  • 尝试去构造矩阵

alogrithm

http://example.com/2025/05/06/alogrithm/

作者

Jiely

发布于

2025-05-06

更新于

2025-05-21

许可协议

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

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

×