UOJ #664. 【IOI2021】dungeons

题面传送门
很容易发现这个题目的特殊点是打败一个敌人就可以加上它的能力值。
也就是说如果我们以\([2^i,2^{i+1}]\)分段，那么如果我们打败了一个段里面的一个敌人那么就可以上一个段。
不难想到对于每个段处理一个倍增数组，并在倍增时维护一个值\(G\)表示只有当前能力值小于等于\(G\)才能继续走。一旦停下要么是可以晋级，要么走到了终点。
时间复杂度\(O(n\log^2V+q\log^2V)\)
然后你发现不对劲，空间复杂度\(O(n\log^2V)\)根本过不去。
考虑改变分段的基数，发现如果以\([B^i,B^{i+1}]\)分段，那么一个段内会停下\(B\)次。
所以时间复杂度为\(O(n\log_{B}V\log V+qB\log V\log_{B}V)\)，实测取\(B=26\)最优。
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N 400000
#define M 500000
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-5)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (m*x+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound  
using namespace std;
int n,m,k,fa[6][25][N+5],S[N+5],P[N+5],W[N+5],L[N+5];ll Z,Up[30],G[6][25][N+5],F[6][25][N+5];const int B=26;
void init(int m,vector s,vector p,vector w,vector l) {
	RI i,j,h;n=m;for(i=0;iUp[i-1]?L[j]:W[j]);F[i][0][j]=(S[j]>Up[i-1]?P[j]:S[j]);
			G[i][0][j]=(S[j]>Up[i-1]&&S[j]<=Up[i]?min(S[j]-1,Up[i]-F[i][0][j]):Up[i]-F[i][0][j]);fa[i][0][j]==n&&(G[i][0][j]=-1e18);
		}
		for(j=1;j<=24;j++)for(h=0;hUp[i]){i++;continue;}if(x==n) return Z;//cerr<=S[x]?(Z+=S[x],x=W[x]):(Z+=P[x],x=L[x]);
	}
}