二分和前缀和笔记

二分模板

二分模板一共有两个,分别适用于不同情况。
算法思路:假设目标值在闭区间[l, r]中, 每次将区间长度缩小一半,当l = r时,我们就找到了目标值。

版本1

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时,其更新操作是r = mid或者l = mid + 1;,计算mid时不需要加1。

1
2
3
4
5
6
7
8
9
10
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}

版本2

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时,其更新操作是r = mid - 1或者l = mid;,此时为了防止死循环,计算mid时需要加1。

1
2
3
4
5
6
7
8
9
10
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}

递增三元组

给定三个整数数组

$A = [A_1, A_2, …, A_N]$,
$B = [B_1, B_2, …, B_N]$,
$C = [C_1, C_2, …, C_N]$,

请你统计有多少个三元组 $(i, j, k)$ 满足:

  1. $1 \leq i, j, k \leq N$
  2. $A_i < B_j < C_k$

输入格式

  • 第一行包含一个整数 $N$。
  • 第二行包含 $N$ 个整数 $A_1, A_2, …, A_N$。
  • 第三行包含 $N$ 个整数 $B_1, B_2, …, B_N$。
  • 第四行包含 $N$ 个整数 $C_1, C_2, …, C_N$。

输出格式

一个整数表示答案。

数据范围

$1 \leq N \leq 10^5$,
$0 \leq A_i, B_i, C_i \leq 10^5$

输入样例:

3
1 1 1
2 2 2
3 3 3

输出样例:

27

分析

关键在于:求一个数组中(A)有几个数小于B[i]。可用排序加2分,前缀和。

前缀和做法:

假设有一个数组a{3,1,3,2,5} 假设求比 3 小的个数。设一个数组b, b[a[i]]++, 则b{1,1,2,0,1},再设数组c为数组b的前缀和, c{1,2,4,4,5}, 比 3 小的数的个数为:b[0]+b[1], 即c[1]=2。

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<iostream>
using namespace std;

int n;
const int N = 100010;
int a[3][N];
int b1[N];
int b2[N];
int c1[N];
int c2[N];
long long res;

int main() {
cin >> n;
for (int i = 0; i < 3; i++) {
for (int j = 1; j <= n; j++)
cin >> a[i][j];
}

for (int i = 1; i <= n; i++) {
b1[a[0][i]]++;
b2[a[2][i]]++;
}
c1[0] = b1[0];
c2[0] = b2[0];
for (int i = 1; i <=N-1; i++) {
c1[i] = b1[i] + c1[i - 1];
c2[i] = b2[i] + c2[i - 1];
}

for (int i = 1; i <= n; i++) {
int temp=a[1][i];
//这个地方卡了好久,不加long long过不了:在这个特定的例子中,
// 假设 c1 和 c2 是整数数组,temp 和 N 是整数变量,res 是一个 long long
// c1 和 c2 中的元素是 int 类型,而 res 是 long long 类型,那么进行乘法运算时,
// 可能需要将 int 类型的乘积累极转换为 long long 类型,
// 以避免可能的整数溢出或者确保结果的准确性。
res += (long long)c1[temp - 1] * (c2[N-1]-c2[temp]);
}

cout << res;
return 0;
}

二分做法:

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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 1e5+10;
int num[3][N];

int main() {
int n;
scanf("%d", &n);
for(int i = 0; i < 3; ++i)
for(int j = 1; j <= n; ++j)
scanf("%d", &num[i][j]);
for(int i = 0; i < 3; ++i)
sort(num[i]+1, num[i]+n+1);

LL ans = 0;
//枚举B,寻找A满足的个数以及C满足的个数相乘
for(int i = 1; i <= n; ++i) {
int key = num[1][i];
//A中二分查找第一个小于key的数的下标
int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
//C中二分查找第一个大于key的数的下标
int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
if(pos1 >= 1 && pos2 <= n) {
ans += (LL)pos1*(n-pos2+1);
}
}
cout<<ans<<endl;
return 0;
}


二分和前缀和笔记
http://example.com/2024/03/05/二分和前缀和笔记/
作者
邓骏韬
发布于
2024年3月5日
许可协议