1 条题解

  • 0
    @ 2023-1-31 9:52:53
    #include <bits/stdc++.h>
    using namespace std;
    int n, opt, l, r, c;
    int a[50004];
    //块的大小、块的数量,第i个数所在的块、第i个块的左右端点、整个区间加法的标记
    int SZ, CNT, ID[50004], L[1004], R[1004], lazy[1004];
    void update(int l, int r, int c)
    {
        if (ID[l] == ID[r])
        {
            for (int i = l; i <= r; i++)
                a[i] += c;
            return;
        }
        for (int i = l; i <= R[ID[l]]; i++)
            a[i] += c;
        for (int i = ID[l] + 1; i <= ID[r] - 1; i++)
            lazy[i] += c;
        for (int i = L[ID[r]]; i <= r; i++)
            a[i] += c;
    }
    int query(int r)
    {
        return a[r] + lazy[ID[r]];
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        SZ = sqrt(n);
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            //1: [1, SZ], 2: [SZ + 1, 2SZ]
            ID[i] = (i - 1) / SZ + 1;
        }
        CNT = n / SZ + (n % SZ > 0);
        for (int i = 1; i <= CNT; i++)
        {
            L[i] = (i - 1) * SZ + 1;
            R[i] = i * SZ;
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> opt >> l >> r >> c;
            if (opt == 0)
                update(l, r, c);
            else
                cout << query(r) << "\n";
        }
        return 0;
    }
    
    • 1

    信息

    ID
    872
    时间
    100ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    83
    已通过
    23
    上传者