---
title: "改变数组元素"
created: 2025-11-28
tags:
  - 算法
---

# 改变数组元素

## 题目 [改变数组元素](https://www.acwing.com/problem/content/description/3732/)

![[image-d809f068.png]]

## 思路分析

每进行一次操作 就让最后i个数变成1

直接想到差分

注意几个边界问题

不难得知这个区间就是i-a[i]+1处++ i处--

但如果i-a[i]+1<0呢 那就越界了

这个情况实际是把所有数都置成1(区间变成1 ，i）

所以可以用max(1,i-a[i]+1）确定左区间

![[image-133b20d0.png]]

然后一个性质就是 和之前有道题“[[合格数|合格数]]”差不多
它也不在乎数组里具体是什么

有就是1 没有就是0

感觉这也是差分和区间合并的一个交集的地方 好像有这种性质的大都能用区间合并写

那么来看第二种 区间合并的写法

把每次的操作读入 不急着做 因为它每次都是把一些置1 这就有很多重复的地方

我完全可以把能合并的操作都合并起来

再统一做置1的操作

这个过程可以朴素的直接把st~ed的数置1

也可以再结合差分

在区间开始处+1 结尾处-1

然后发现还没有直接差分快hhh

## 代码实现

**差分 531ms**

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;
int a[N],b[N];
int T,n;

int main()
{
    cin>>T;
    while(T--){
        cin>>n;
        memset(b,0,(n+1)*4);// 重置差分数组 其实只要前(n+1)个数
        for(int i=1;i<=n;i++){
            cin>>a[i];//也可以不用开a[]存 直接用x读入就行
            //让前i个数变成1 找到左右区间准备做差分
            //如果左边越界就直接从第一个数开始全设为1
            int l=max(1,i-a[i]+1),r=i;
            b[l]++,b[r+1]--;
        }
        //构造前缀和 但不在于具体是几 有就是1 没有就是0
        for(int i=1;i<=n;i++){
            b[i]+=b[i-1];
            if(b[i])
                cout<<1<<" ";
            else
                cout<<0<<" ";
        }
        cout<<endl;
    }
    return 0;
}
```

**区间合并873ms**

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N=2e5+10;
vector<PII> ranges;
int ans[N];
int T,n;

int main()
{
    cin>>T;
    while(T--){
        cin>>n;
        memset(ans,0,(n+1)*4);// 重置前(n+1)个数
        ranges.clear();
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            //这里要特判一下 是0才加入
            //直接差分就不需要 因为l=i+1 r=i 右边又是r+1 所以抵消
            if(x>0){
                int l=max(1,i-x+1),r=i;
                ranges.push_back({l,r});
            }
        }
        sort(ranges.begin(),ranges.end());
        int st=-1,ed=-1;
        for(auto range:ranges){
            if(ed+1<range.first){//1~2 3~4这种也能合并
                if(ed!=-1)
                    for(int i=st;i<=ed;i++)
                        ans[i]=1;
                st=range.first,ed=range.second;
            }
            else if(ed<range.second)
                ed=range.second;
        }
        if(ed!=-1)
            for(int i=st;i<=ed;i++)
                ans[i]=1;
        for(int i=1;i<=n;i++)
            cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}
```

**区间合并加差分 832ms**

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N=2e5+10;
vector<PII> ranges;
int ans[N];
int T,n;

int main()
{
    cin>>T;
    while(T--){
        cin>>n;
        memset(ans,0,(n+1)*4);// 重置前(n+1)个数
        ranges.clear();
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            if(x>0){
                int l=max(1,i-x+1),r=i;
                ranges.push_back({l,r});
            }
        }
        sort(ranges.begin(),ranges.end());
        int st=-1,ed=-1;
        for(auto range:ranges){
            if(ed+1<range.first){
                if(ed!=-1){
                    ans[st]++;//把全赋1改成差分形式的++--
                    ans[ed+1]--;
                }
                st=range.first,ed=range.second;
            }
            else if(ed<range.second)
                ed=range.second;
        }
        if(ed!=-1){
            ans[st]++;//同理
            ans[ed+1]--;
        }

        for(int i=1;i<=n;i++){
            ans[i]+=ans[i-1];
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[差分|差分]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/前缀和与差分相关模型/差分/救生员|救生员]]