第二题 亚索的粒子实验
【问题描述】
亚索是一名伟大的科学家，他最近在做一个粒子的实验，粒子初始有一定的能量，实验过程中倘若第i个粒子被注入k能量，那该粒子就会增加k能量，同时由于辐射作用，第2i，3i，4i……（即i的倍数的粒子）也会增加k能量。
他有一台特殊的机器，能够为一段连续的粒子注入一定的能量，此时辐射同样存在，实验过程中，由于他需要取出某些粒子观察一下数据变化，但这十分困扰他，因此，他找到了聪明的你们，希望你们能在他需要数据的时候告诉他相应粒子能量的大小。
【输入格式】
输入文件名为yasuo.in。
输入第 1 行包含 1 个正整数 n ，表示 n 个粒子。
接下来第 2 行有n个数，第i个数ai表示第i个粒子的初始能量值。
第 3 行包括一个数q，表示操作数，包括询问和操作。
接下来 q 行，每行格式如下：
1 i，表示询问第i个粒子当前的能量值。
2 l r d，表示对[l,r]区间中的所有粒子注入d能量。
【输出格式】
输出文件名为yasuo.out。
对于每一个询问输出一行，表示相应粒子的能量值。
【输入输出样例1】
|
yasuo.in |
yasuo.out |
|
3 1 2 3 2 2 1 3 5 1 2 |
12 |
【输入输出样例2】
|
yasuo.in |
yasuo.out |
|
6 1 2 1 4 5 6 5 2 2 4 2 1 3 1 4 2 3 5 1 1 5 |
3 8 6 |
【数据规模与约定】
对于 30%的数据 0<=n<=100,0<=q<=100.
对于 70%的数据 0<=q<=10^5.
对于 100%的数据 0<=n<=10^5,0<=q<=5*10^5,0<=ai<=10^6
1<=i<=n,1<=l<=r<=n,0<=d<=10^6
半年前做这道题是一脸懵逼，半年后依然懵逼= =，撸了半个多小时线段树+调了1个多小时仍然是只过样例，看了std才发现是分块！
具体实在没啥好说的了，直接看代码好了，代码实在是太清晰了。。。
#include <cstdio>
#include <cmath>
const int maxn = 100005;
int n, div[maxn][135], idx[maxn], opr, t1, t2, p, lmt, q, a[maxn], x, y;
long long f[maxn], g[maxn], t3, ans;
int main(void) {
freopen("yasuo.in", "r", stdin);
freopen("yasuo.out", "w", stdout);
scanf("%d", &n);
p = (int)sqrt((float)n + 0.5f);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
div[1][idx[1]++] = 1;
for (int i = 2; i <= n; ++i) {
lmt = (int)sqrt((float)i + 0.5f);
for (int j = 1; j <= lmt; ++j) {
if (i % j == 0) {
div[i][idx[i]++] = j;
if (j != i / j) {
div[i][idx[i]++] = i / j;
}
}
}
}
scanf("%d", &q);
while (q--) {
scanf("%d", &opr);
if (opr == 1) {
scanf("%d", &t1);
ans = (long long)a[t1];
for (int i = 0; i < idx[t1]; ++i) {
t2 = div[t1][i];
ans += f[t2] + g[t2 / p];
}
printf("%I64d
", ans);
}
else {
scanf("%d%d%I64d", &t1, &t2, &t3);
x = t1 / p;
y = t2 / p;
if (x == y) {
for (int i = t1; i <= t2; ++i) {
f[i] += t3;
}
continue;
}
for (int i = t1; i < (x + 1) * p; ++i) {
f[i] += t3;
}
for (int i = x + 1; i < y; ++i) {
g[i] += t3;
}
for (int i = y * p; i <= t2; ++i) {
f[i] += t3;
}
}
}
return 0;
}