二分和前缀和笔记

二分模板

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

版本1

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

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。

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。

#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;
}

二分做法：

#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;
}