[GZOI2016] 亚索的量子实验【分块】

第二题亚索的粒子实验

【问题描述】

亚索是一名伟大的科学家，他最近在做一个粒子的实验，粒子初始有一定的能量，实验过程中倘若第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

1 2 3

2 1 3 5

1 2

【输入输出样例2】

yasuo.in

yasuo.out

1 2 1 4 5 6

2 2 4 2

1 3

1 4

2 3 5 1

1 5

【数据规模与约定】

对于 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\n", 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;

}

巴特西

[GZOI2016] 亚索的量子实验【分块】

最新文章

热门文章