P3203 HNOI2010 弹飞绵羊

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, len, t, op, p, w, k[200025], dp[200025], to[200025], pos[200025], s[1025], e[1025];
inline ll read() {
	ll neg = 1, x = 0;
	char c;
	while ((c = getchar()) < '0' || c > '9') if (c == '-') neg = -1;
	x = c - '0';
	while ((c = getchar()) >= '0' && c <= '9') x = x * 10 + (c - '0');
	return x * neg;
}
ll ask(int p) {
	ll res = 0;
	while (p <= n) {
		res += dp[p];
		p = to[p];
	}
	return res;
}
void change() {
	k[p] = w;
	for (int i = e[pos[p]]; i >= s[pos[p]]; i--) {
		if (i + k[i] >= e[pos[i]] + 1) {
			dp[i] = 1;
			to[i] = i + k[i];
		} else {
			dp[i] = dp[i + k[i]] + 1;
			to[i] = to[i + k[i]];
		}
	}
}
int main() {
	n = read();
	len = sqrt(n);
	t = (ll)ceil(1.0 * n / len);
	for (int i = 1; i <= n; i++) {
		k[i] = read();
		pos[i] = (ll)ceil(1.0 * i / len);
	}
	for (int i = 1; i <= t; i++) {
		s[i] = e[i - 1] + 1;
		e[i] = i*len;
	}
	for (int i = n; i >= 1; i--) {
		if (i + k[i] >= e[pos[i]] + 1) {
			dp[i] = 1;
			to[i] = i + k[i];
		} else {
			dp[i] = dp[i + k[i]] + 1;
			to[i] = to[i + k[i]];
		}
	}
	m = read();
	while (m--) {
		op = read(), p = read();
		p++;
		if (op == 1) {
			cout << ask(p) << "\n";
		} else {
			w = read();
			change();
		}
	}
	return 0;
}

除了第1和第3个测试点，其他全部TLE