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

#include      
#include 
 
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];又怎么解释？

该回答引用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$ 的数的个数。

b[l]++ 就是取b数组的下标 l 位置的数比如b[l]=a，那么另a=a+1。即让下标 l 的这个数变大1
b[r+1]-- 与上面类似，取b数组下标为 r+1 位置的数比如b[r+1]=c，另c=c-1 。即让下标r+1对应的数减小1
b[i]+=b[i-1] 就是b数组的每个数是自己与前面那个数的和

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7639411
• 这篇博客你也可以参考下：C++ 算法 查找元素
• 这篇博客也不错, 你可以看下C++ 算法 查找元素

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^