题目描述

给定一个空数组 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×10^5,
0≤ai≤n,
保证一个测试点内所有 n 的和不超过 2×10^5。

输入样例：

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

思路

方法一：差分（O(N)）(N是数组长度)

思路

我们会发现问题可以简化为：给定一个长度为n的0串，然后去修改它中的一些区间变为1。那么我们发现其实有的位置可以被修改很多次，只不过如果已经是1了，那么再修改就不起作用了。所以我们每次，拿到一个值，相当于将一个范围内的所有数字都变为1，于是我们就对修改次数进行差分即可，最后我们求差分数组的前缀和来还原原数组之后，只要是某个位置上的值不是0，那么这个位置就是1。
这里有个小的trick：对于一个非0的值变为1，对于0就是0，有什么简洁的操作吗？答：!!a即可。！会将非零值变为0，将0值变为1。

代码

//差分数组：时间复杂度O(N)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 200010;

int b[N];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        //由于数据范围比较大，我们手动清空b数组
        for(int i = 1; i<=n; i++) b[i] = 0;
        for(int i = 1; i<=n; i++)
        {
            int a;
            cin>>a;
            int l = max(1,i-a+1), r = i;
            b[l]++, b[r+1]--;
        }
        for(int i = 1; i<=n; i++)
        {
            b[i] += b[i-1];
            printf("%d ", !!b[i]);
        }
        cout<<endl;
    }
    return 0;
}

方法二：区间合并（O(NlogN)）(N为原始区间的个数)

思路

根据方法一所说，这其实就是将原本一个0串的区多个区间修改为1的过程，只不过这个过程会有重叠，有重叠就意味着时间可能会超。因此，我们可以利用区间合并算法来将重叠的区间进行合并。

区间合并

第一步：按照各个区间的左端点对所有区间进行排序。
第二步：合并区间。

void merge(vector<PII> &segs)
{
    vector<PII> res;
    sort(segs.begin(),segs.end());
    int st = -1, en = -1;
    for(auto & v : segs)
    {
        if(en < v.first)
        {
            if(st != -1) res.push_back({st,en});
            st = v.first, en = v.second;
        }
        else en = max(v.second,en);
    }
    if(st != -1) res.push_back({st,en});
    segs = res;
}

代码

//区间合并 O（NlogN）
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 200010;

typedef pair<int, int> PII;

void merge(vector<PII> &segs)
{
    vector<PII> res;
    sort(segs.begin(),segs.end());
    int st = -1, en = -1;
    for(auto & v : segs)
    {
        if(en < v.first)
        {
            if(st != -1) res.push_back({st,en});
            st = v.first, en = v.second;
        }
        else en = max(v.second,en);
    }
    if(st != -1) res.push_back({st,en});
    segs = res;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        vector<PII> segs;
        for(int i = 0; i<n; i++)
        {
            int a;
            cin>>a;
            int l = max(0,i-a+1), r = i;
            if(l<=r)
                segs.push_back({l,r});
        }
        // for(auto &t : segs)
        //     cout<<t.first<<" "<<t.second<<endl;
        merge(segs);
        // for(auto &t : segs)
        //     cout<<t.first<<" "<<t.second<<endl;
        vector<int> ans(n);
        for(auto & t: segs)
        {
            for(int i = t.first; i<=t.second; i++)
                ans[i] = 1;
        }
        for(int i = 0; i<n; i++) cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}