IOI2021
Mars_Dingdang
·
·
题解
不理解啊，LOJ 上一发就过了，但是洛谷上一直被卡常。
题目大意
有 n 个人，n+1 个位置，一开始第 i 个人在 i（编号从 0 开始），能力值为 s_i。
$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$ 设置得大一点，减少预处理时候的块数。具体实现可以参考代码。
```cpp
#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;
}
```