一、题目
1、原题链接
3729. 改变数组元素
2、题目描述
给定一个空数组 V 和一个整数数组 a1,a2,…,an。
现在要对数组 V 进行 n 次操作。
第 i 次操作的具体流程如下：
从数组 V 尾部插入整数 0。 将位于数组 V 末尾的ai个元素都变为 1（已经是 1 的不予理会）。
注意：
ai 可能为 0，即不做任何改变。
ai 可能大于目前数组 V 所包含的元素个数，此时视为将数组内所有元素变为 1。
请你输出所有操作完成后的数组 V。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
每组数据输出一行结果，表示所有操作完成后的数组 V，数组内元素之间用空格隔开。
数据范围
1≤T≤20000,1≤n≤2×105,0≤ai≤n,保证一个测试点内所有 n 的和不超过 2×105。
输入样例：
3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0
输出样例：
1 1 0 1 1 1
0 1 1 1 1 1 0 0 1 1
0 0 0
1
2
3
二、解题报告
1、思路分析
思路1：差分+区间合并
（1）将每个需要+1的区间合并，得到若干个不重叠的区间。
（2）对每个区间利用差分将每个区间元素值+1。
（3）对差分数组求前缀和得到结果数组，输出即可。
思路2：y总思路
思路来源：y总每日一题b站视频链接
y总yyds
（1）直接对每个区间进行差分将每个区间元素值+1。
（2）对差分数组求前缀和得到数组，如果数组元素值>=1说明进行了+1操作，直接输出1；否则说明该值没有+1，直接输出0。
2、时间复杂度
思路1时间复杂度O(nlogn)（sort()函数、快排时间复杂度nlogn级别）
思路2时间复杂度O(n)
3、代码详解
思路1代码
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;
vector<PII> v;
const int N=200010;
int pos;
int t,n;
int a[N],b[N];
//区间合并
void merge(vector<PII> &vec){
vector<PII> ans;
sort(vec.begin(),vec.end());
int st=-1,ed=-1;
for(auto i:vec){
if(ed<i.first){
if(st!=-1) ans.push_back({st,ed});
st=i.first,ed=i.second;
}
else ed=max(ed,i.second); }
if(st!=-1) ans.push_back({st,ed});
vec=ans;
}
//差分
void insert(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++){
pos=i; //pos记录当前数组中元素的个数
cin>>a[i];
if(a[i]==0) continue; //如果需要将0个元素置为1，跳过下面步骤，执行下一次循环
if(pos<=a[i]){ //如果需要置为1的元素个数超过数组元素个数
v.push_back({1,pos}); //需置成1的区间为整个数组
}
else{
v.push_back({pos-a[i]+1,pos}); //否则需置成1的区间为数组后a[i]个元素所在区间
}
}
merge(v);
for(auto i:v){
insert(i.first,i.second,1);
}
//差分数组求前缀和，得到结果数组
for(int i=1;i<=pos;i++){
b[i]+=b[i-1];
cout<<b[i]<<' ';
}
cout<<endl;
memset(b,0,sizeof b); //注意不要忘记，下一次循环前需将元素置为0
pos=0; //pos也别忘记
v.clear(); //区间数组也得清空
}
return 0;
}
思路2代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=200010;
int t,n;
int a[N],b[N];
//差分
void insert(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
int main(){
cin>>t;
int pos=0;
while(t--){
cin>>n;
for(int i=1;i<=n;i++){
pos=i; //pos代表当前元素个数
cin>>a[i];
if(a[i]==0) continue; //如果需要把0个元素置为1，直接跳过下面步骤，执行下一次循环
if(a[i]>=pos){ //如果需要置的元素个数大于等于区间元素数
insert(1,pos,1); //将[1,pos]即整个区间加1
}
else{
insert(pos-a[i]+1,pos,1); //否则只个数组后a[i]个元素加1
}
}
//差分数组求前缀和，得到每个区间加1后的结果数组
for(int i=1;i<=pos;i++){
b[i]+=b[i-1];
if(b[i]>=1) cout<<1<<' '; //如果某个位置加了大于等于1次个1，输出1
else cout<<0<<' '; //如果没有加过1，输出0
}
cout<<endl;
memset(b,0,sizeof b); //注意不要忘记，下一次循环前需将元素置为0
pos=0; //pos也别忘记
}
return 0;
}
三、知识风暴
一维差分
一维差分可以快速地给指定区间的每个数加任意常数c
差分数组顾名思义就是相邻元素之差组成的数组。
我们如果要对某个区间加减任意常数c可以先求其差分数组，然后对差分数组进行操作。设b数组为差分数组。
操作：对[l,r]区间每个数+c：b[l]+=c,b[r+1]-=c。
最后再对差分数组求前缀和即为处理后的原数组。
区间合并
区间合并就是将某些有重叠（或者说是相交）的区间合并。
基本思路：
将所有需要合并的区间按左端点排好序。
以排好序的第一个区间开始，看第二个区间是否与第一个区间有重叠，而且右端点比第一个区间大，如果满足则合并，合并操作就是将第一个区间的右端点更新成第二个区间的右端点；如果第二个区间被第一个区间所完全覆盖，则合并后的区间就是第一个区间，不需要操作；如果第二个区间和第一个区间完全没有交集，说明第二个区间的左端点比第一个区间的右端点大，而我们又是按照区间左端点进行排序的，则下一个区间的左端点也比第一个区间的左端点大，说明当前第一个区间已经和后面所有区间都不可能有交集了，所以第一个区间已经合并完成，我们将其放入结果数组中，下一次将剩下区间里的第一个区间进行如上合并操作，直到完成所有区间合并操作，将最后一个区间也放入结果数组，合并完成。
