第二讲二分和前缀和
- 第一节二分
- 第二节前缀和

第二讲二分和前缀和

第二讲二分和前缀和
- 第一节二分
- 第二节前缀和

第一节二分

要点：

确定一个区间，使得目标值一定在区间中。
找一个性质，满足：
1. 性质具有二段性（一段满足、一段不满足）
2. 答案是二段性的分界点。

整数二分

2二分和前缀和 - 图1

第一类：ans是红色区间的右端点。

将[L,R]分成[L,M-1]，[M+1,R]

if M是红色的，说明答案必然在[M,R]

else 说明ans必然在[L,M-1]

2二分和前缀和 - 图2

第二类：ans是绿色区间的左端点。

将[l,R]分成[L,M]和[M+1,R]

if M是绿色，说明ans在[L,M]

else 说明ans在[M+1,R]

2二分和前缀和 - 图3

总结：

2二分和前缀和 - 图4

实数划分

2二分和前缀和 - 图5

将区间[L,R]划分成[L,M],[M,R]

2二分和前缀和 - 图6

例题1：数的范围

https://www.acwing.com/problem/content/791/

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。如果数组中不存在该元素，则返回“-1”。

输入格式
第一行包含整数n和q，表示数组长度和询问个数。第二行包含n个整数（均在1~10000范围内），表示完整数组。接下来q行，每行包含一个整数k，表示一个询问元素。

输出格式
共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。如果数组中不存在该元素，则返回“-1”。

数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000

输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1

