1 条题解
-
0
#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
- 上传者