摘要
Title: 3729. 改变数组元素
Tag: memset、差分
Memory Limit: 64 MB
Time Limit: 1000 ms

3729. 改变数组元素

情人节快乐！

题意

给定一个空数组 V和一个整数数组 a1,a2,…,an
现在要对数组 V进行 n次操作。
第 i次操作的具体流程如下：
从数组 V尾部插入整数 0。将位于数组 V末尾的 ai个元素都变为 1（已经是 1的不予理会）。
思路

思路就是差分，没什么好说的，就是想记录一下memset的用法
可以注意到此题 T = 2e4, n = 2e5, 虽然memset相对于循环定义来说，快了不少
但如果我们每次都
1
memeset(b, 0, sizeof b)
会导致每组数据都O(n)跑一遍，4e9就很难过，也就是卡memset！！

所以采用下面两种方法，原理是一样的，都是不全清0
1
2
3
4
memset(b, 0, (n + 1) * 4) // 意思就是，我们下标是从0开始的，所以用n+1个元素。数组类型是int，所以占4个byte

for (int i = 1; i <= n; ++i) // 循环清0
b[i] = 0;
亲测快了十倍！

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-02-14 21:37:04
* @FilePath: \Acwing\3729\3729.cpp
* @LastEditTime: 2023-02-14 22:18:33
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int a[N], b[N];

int n;
void solve()
{
    scanf("%d", &n);
    memset(b, 0, (n + 1) * 4);
    // for (int i = 1; i <= n; ++i)
    //     b[i] = 0;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        b[max(1, i - a[i] + 1)]++;
        b[i + 1]--;
    }
    for (int i = 1; i <= n; ++i)
    {
        b[i] += b[i - 1];
        printf("%d ", b[i] ? 1 : 0);
    }
    printf("\n");
    return;
}

signed main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        solve();
    return 0;
}

3729. 改变数组元素

题意

思路

代码