题解：P8522 [IOI2021] 地牢游戏

· · 题解

看到大于等于 s_i 加上 s_i，考虑应该是倍增分块状物，于是先倍增分块，假设当前能力值处在块 [B^k,B^{k+1}) 中，那么对于任意 s_i < B^k 必定成功，任意 s_i \geq B^{k+1} 必定失败，对于 s_i \in [B^k,B^{k+1}] 的情况不确定，但是这种情况只会成功 B 次。

于是考虑我们认为一次过程是走若干步，在走到过程中能力值始终处在 [B^k,B^{k+1}) 范围内且经过所有的 s_i \in [B^k,B^{k+1}) 的情况必定失败，那么观察到至多 B 个极大过程后所处块会增加，也就是至多进行 \log_{B} V \times B 次极大过程。

找极大过程可以直接考虑倍增，具体而言，对于每个块处理 dp_{u,i},f_{u,i},g_{u,i} 分别表示从 u 出发走 2^i 步，走到的节点，走的过程中能力值的增量与使得走 2^i 步在一个过程中的最大初始值（显然初始值越大越容易在走了若干步后不满足在一次过程中的条件），这一部分是 O(n \times \log_{B} V \times \log V) 的，所以总时间复杂度就是 O(n \times \log_{B} V \times \log V + q \times \log_{B} V \times \log V \times B)。

由于观察到 q 相较 n 要小很多，于是考虑令 B = 64 即可通过。

#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#define lowbit(x) (x&(-x))
//#define bp push_back
//#define sz size
//#define cl clear
const int maxn = 4e5+14;
const int warma = 64;
int dp[6][maxn][25];//在第 i 块中点 u 出发跳 2^j 步抵达的点
long long f[6][maxn][25];//在第 i 块中点 u 出发跳 2^j 步获得加成
long long g[6][maxn][25];//在第 i 块中点 u 出发跳 2^j 步，中途不超过块，遇到 s_i 在块内的必失败，初始节点最大能力值
long long _pow[6];
vector<int> s,p,w,l;
int n;
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L){
    n=N,s=S,p=P,w=W,l=L;
    _pow[0]=1;
    for(int i=1;i<5;i++) _pow[i]=_pow[i-1]*warma;
    _pow[5]=1e18;
    for(int bl=0;bl<5;bl++){
        for(int i=0;i<n;i++) dp[bl][i][0]=(s[i]<_pow[bl]?w[i]:l[i]),f[bl][i][0]=(s[i]<_pow[bl]?s[i]:p[i]),g[bl][i][0]=((_pow[bl]<=s[i]&&s[i]<_pow[bl+1])?min(1ll*s[i]-1,_pow[bl+1]-1):_pow[bl+1]-1);
        for(int j=1;j<25;j++){
            for(int i=0;i<n;i++){
                dp[bl][i][j]=dp[bl][dp[bl][i][j-1]][j-1];
                f[bl][i][j]=f[bl][i][j-1]+f[bl][dp[bl][i][j-1]][j-1];
                g[bl][i][j]=min(g[bl][i][j-1],g[bl][dp[bl][i][j-1]][j-1]-f[bl][i][j-1]);        
            }
            dp[bl][n][j]=n;
            f[bl][n][j]=0;
            g[bl][n][j]=1e18;
        }
    }
    return ;
} 
int chk(long long z){
    int mx=0;
    for(int i=0;i<6;i++){
        if(z>_pow[i]) mx=i;
    }
    return mx;
}
long long ask(int x,long long z,int h){
    for(int i=24;i>=0;i--){
        if(z<=g[h][x][i]) z+=f[h][x][i],x=dp[h][x][i];
    }
    if(x==n) return z;
    if(z>=s[x]) z+=s[x],x=w[x];
    else z+=p[x],x=l[x];
    if(x==n) return z;
    else return ask(x,z,chk(z));
}
long long simulate(int x, int z){
    return ask(x,z,chk(z));
}