Solution - Holes

liuzimingc / 2024-01-09 / 原文

Link。

暴力做是 $O(nm)$ 的。怎么优化呢？I've no slightest idea😢

结果用到了一个特别神的东西，罗阿姨认为 useless 的东西——分块。想到这个就豁然开朗了！

假设块长为 $\sqrt{n}$，$f_i$ 表示块内的步数，$to_i$ 表示块内的最后到达的点。我们分成若干段，如果对于 $i$，跳完之后还在同一块内就简单转移一下，否则说明跳到其它块里去了，相当于当前块里的结束点，那么 $f_i = 1, to_i = i$。

询问的话，每次先算当前块内的，然后跳到 $to_i$。如果 $to_i$ 再跳一步就 $> n$ 了，直接跳出循环，否则说明还会计算下一个块，直接跳就可以了。$O(\sqrt{n})$。

更新只更新一段。$O(\sqrt{n})$。

总的就是 $O(m \sqrt{n})$。由于神秘原因块长设为 $2 \sqrt{n}$ 才可以过。

~~原因是询问比较多，这样平衡一下。~~

namespace liuzimingc {
const int N = 2e5 + 5; // i + pos[i] 可能会 RE，开两倍，也可以单独判一下是否 > n
#define endl '\n'

int n, m, p[N], f[N], to[N], block, pos[N], l[N], r[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m;
	block = (int)2 * sqrt(n);
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
		pos[i] = (i - 1) / block + 1;
	}
	for (int i = 1; i <= n; i++)
		if (!l[pos[i]]) l[pos[i]] = i;
	for (int i = n; i; i--)
		if (!r[pos[i]]) r[pos[i]] = i;
    for (int i = n; i; i--)
		if (pos[i + p[i]] == pos[i]) f[i] = f[i + p[i]] + 1, to[i] = to[i + p[i]];
		else f[i] = 1, to[i] = i;
	while (m--) {
		int op, a;
		cin >> op >> a;
		if (op) {
			int sum = 0;
			while (true) {
				sum += f[a];
                a = to[a];
				if (a + p[a] > n) break;
				a += p[a];
			}
			cout << a << " " << sum << endl;
		}
		else {
			cin >> p[a];
			for (int i = r[pos[a]]; i >= l[pos[a]]; i--)
				if (pos[i + p[i]] == pos[i]) f[i] = f[i + p[i]] + 1, to[i] = to[i + p[i]];
				else f[i] = 1, to[i] = i;
		}
	}
	return 0;
}
} // namespace liuzimingc