2025CSP-J 冲刺训练(3)：前缀和差分

一、基础知识

1. 前缀和

前缀和（又叫积分）：在一个数字组成的序列中从位置 $1$ 到位置 $n$ 这个区间内的所有数字之和。

例如：

${\mathtt{a}}_{\mathtt{i}}$	1	2	3	4	5	6	7	8
$\mathtt{pf}{\mathtt{x}}_{\mathtt{i}}$	1	3	6	10	15	21	28	36

前缀和可以大大提高查询区间和的时间复杂度。如果按照普通的 for 循环，时间复杂度为 $O(r-l+1)$，使用前缀和后套用公式 $\mathtt{pf}{\mathtt{x}}_{\mathtt{r}}-\mathtt{pf}{\mathtt{x}}_{\mathtt{l}-1}$，就可以直接用 $O(1)$ 的时间复杂度获得答案。

2. 差分

差分：求相邻两个元素的差值并存储，也是前缀和的逆运算。

例如：

${\mathtt{a}}_{\mathtt{i}}$	1	3	6	10	15	21	28	36
$\mathtt{dif}{\mathtt{f}}_{\mathtt{i}}$	1	2	3	4	5	6	7	8

3. 公式

3.1 一维

3.2 二维

二维前缀和：$$\mathtt{pf}{\mathtt{x}}_{\mathtt{i},\mathtt{j}}=\mathtt{pf}{\mathtt{x}}_{\mathtt{i}-1,\mathtt{j}}+\mathtt{pf}{\mathtt{x}}_{\mathtt{i},\mathtt{j}-1}-\mathtt{pf}{\mathtt{x}}_{\mathtt{i}-1,\mathtt{j}-1}+{\mathtt{a}}_{\mathtt{i},\mathtt{j}}$$
二维区间和：$$\mathtt{pf}{\mathtt{x}}_{{\mathtt{x}}_2,{\mathtt{y}}_2}-\mathtt{pf}{\mathtt{x}}_{{\mathtt{x}}_1-1,{\mathtt{y}}_2}-\mathtt{pf}{\mathtt{x}}_{{\mathtt{x}}_2,{\mathtt{y}}_1-1}+\mathtt{pf}{\mathtt{x}}_{{\mathtt{x}}_1-1,{\mathtt{y}}_1-1}$$

---

二维差分区间范围统一+1：$$\mathtt{dif}{\mathtt{f}}_{{\mathtt{x}}_1,{\mathtt{y}}_1}+1,\mathtt{dif}{\mathtt{f}}_{{\mathtt{x}}_1,{\mathtt{y}}_2+1}-1,\mathtt{dif}{\mathtt{f}}_{{\mathtt{x}}_2+1,{\mathtt{y}}_1}-1,\mathtt{dif}{\mathtt{f}}_{{\mathtt{x}}_2+1,{\mathtt{y}}_2+1}+1$$

---

用差分数组求前缀和就可以获得原数组。

二、基础运用

1. 堆积成山的书

1.1 审题

有两叠书，分别有 $N$ 和 $M$ 本。
看完第一叠自顶向下第 $i$ 本书需要 $A_i$ 分钟，看完第二叠自顶向下第 $i$ 本书需要 $B_i$ ​分钟。
你每次可以花时间看完任意一叠书（不为空）的最上面那一本书，然后把它移除。
问你在 $K$ 分钟内最多能看完几本书？

1.2 分析

我们可以使用前缀和数组 pfx[]，更方便地计算累积时间。这道题的突破口是通过遍历第一叠书和第二叠书，找到能在限定时间内看完的最大本数。

1.3 参考答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+8;
ll n,m,k,pfx[MAXN];
int main(){
    cin>>n>>m>>k;
    for(int i=1,a;i<=n;i++){
        cin>>a;
        pfx[i]=pfx[i-1]+a;
    }
    ll sum=0,idx=n,ans;//sum:第二叠书的总时间,idx:第一叠书的剩余本数
    //尝试让第一叠书能够在时间限制内看完的最大本数
    while(idx>0&&pfx[idx]>k)idx--;// 少看一本
    }

    ans=idx;//第一叠书的前idx本书
    //逐本判断第二叠书能否在时间限制内看完，并更新答案
    for(int i=1,b;i<=m;i++){
        cin>>b;
        sum+=b;//累加第二叠书的时间
        //判断第一叠书是否能在时间限制内看完
        while(idx>=0&&pfx[idx]+sum>k)idx--;
        if(idx==-1)break;//如果第一叠书已经无法看完，跳出循环
        ans=max(ans,idx+i);//更新答案
    }
    cout<<ans;//输出答案
    return 0;
}