/*
使用二分法，先找左端点
再找右端点
1≤n≤100000
1≤q≤10000
1≤k≤10000
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[100010];
int main() {
    int n,q;//数组长度、询问个数 
    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < q; i++) {
        //一个个处理
        int x;//待查找的数 
        cin >> x;
        //二分找左端点 
        int l = 0;
        int r = n - 1;
        while(l < r) { // 要找到与x相等的最左边的那个 
            int mid = (l+r)/2;    //mid向下取 
            if(a[mid] >= x) r = mid;//如果中间的数比x大或相等，右端点移过来 
            else l = mid + 1;//否则左端点移到mid + 1的位置
        }
        //因为有找不到的可能，所以先判断一下 
        if(a[l] == x) {
            cout << l << " ";//将左端点的下标输出,l和r相等，随便输出哪个 
            //二分找右端点,l保持不动，r移到n-1，然后收缩 
            r = n - 1;
            while(l < r) {
                int mid = (l+r+1)/2; //mid向上取整，所以+1 
                if(a[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;//将右端点的下标输出,l和r相等，随便输出哪个
        }else {
            cout << -1 << -1 << endl; 
        }
    }
    return 0;
}

例题2：数的三次方根

https://www.acwing.com/problem/content/792/

给定一个浮点数n，求它的三次方根。

输入格式
共一行，包含一个浮点数n。

输出格式
共一行，包含一个浮点数，表示问题的解。注意，结果保留6位小数。

数据范围
−10000≤n≤10000

输入样例：
1000.00
输出样例：
10.000000

/*
10000≤n≤10000
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    double n;
    cin >> n;
    double l = -10000.0;
    double r = 10000.0;
    while(r - l >= 1e-8) {//保留6位小数，多取2位保证精度够高 
        double mid = (l+r)/2;
        if(mid*mid*mid >= n) r = mid;//mid太大，缩小mid 
        else l = mid;//mid太小，放大mid 
    }
    printf("%lf",l);
    return 0;
}

作业1：机器人跳跃问题

https://www.acwing.com/problem/content/732/

机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号，从左到右排列。编号为0的建筑高度为0个单位，编号为 i 的建筑高度为H(i)个单位。起初，机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E，下一步它将跳到第k+1个建筑。如果H(k+1)>E，那么机器人就失去H(k+1)-E的能量值，否则它将得到E-H(k+1)的能量值。游戏目标是到达第N个建筑，在这个过程中能量值不能为负数个单位。现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式
第一行输入整数N。第二行是N个空格分隔的整数，H(1),H(2),…,H(N)代表建筑物的高度。

输出格式
输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。

数据范围
1≤N,H(i)≤105

输入样例1：
5
3 4 3 2 4
输出样例1：
4
输入样例2：
3
4 4 4
输出样例2：
4
输入样例3：
3
1 6 4
输出样例3：
3

/*
注意加到溢出 
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[100010];
int n;
//输入初始能量值，判断是否全程>=0 
bool check(int e){
    for(int i = 0; i < n; i++) {
        e = 2*e-a[i+1];
        if(e >= 1e5)return true;
        if(e < 0) return false;
    }
    return true;
}
int main() {
    cin >> n;
    a[0] = 0;//第0个高度为0 
    for(int i = 1; i <= n; i++) cin >> a[i];    //第i个高度为a[i]; 
    int l = 0, r = 1e5;
    while(l < r) {
        int mid = (l+r)/2;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}

作业2：四平方和

https://www.acwing.com/problem/content/1223/

四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多 4 个正整数的平方和。如果把 0 包括进去，就正好可以表示为 4个数的平方和。比如： 5=02+02+12+22
7=12+12+12+22 对于一个给定的正整数，可能存在多种平方和的表示法。要求你对 4 个数排序： 0≤a≤b≤c≤d 并对所有的可能表示法按 a,b,c,d为联合主键升序排列，最后输出第一个表示法。

输入格式
输入一个正整数 N。

输出格式
输出4个非负整数，按从小到大排序，中间用空格分开。

数据范围
0

输入样例：
5
输出样例：
0 0 1 2

/*
0<N<5*10^6（5e6）
sqrt(5000000)约等于2236 
思路：枚举cd，存起来，枚举ab，用二分查找判断一下 
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2500010;
struct TB{
    int num,c,d;
};
TB table[N];
int cnt; 
bool cmp(TB a,TB b) {
    if(a.num != b.num) return a.num < b.num;
    if(a.c != b.c) return a.c < b.c;
    return a.d < b.d;
}
//在表中找t，返回c和d
bool myfind(int t, int& c, int& d){
    int l = 0, r = cnt-1;
    while(l < r) {
        int mid = l + r >> 1;
        if(table[mid].num >= t) r = mid;
        else l = mid + 1;
    }
    if(table[l].num == t) {
        c = table[l].c;
        d = table[l].d;
        return true;
    }
    return false;
} 
int main() {
    int n;
    cin >> n;
    for(int c = 0; c*c <= n; c++) {
        for(int d = c; c*c + d*d <= n; d++) {
            table[cnt++] = {c*c+d*d,c,d};
        }
    }
    sort(table,table+cnt,cmp);
    for(int a = 0; a*a <= n; a++) {
        for(int b = a; a*a + b*b <= n; b++) {
            int t = n - (a*a + b*b);
            int c = 0,d = 0;
            if(myfind(t,c,d)) {
                printf("%d %d %d %d",a,b,c,d);
                return 0;
            }
        }
    }
    return 0;
}

作业3：分巧克力

https://www.acwing.com/problem/content/1229/

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N 块巧克力，其中第 ii 块是 Hi×Wi 的方格组成的长方形。为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：

形状是正方形，边长是整数
大小相同

例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入格式
第一行包含两个整数 N 和 K。以下 N 行每行包含两个整数 Hi 和 Wi。输入保证每位小朋友至少能获得一块 1×1 的巧克力。

输出格式
输出切出的正方形巧克力最大可能的边长。

数据范围
1≤N,K≤105
1≤Hi,Wi≤105

输入样例：
2 10
6 5
5 6
输出样例：
2

/*
边长越长，分的块数越少
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
struct QKL{
    int h,w;
};
int n,k;
QKL a[N];
//算变长为x分下来是否满足k个小朋友 
bool check(int x) {
    int sum = 0;
    for(int i = 0; i < n; i++){
        sum += (a[i].h/x) * (a[i].w/x);
        if(sum >= k) return true;
    }
    return false;
}
int main() {
    cin >> n >> k;//n个巧克力，k个小朋友
    for(int i = 0; i < n; i++) {
        cin >> a[i].h >> a[i].w;
    }
    int l = 1, r = 1e5;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;//块数大于人数，放大变长，缩小块数 
        else r = mid - 1;
    }
    cout << l << endl;
    return 0;
}

第二节前缀和

2二分和前缀和 - 图7 、

一维前缀和：

用一个数组S，让Si = a1 + a2 + … + ai。也就是存着前i个的元素和。

例题1：前缀和

https://www.acwing.com/problem/content/797/

输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。

输入格式
第一行包含两个整数n和m。第二行包含n个整数，表示整数数列。接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。

输出格式
共m行，每行输出一个询问的结果。

数据范围
1≤l≤r≤n
1≤n,m≤100000
−1000≤数列中元素的值≤1000−1000≤数列中元素的值≤1000

输入样例：
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例：
3
6
10

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int m,n;
int a[N];   //表示原数组
int s[N];   //表示前缀和数组
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    while(m--) {
        int l,r;
        cin >> l >> r;
        cout << s[r] - s[l-1] << endl;
    }
    return 0;
}

例题2：子矩阵的和

https://www.acwing.com/problem/content/798/

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

输入格式
第一行包含三个整数n，m，q。接下来n行，每行包含m个整数，表示整数矩阵。接下来q行，每行包含四个整数x1, y1, x2, y2，表示一组询问。

输出格式
共q行，每行输出一个询问的结果。

数据范围
1≤n,m≤1000
1≤q≤200000
1≤x1≤x2≤n
1≤y1≤y2≤m
−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000

输入样例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21

2二分和前缀和 - 图8

2二分和前缀和 - 图9

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m,q;
int a[N][N],s[N][N];
int main() {
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <=m; j++){
            scanf("%d",&a[i][j]);
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
        }
    }
    while(q--) {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]);
    }
    return 0;
}

作业1：激光炸弹

https://www.acwing.com/problem/content/101/

地图上有 N 个目标，用整数Xi,YiXi,Yi表示目标在地图上的位置，每个目标都有一个价值WiWi。注意：不同目标可能在同一位置。现在有一种新型的激光炸弹，可以摧毁一个包含 R×R 个位置的正方形内的所有目标。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和x，y轴平行。求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式
第一行输入正整数 N 和 R ,分别代表地图上的目标数目和正方形的边长，数据用空格隔开。接下来N行，每行输入一组数据，每组数据包括三个整数Xi,Yi,Wi分别代表目标的x坐标，y坐标和价值，数据用空格隔开。

输出格式
输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围
0≤R≤109
00≤Xi,Yi≤5000
0≤Wi≤1000

输入样例：
2 1
0 0 1
1 1 1
输出样例：
1

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 5010;
int s[N][N];
int mx, my, mval;
int main() {
    int n, r;
    cin >> n >> r;    //n个目标，轰炸边长为r
    r = min(5001, r);    //r最大取到5001，不然会有数组边界问题。
    mx = my = r;    //如果所有的目标都小于r，那么最大值为r，不然会有边界问题。
    for (int i = 0; i < n; i++) {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        x++, y++;
        s[x][y] += w;    //注意这里是+=，不同目标可能在同一位置
        mx = max(mx, x);
        my = max(my, y);
    }
    //预处理前缀和
    for (int x = 1; x <= mx; x++) {
        for (int y = 1; y <= my; y++) {
            s[x][y] += s[x - 1][y] + s[x][y - 1] - s[x - 1][y - 1];
        }
    }
    for (int x1 = 1; x1 <= mx; x1++) {
        for (int y1 = 1; y1 <= my; y1++) {
            int x2 = x1 + (r - 1);
            int y2 = y1 + (r - 1);
            if (x2 > mx || y2 > my)continue;
            int val = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
            mval = max(mval, val);
        }
    }
    cout << mval << endl;
    return 0;
}

作业2：K倍区间

https://www.acwing.com/problem/content/1232/

给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j] 是K 倍区间。你能求出数列中总共有多少个 K 倍区间吗？

输入格式
第一行包含两个整数 N 和 K。以下 N 行每行包含一个整数 Ai。

输出格式
输出一个整数，代表 K 倍区间的数目。

数据范围
1≤N,K≤100000
1≤Ai≤100000

输入样例：
5 2
1
2
3
4
5
输出样例：
6

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
LL a[N], cnt[N];
int main() {
    int n, k;
    LL ans = 0;
    cin >> n >> k;    // 数列长度为n，k倍区间
    //输入序列并预处理前缀和
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[i] += a[i - 1];
    }
    cnt[0] = 1;
    for (int i = 1; i <= n; i++) {
        ans += cnt[a[i] % k];
        cnt[a[i] % k]++;
    }
    //输出答案
    cout << ans << endl;
    return 0;
}

2二分和前缀和

第二讲 二分和前缀和

第一节 二分

整数二分

实数划分

例题1：数的范围

输入格式

输出格式

数据范围

输入样例：

输出样例：

例题2：数的三次方根

输入格式

输出格式

数据范围

输入样例：

输出样例：

作业1：机器人跳跃问题

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

输入样例3：

输出样例3：

作业2：四平方和

输入格式

输出格式

数据范围

输入样例：

输出样例：

作业3：分巧克力

输入格式

输出格式

数据范围

输入样例：

输出样例：

第二节 前缀和

例题1：前缀和

输入格式

输出格式

数据范围

输入样例：

输出样例：

例题2：子矩阵的和

输入格式

输出格式

数据范围

输入样例：

输出样例：

作业1：激光炸弹

输入格式

输出格式

数据范围

输入样例：

输出样例：

作业2：K倍区间

输入格式

输出格式

数据范围

输入样例：

输出样例：

第二讲二分和前缀和

第一节二分

第二节前缀和