C++蓝桥杯改变数组元素问题差分算法

Question

#include <iostream>     
#include <cstring>
 
using namespace std;

const int N=200010;

int n;
int b[N];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(b,0,(n+1)*4);
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            x=min(x,i);
            int l=i-x+1,r=i;
            b[l]++,b[r+1]--;
        }
        for(int i=1;i<=n;i++)
            b[i]+=b[i-1];
        for(int i=1;i<=n;i++)
            printf("%d ",!!b[i]);
        puts("");
    }
    return 0;
}

b[l]++,b[r+1]--;如何解释，不是把l和r之间的+1吗？
b[i]+=b[i-1];又怎么解释？

Answer 1

该回答引用ChatGPT

$a_1,a_2,\cdots,a_n$，对于每个位置 $i$，求出该位置之前的所有数中，最大值不超过 $i$ 的数的个数。

代码中使用的是差分的思想。具体来说，对于每个数 $a_i$，我们将它和位置 $i$ 取 $\min$，记为 $x$，则 $a_i$ 之前的数中最大值不超过 $i$ 的数的个数就是 $i-x+1$。于是我们将差分数组 $b$ 的第 $l$ 项加 $1$，第 $r+1$ 项减 $1$，其中 $l=i-x+1,r=i$。这样得到的差分数组 $b$ 的前缀和就是我们要求的结果。具体来说，对于每个位置 $i$，$b_i$ 表示有多少个数的最大值不超过 $i$。对 $b$ 数组求前缀和后，$b_i$ 表示有多少个数的最大值不超过 $i$，将其输出即可。

至于你的疑问：

b[l]++,b[r+1]-- 是在对差分数组进行修改。我们将 $[l,r]$ 这个区间内的数的贡献加上 $1$，也就是说，$[l,r]$ 这个区间内的所有位置的值都加 $1$，同时，将 $r+1$ 这个位置的值减 $1$，这样可以保证下一次处理 $[l',r']$ 区间时不会把 $[l,r]$ 的贡献算进去。
b[i]+=b[i-1] 是在对差分数组求前缀和，也就是将差分数组还原为原数组。具体来说，$b_i$ 表示了原数组中最大值不超过 $i$ 的数的个数，所以将 $b$ 数组求前缀和后，$b_i$ 表示的就是原数组中最大值不超过 $i$ 的数的个数。