「HNOI2010」弹飞绵羊

传送门

考虑分块。

每一个位置 \(i\) ，记 \(to[i]\) 表示从这个位置一直往右跳回落在哪个位置。

然后修改的时候直接暴改，查询也是暴跳，复杂度 \(O(n \sqrt n)\)

参考代码：

#include <algorithm>

#include <cstdio>

#include <cmath>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while ('0' > c || c > '9') f |= c == '-', c = getchar();

	while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

	s = f ? -s : s;

}

const int _ = 200010;

int n, f[_], k[_];

int gap, pos[_], to[_], l[_ >> 1];

int main() {

#ifndef ONLINE_JUDGE

	file("cpp");

#endif

	read(n), gap = sqrt(n * 1.0);

	for (rg int i = 1; i <= n; ++i) {

		read(k[i]), pos[i] = (i - 1) / gap + 1;

		if (pos[i - 1] != pos[i]) l[pos[i]] = i;

	}

	l[pos[n] + 1] = n + 1;

	for (rg int i = n; i >= 1; --i) {

		if (i + k[i] >= l[pos[i] + 1])

			f[i] = 1, to[i] = i + k[i];

		else

			f[i] = f[i + k[i]] + 1, to[i] = to[i + k[i]];

	}

	int q; read(q);

	for (rg int opt, x, o = 1; o <= q; ++o) {

		read(opt), read(x), ++x;

		if (opt == 1) {

			int res = 0;

			while (x <= n) res += f[x], x = to[x];

			printf("%d\n", res);

		} else {

			read(k[x]);

			for (rg int i = l[pos[x] + 1] - 1; i >= l[pos[x]]; --i) {

				if (i + k[i] >= l[pos[x] + 1])

					f[i] = 1, to[i] = i + k[i];

				else

					f[i] = f[i + k[i]] + 1, to[i] = to[i + k[i]];

			}

		}

	}

	return 0;

}

巴特西

「HNOI2010」弹飞绵羊

「HNOI2010」弹飞绵羊

最新文章

热门文章