2. 皮皮过马路

2.1 审题

每天放学的时候，皮皮和他的朋友们都会穿过校门口的马路。
考虑皮皮的学校在二维平面的地图，马路沿水平方向延伸，马路的一侧由直线 $y=0$ 描述，另一侧由直线 $y=1$ 描述。
第 $i$ 个小朋友从马路一侧的位置 $(a_i,0)$ 沿直线过马路到达另一侧的位置 $(b_i,1)$。
所有 $a_i$ 互不相同，所有 $b_i$ 互不相同。
尽管他的朋友们行动敏捷，他还是担心行动路径交叉的两个小朋友在过马路时发生碰撞。
皮皮认为，如果一个小朋友的行动路径没有跟其他任何小朋友的行动路径相交，则该小朋友是安全的。
请帮助皮皮计算安全的小朋友的数量。

2.2 分析

善用前缀信息和后缀信息。

2.3 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
int n,ans,pfx_mx[MAXN],sfx_mn[MAXN];
struct Node{
    int a,b;
    bool operator<(const Node&rhs)const{
        return a<rhs.a;
    }
}p[MAXN];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>p[i].a>>p[i].b;
    sort(p+1,p+n+1);
    pfx_mx[0]=-1e9,sfx_mn[n+1]=1e9;
    for(int i=1;i<=n;i++)
        pfx_mx[i]=max(pfx_mx[i-1],p[i].b);
    for(int i=n;i>=1;i--)
        sfx_mn[i]=min(sfx_mn[i+1],p[i].b);
    for(int i=1;i<=n;i++)
        if(p[i].b==pfx_mx[i]&&p[i].b==sfx_mn[i])
            ans++;
    cout<<ans;
    return 0;
}

3. 吃豆子

3.1 审题

现在有一个 $n\times m$ 的棋盘，左下角的格子为 $(1,1)$，右上角格子为 $(n,m)$，每个棋盘格子可以放任意数量的豆子。
小明有 $k$ 次操作，对于每次操作给出四个数字 $x_1,y_1,x_2,y_2$，表示小明会将所有 $(x,y)$ 满足 $x_1\le x\le x_2,y_1\le y\le y_2$ 格子放上一个豆子。
在小明完成 $k$ 次操作后，他将对你进行 $q$ 次询问。
每次询问给出四个数 $x_1,y_1,x_2,y_2$，问所有 $(x_1,y_1)$ 满足 $x_1\le x\le x_2,y_1\le y\le y_2$ 的格子上的豆子的总数和为多少？

3.2 分析

区间和模板，但是会超时：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2008;
const int MAXM=2008;
int n,m,k,q,a[MAXN][MAXM],pfx[MAXN][MAXM];
int main() {
cin>>n>>m>>k>>q;
for(int i=1,x1,y1,x2,y2;i<=k;i++){
    cin>>x1>>y1>>x2>>y2;
    for(int j=x1;j<=x2;j++)
        for(int k=y1;k<=y2;k++)
            a[j][k]++;
}
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        pfx[i][j]=pfx[i-1][j]+pfx[i][j-1]-pfx[i-1][j-1]+a[i][j];
for(int i=1,x1,y1,x2,y2;i<=q;i++){
    cin>>x1>>y1>>x2>>y2;
    cout<<pfx[x2][y2]-pfx[x1-1][y2]-pfx[x2][y1-1]+pfx[x1-1][y1-1]<<endl;
}
    return 0;
}

所以需要用二维差分和二维前缀和，两者之间互相转换。

