- 数列分块入门 1
TJ
- 2024-1-31 15:42:36 @
/* created by chjshen, date: 2024-01-31 15:31 */
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define int long long
const int N = 5E4 + 5;
int n, a[N], L[N], R[N], pos[N], add[N];
int bl, bn;
void update(int l, int r, int c)
{
int lb = pos[l], rb = pos[r];
if (lb == rb)
for (int i = l; i <= r; i++) a[i] += c;
else
{
// 1. pre block
for (int i = l; i <= R[lb]; i++) a[i] += c;
// 2. mid block
for (int i = lb + 1; i <= rb - 1; i++) add[i] += c;
// 3.after block
for (int i = L[rb]; i <= r; i++) a[i] += c;
}
}
void query(int k)
{
cout << a[k] + add[pos[k]] << endl;
}
void handle(void)
{
int op, l, r, c;
cin >> op >> l >> r >> c;
if (op == 0)
update(l, r, c);
else
query(r);
}
void initInput(void)
{
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
// init block
bl = sqrt(n);
bn = n / bl;
for (int i = 1; i <= bn; i++)
{
L[i] = (i - 1) * bl + 1, R[i] = i * bl;
for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
}
if (bl * bn < n)
{
bn++;
L[bn] = (bn - 1) * bl + 1;
R[bn] = n;
for (int j = L[bn]; j <= R[bn]; j++) pos[j] = bn;
}
for (int i = 1; i <= n; i++) handle();
}
signed main(void)
{
initInput();
return 0;
}
1 条评论
-
yl001 LV 9 @ 2024-1-31 15:46:10
qp
- 1
信息
- ID
- 2596
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 167
- 已通过
- 30
- 上传者