本文实际上是我于2022/7/29补写的
分治
逆序对(洛谷P1908)
我们直接打暴力，枚举每一个树a[i],在a[1~n]直接寻找比a[i]小的数即可。
但是这样很明显不能通过本题，他的时间复杂度是$O(n^{2})$
我们可以用线段树维护权值数组来加速，但是今天的重点是分治。
我们可以观察到，对于逆序对(x,y),只有3种情况:
所以我们能实现一个函数 calc(l, r)：
- 调用 calc(l, mid) 获得左边块内的逆序对个数
- 调用 calc(mid, r) 获得右边块内的逆袭对个数
- 亲自去统计跨块的逆序对个数
即为在归并的过程中统计个数。
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
| #include <bits/stdc++.h>
using namespace std;
int a[500005], n;
void input() {
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
}
long long ans;
void calc(int l, int r) {
if(l == r - 1)
return;
int mid = (l + r) / 2;
calc(l, mid);
calc(mid, r);
for(int x=l; x<mid; x++)
for(int y=mid; y<r; y++)
if(a[x] > a[y]) ans++;
}
void work() {
calc(0, n);
printf("%lld\n", ans);
}
int main() {
input();
work();
return 0;
}
|
但是我们用Master定理一算,嗯？还是$O(n^{2})$啊！
实现一个函数 calc(l, r)：
- 调用 calc(l, mid)
- 调用 calc(mid, r)
- 将左边、右边的块排序
- O(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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <bits/stdc++.h>
using namespace std;
int a[500005], n;
void input() {
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
}
long long ans;
int tmp[500005];
void calc(int l, int r) {
if(l == r - 1)
return;
int mid = (l + r) / 2;
calc(l, mid);
calc(mid, r);
int y = mid;
for(int x=l; x<mid; x++) {
while(y < r && a[y] < a[x]) y++;
ans += y - mid;
}
int p=l, q=mid, cur=l;
while(p < mid && q < r){
if(a[p] < a[q])
tmp[cur++] = a[p++];
else
tmp[cur++] = a[q++];
}
while(p < mid)
tmp[cur++] = a[p++];
while(q < r)
tmp[cur++] = a[q++];
for(int i=l; i<r; i++)
a[i] = tmp[i];
}
void work() {
calc(0, n);
printf("%lld\n", ans);
}
int main() {
input();
work();
return 0;
}
|
省了2个sort，就降下来了时间复杂度:
快速幂
因为取模可以在运算过程中取，所以我们可以不爆空间。
计算 $x_{a} mod p$ 时，分两种情况：
1
2
3
4
5
6
7
8
9
10
11
| ll quickPow(ll a, ll x, ll p) {
if(x == 0) return 1;
if(x == 1) return a % p;
ll tmp = quickPow(a, x/2, p);
if(x % 2 == 0)
return tmp * tmp % p;
else
return tmp * tmp % p * a % p;
}
|
二分
平方根
题目描述
求$\sqrt n$ 的整数部分。
输入格式
仅一行，一个正整数，表示$n$。
输出格式
仅一行，一个正整数，表示$\lfloor \sqrt n\rfloor $。
样例 #1
样例输入 #1
样例输出 #1
提示
对于$100\%$的数据，$n\lfloor 10^{18}\rfloor$。
可以转换为求最大的x使$x^{2}\leq n$
暴力
可以直接暴力
1
2
| for(ll i=1;i*i<=n;i++);
printf("%lld",x-1);
|
但是x达到了$1^{18}$级别，无法通过本题。
二分
我们可以通过猜来解决问题。猜一个数x如果$x^{2}$大于n就说明我们猜大了，如果小于就说明猜小了。
在1~1e9猜数即可:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void work() {
ll l = 0, r = 1000000000;
while(r - l > 5) {
ll mid = (l + r) / 2;
if(mid * mid > n)
r = mid - 1;
else
l = mid;
}
for(ll x=r; x>=l; x--)
if(x * x <= n) {
cout << x << endl;
return;
}
}
|
可能会有人问：“嗯？你这个二分怎么和一般的二分不一样？”
因为这样好写，不容易写炸。如果写“学院派”二分可能不小心就写炸了。
这样写之比“学院派”二分慢一点点，称为”通用二分“。
我们缩小到5个后逐个判断。
可二分性
如果你可以快速判断一个答案是否满足要求，那就满足可二分性，可以尝试二分求解。
区间和(前缀和)
今有 n 个同学，学号为 1 ∼ n。给出每个人的语文成绩。 需要处理 m 次询问，每次询问给定 l, r，查询学号在 [l, r] 范围内的学生的成绩
sum。
即给定一个数组，多次查询区间和。
如果采用分块，每次查询代价是 $O(\sqrt n)$，总复杂度 $O(m\sqrt n)$
那么我们可以弄一个pre数组,来储存1~k的和，求i~k的和即为pre[k]-pre[i] 真是方便呢！
这个pre数组便被成为前缀和。
所以前缀和实际上也不是个很高级的东西。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void init() {
for(int i=1; i<=n; i++)
pre[i] = pre[i-1] + a[i];
}
int getSum(int l, int r) {
return pre[r] - pre[l-1];
}
|
仅适用于数组固定，如果是动态(插入+查询)的那种就不能使用。
我们需要使用 O(n) 的时间预处理出 pre 数组。 接下来每个询问可以 O(1) 回答。
复杂度在 OI 中简记为 O(n) −O(1)，即 O(n) 预处理，每次查询 O(1)。
差分
差分 可以用来解决多次区间加，最终求整个数组 的问题。 我们采用 d[x] 记录a 。 那么，[l, r] 区间加 k 可以表示为： - d[l] += k - d[r+1] -= k 最后扫一遍 d 数组即可还原 a[]。1
2
| a={0,0,+1,0,0,0,-1,0,0};
pre={0,0,1,1,1,1,0,0};
|
这样即可实现区间加/减。
不用直接给数组加减，我们只需维护差分数组即可。
前缀和和查询何为逆运算。
想要给1~3加1，只需要给差分数组的[1]+1,[3]-1即可。
在所有的都做完差分后做一次差分即可$O(n)$完成运算。
浇花
题目描述
今有 $n$ 盆花摆成一排，编号为 $1\sim n$。
机器猫一时兴起，就会去浇花。机器猫每次浇花，是选择一个区间 $[l, r]$，给这个区间内的花浇水。
机器猫一共浇了 $m$ 次水。我们想知道，每盆花被浇了多少次。
输入格式
第一行，两个正整数 $n, m$。
接下来 $m$ 行，每行两个正整数 $l, r$，表示一次浇花。
输出格式
仅一行，$n$ 个整数，表示每盆花被浇了多少次。
样例 #1
样例输入 #1
样例输出 #1
提示
对于 $100\%$ 的数据，$n, m\leq 100000$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void add(int l, int r) {
d[l] += 1;
d[r+1] += -1;
}
void work() {
while(m--) {
int l, r;
cin >> l >> r;
add(l, r);
}
for(int i=1; i<=n; i++)
a[i] = a[i-1] + d[i];
for(int i=1; i<=n; i++)
cout << a[i] << ' ';
}
|
差分是不是非常的有意思和强大呢？对于固定的修改可以很方便的操作。
差分与前缀和
差分可以应对多次输入区间加，最后输出整个序列的问题。
差分的缺陷是不能中途询问，因为中途查询的复杂的是O(n)的。
差分与前缀和是两个极端，一个中途不能改，一个中途不能查。
- 差分可以O(1)改，O(n)查询。
- 前缀和可以O(n)预处理，O(1)查询
（线段树可以中途改和查且复杂的为O(nlogn)
Two-pointers
$eg_1$：
最短区间
题目描述
给定长度为 $n$ 的序列 $a$ ，以及一个正整数 $s$。
要寻找最短的区间，使区间 sum $\geq s$。
输出最短区间的长度。
输入格式
第一行，两个正整数$n, s$。
接下来一行，$n$ 个正整数，表示序列 $a$。
输出格式
仅一行，一个正整数，表最短合法区间的长度。
样例 #1
样例输入 #1
样例输出 #1
样例 #2
样例输入 #2
样例输出 #2
提示
对于 $40\%$ 的数据，$n \leq 1000$。
对于 $100\%$ 的数据，$n\leq 100000, 1\leq a_i \leq 10000$。
我们可以想到直接$O(n^{2})$暴力，但是文明人都不会暴力。所以我们想到了二分，可以$O(nlogn)$解决。枚举l二分r。
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
| #include <bits/stdc++.h>
using namespace std;
int n, s;
int a[100005];
void input() {
cin >> n >> s;
for(int i=1; i<=n; i++)
cin >> a[i];
}
int pre[100005];
void init() {
for(int i=1; i<=n; i++)
pre[i] = pre[i-1] + a[i];
}
int getSum(int l, int r) {
return pre[r] - pre[l-1];
}
int findRight(int begin) {
int l = begin, r = n;
while(r - l > 5) {
int mid = (l + r) / 2;
if(getSum(begin, mid) <= s)
l = mid;
else
r = mid;
}
for(int x=l; x<=r; x++)
if(getSum(begin, x) >= s)
return x;
return 23333333;
}
void work() {
int ans = 23333333;
for(int l=1; l<=n; l++) {
int r = findRight(l);
ans = min(ans, r - l + 1);
}
cout << ans << endl;
}
int main() {
input();
init();
work();
return 0;
}
|
但是其实这道题有线性($O(1)$)的做法.
定义指针l和r，一开始都指向1，如果cursum<s就将r向右移，直到cursum>=s为止，统计答案，再将l向右移。
这就是Two-pointers算法。
因为总体只移动了n次，所以时间复杂度为$O(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
| #include <bits/stdc++.h>
using namespace std;
int n, s;
int a[100005];
void input() {
cin >> n >> s;
for(int i=1; i<=n; i++)
cin >> a[i];
}
void work() {
int l = 1, r = 1, curSum = a[1];
int ans = 23333333;
while(l <= n) {
while(r <= n && curSum < s) {
r++;
curSum += a[r];
}
if(curSum >= s)
ans = min(ans, r-l+1);
curSum -= a[l];
l++;
}
cout << ans << endl;
}
int main() {
input();
work();
return 0;
}
|
This article was written on 2022/8/5