3.3 参考答案

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2008;
const int MAXM=2008;
int n,m,k,q,diff[MAXN][MAXM],a[MAXN][MAXM],pfx[MAXN][MAXM];
signed main(){
    cin>>n>>m>>k>>q;
    for(int i=1,x1,y1,x2,y2;i<=k;i++){
        cin>>x1>>y1>>x2>>y2;
        diff[x1][y1]++;
        diff[x1][y2+1]--;
        diff[x2+1][y1]--;
        diff[x2+1][y2+1]++;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            a[i][j]=diff[i][j]+
                    (i>1?a[i-1][j]:0)+
                    (j>1?a[i][j-1]:0)-
                    (i>1&&j>1?a[i-1][j-1]:0);
            pfx[i][j]=a[i][j]+
                        (i>1?pfx[i-1][j]:0)+
                        (j>1?pfx[i][j-1]:0)-
                        (i>1&&j>1?pfx[i-1][j-1]:0);
        }
    for(int i=1,x1,y1,x2,y2;i<=q;i++){
        cin>>x1>>y1>>x2>>y2;
        int result=pfx[x2][y2]-
                     (x1>1?pfx[x1-1][y2]:0)-
                     (y1>1?pfx[x2][y1-1]:0)+
                     (x1>1&&y1>1?pfx[x1-1][y1-1]:0);
        cout<<result<<endl;
    }
    return 0;
}

三、高阶应用

1. 老式录音机

1.1 审题

小明要用录像机录 $N$ 个电视节目。 一共有 $C$ 个电视频道，从 $1$ 到 $C$ 编号。
第 $i$ 个电视节目从时刻 $s_i$ 开始，时刻 $t_i$ 结束，在频道 $c_i$ 播出。(包含开始时刻 $s_i$，不包含结束时刻 $t_i$)
同一个频道不会同时播出多个节目。
如果某个录像机在时刻 $S$ 到时刻 $T$ 录像某个频道的节目，如果接下来想用它录像其他频道的节目，需要将这个录像机接到另一个频道上，操作时间为 $D$，所以最早必须等到 $T+D$ 时刻才能开始录制其他频道的节目。
若要录下全部 $N$ 个节目，至少需要多少台录像机？

1.2 参考答案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int MAXT=2e6+8;
int n,c,d,maxt=0,diff[MAXT];
struct show{
    int s,t,c;
    bool operator<(show&rhs)const{
        if(c!=rhs.c)return c<rhs.c;
        else return s<rhs.s;
    }
}s[MAXN];
int main(){
    cin>>n>>c>>d;
    for(int i=1;i<=n;i++){
        cin>>s[i].s>>s[i].t>>s[i].c;
        maxt=max(maxt,s[i].t);
    }
    sort(s+1,s+n+1);
    for(int i=1;i<=n;i++){
        if(s[i].c==s[i-1].c&&s[i-1].t+d>s[i].s){
            diff[s[i-1].t+d]++;
            diff[s[i].t+d]--;
        }else{
            diff[s[i].s]++;
            diff[s[i].t+d]--;
        }
    }
    int ans=0,cnt=0;
    for(int i=1;i<=maxt;i++)
        cnt+=diff[i],ans=max(ans,cnt);
    cout<<ans;
    return 0;
}

2. [NOIP2012 提高组] 借教室

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+8;
int n,m,d[MAXN],s[MAXN],t[MAXN],base[MAXN],diff[MAXN];
bool check(int ans){
    for(int i=1;i<=n;i++)diff[i]=base[i];
    for(int i=1;i<=ans;i++)
        diff[s[i]]-=d[i],diff[t[i]+1]+=d[i];
    int rmn=0;
    for(int i=1;i<=n;i++){
        rmn+=diff[i];
        if(rmn<0)return false;
    }
    return true;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>base[i];
    for(int i=n;i>=1;i--)base[i]-=base[i-1];
    for(int i=1;i<=m;i++)cin>>d[i]>>s[i]>>t[i];
    if(check(m))return cout<<0<<endl,0;
    int l=0,r=m;
    while(l<r){
        int mid=l+(r-l>>1);
        if(check(mid))l=mid+1;
        else r=mid;
    }
    cout<<-1<<endl<<l;
    return 0;
}

原文地址：https://blog.csdn.net/joe_g12345/article/details/145259702

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！