自动搬运

查看原文

来自洛谷，原作者为

	Mars_Dingdang 最怕你一生碌碌无为，却总安慰自己平凡可贵

搬运于2025-08-24 22:39:48，当前版本为作者最后更新于2024-01-16 16:26:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不理解啊，LOJ 上一发就过了，但是洛谷上一直被卡常。

题目大意

有 $n$ 个人，$n+1$ 个位置，一开始第 $i$ 个人在 $i$（编号从 $0$ 开始），能力值为 $s_i$。

$q$ 次询问，每次你初始在 $x$，能力值为 $z$。如果你能力值不小于当前位置人的能力值，那么你的能力值增加 $s_i$ 并且前往位置 $w_i$；否则你的能力值增加 $p_i$ 并前往位置 $l_i$。当你走到 $n$ 位置时游戏结束。求此时你的能力值。

$n\le 4\times 10^5$。

大体思路

最近新学习了倍增值域分块。

我们将能力值的值域分成 $[2^{\omega},2^{\omega+1})$。

对于一个 $s_i\le 2^{\omega}$ 的位置，我们显然会获胜。对于一个 $s_i\ge 2^{\omega+1}$ 的位置，我们显然会失败；而对于 $s_i\in [2^{\omega},2^{\omega+1})$ 的位置，在获胜后显然会前往下一个块。

我们可以对每一个块维护以下几个值：$gain$ 表示收获的能力值，$lim$ 表示战胜一个对手至少需要的能力值。

然后我们发现，我们的移动是每次往后跳一个位置。这样太劣了，考虑倍增，对每一个位置 $i$ 开始，在每一个块 $\omega$ 中都开一个倍增数组表示往后跳 $2^j$ 步。

初始的时候 $to(i,\omega,0)=w_i$ 或 $l_i$，$gain$ 和 $lim$ 赋值如上文所述。预处理倍增数组即可。

查询的时候，每次倍增往后跳必败或者必胜，最后遇到一个位置再基于 $s_i$ 判断胜负即可。这样的判断至多 $O(\log V)$ 次，单次复杂度为 $O(\log n\log V)$。

然而一开始被卡常了。一种是相信答案步数不会太多，倍增跳的时候可以开小一点；一种是倍增值域分块的 $Base$ 设置得大一点，减少预处理时候的块数。具体实现可以参考代码。

#include <iostream>
#include <cstdio>
#include <vector>
// using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
// typedef unsigned long long ull;
// typedef double db;
// typedef std::pair<int, int> PII;
const int maxn = 4e5 + 5, Omega = 5, Bits = 17;
const ll inf = 1e18, Base = 32;
template <typename T>
inline void chkmax(T &x, T y) {x = (x > y ? x : y);}
template <typename T>
inline void chkmin(T &x, T y) {x = (x < y ? x : y);}
namespace IO_ReadWrite {
	#define re register
	#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
	char _buf[1<<21], *p1 = _buf, *p2 = _buf;
	template <typename T>
	inline void read(T &x){
		x = 0; re T f=1; re char c = gg;
		while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
		while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
		x *= f;return;
	}
	inline void ReadChar(char &c){
		c = gg;
		while(!isalpha(c)) c = gg;
	}
	template <typename T>
	inline void write(T x){
		if(x < 0) putchar('-'), x = -x;
		if(x > 9) write(x/10);
		putchar('0' + x % 10);
	}
	template <typename T>
	inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
int n; std::vector<int> s, p, w, l;
int to[maxn][9][20];
ll lim[maxn][9][20], gain[maxn][9][20], P[9];
inline ll Min(ll a, ll b) {return a < b ? a : b;}
void init(int _n, std::vector <int> _s, std::vector <int> _p, std::vector <int> _w, std::vector <int> _l) {
	n = _n; s = _s, p = _p, w = _w, l = _l;
//	rep(i, 0, n - 1) s[i] = _s[i], p[i] = _p[i], w[i] = _w[i], l[i] = _l[i];
	P[0] = 1;
	rep(i, 1, Omega) P[i] = P[i - 1] * Base;
	rep(omega, 0, Omega) {
		rep(i, 0, n - 1) {
			if(P[omega] >= s[i]) {
				w[i] == n ? to[i][omega][0] = -1 : to[i][omega][0] = w[i], lim[i][omega][0] = inf, gain[i][omega][0] = s[i];
			}
			else {
				l[i] == n ? to[i][omega][0] = n : to[i][omega][0] = l[i], lim[i][omega][0] = s[i], gain[i][omega][0] = p[i];
			}
		}
	}
	rep(omega, 0, Omega) {
		rep(j, 1, Bits) {
			rep(i, 0, n - 1) {
				if(to[i][omega][j - 1] == -1 && to[to[i][omega][j - 1]][omega][j - 1] == -1) {
					to[i][omega][j] = -1;
					continue;
				}
				to[i][omega][j] = to[to[i][omega][j - 1]][omega][j - 1];
				gain[i][omega][j] = gain[i][omega][j - 1] + gain[to[i][omega][j - 1]][omega][j - 1];
				lim[i][omega][j] = Min(lim[i][omega][j - 1], lim[to[i][omega][j - 1]][omega][j - 1] - gain[i][omega][j - 1]);
			}
		}
	}
} 
//int omega;
ll simulate(int x, int z) {
	ll res = z; int omega = 0;
	while(x != n) {
		while(omega + 1 <= Omega && P[omega + 1] <= res) ++ omega;
		Rep(j, Bits, 0) {
			if(to[x][omega][j] == -1) continue;
			(res < lim[x][omega][j] ? res += gain[x][omega][j], x = to[x][omega][j] : 1);
		}
		res >= s[x] ? (res += s[x], x = w[x]) : (res += p[x], x = l[x]);
	}
	return res;
}