「地牢」

题目

点击此处查看标题。

分析

将基本观察与奇异的优化问题进行比较是值得一试的。

算法 1

复杂度为\(0(QS)\)的直接模拟。

算法 2

移动的重复过程相当多，你可以想到使用倍增压缩.

为失败案例写一个乘数，得到子任务3的分数。为win写一个乘数，得到Subtask2的分数。

算法 3

单纯将移动过程翻倍，优化效果不明显。注意，\(z\)只需要考虑当\(\max s\)时的限制，当\(z\ge\max s\)时，图是确定的,只是直接相乘。

一个容易想到的方向就是找一个特殊的进程，这样这个进程之后的\(z'\)保证可以达到\(z\)的某个倍数，从而完成执行复杂度的分析。我们不能很快注意一件事：当\(z\ge s_x\)时，我们不会添加随机数，而恰恰是 \(s_x\).事实上，这意味着我们\(z'\ge 2s_x\)。

我们找到了“双重”关系。虽然和我们想要的不完全一样，但是已经可以带来一些启发了。——我们可以对于 \(z\) 按照 2 的次幂划分阶段.我们面前有两种情况：当没有像\(z\ge s_x\)这样的转会时，图的形态可以确定，也就意味着可以预处理;另一方面，如果我们遇到像\(z\ge s_x\)这样的转会，我们只需要一步就可以进入下一阶段。

具体地说，我们构造了一个\(G_t\)，它表示当\(z \u in[2t，2 { t ^ 1 })\)时没有\(z \u ge s _ x \)过渡的图的形状。因此，对于\ (s _ x2 t \)，我们连接边\(x \u overset { s \u right arrow } w \u x \)，而对于\(s \u x \u ge2t \)，我们连接\(x \u overset)这样，在一定的\(G \u t \)下，我们可以相乘并加速转移。跨阶段情况最多出现\(\log s\)次。

需要注意的是，当\(t \ ge \ l floor \ log _ 2 \ max s \ r floor \)时，图上没有丢失边，而且\(z\)不再受权重影响，所以乘法的上界是\(\log_2 n\)而不是\(。

该算法的复杂度为\(o((n ^ q)\ log 2s)\)。它似乎没有通过，但请注意，复杂性可以在\(n\)和\(q\)之间平衡，因此我们可以适当调低倍增上界,从而减少预处理时间和增加查询时间，这样我们就可以卡住。

总结：

注意观察问题的特殊性,尤其是与常见条件不同的地方,这些往往是设定的突破点。在某种程度上，解决(人为)问题也能反映提问者的意图。

注意这个“模拟”问题背后的值限制，我们经常可以找到一个令某个特征值“翻倍”的过程,来分析a \(O(\log x)\)的复杂性。

学习如何调整和倍增平衡复杂度.

算法 4

在NOIP之前写下这个解决方案。目前看来这部分算法在实战中价值不大。先简单写一下。

请注意，\(G_t\)和\(G _ { t } \)之间有许多重复和一些差异。基于此，我们可以发现每个图上的“关键”点——是两个图上的出边有区别的点。如果我们不能模拟这些关键点，那么在 \(G_t\) 和 \(G_{t+1}\) 上模拟是一致的;不然，我们就相当于确定了起点。这时候单独把关键点相乘会简单很多。

最终得到了o (n \ log s q \ log 2s)的算法。

代码

算法 3

void Init(){ 0

MX=0；

rep(i，1，N ) mx=MAX(mx，S[I])；

lg2=log2(MX)；

//lg2=max{ x | 2^x=mx }

//所以2^{lg2 1} mx为sur

e
rep( t, 0, lg2 ) {
rep( i, 1, N ) {
int upper = ( 1 ( t + 1 ) ) - 1;
if( S[i] ( 1 t ) ) {
go[t][i][0] = W[i];
gain[t][i][0] = S[i];
lim[t][i][0] = upper - S[i];
} else {
go[t][i][0] = L[i];
gain[t][i][0] = P[i];
lim[t][i][0] = MAX( 0, MIN( S[i] - 1, upper - P[i] ) );
}
}
lim[t][N + 1][0] = 0;
gain[t][N + 1][0] = 0;
go[t][N + 1][0] = N + 1;
rep( j, 1, lg2 ) rep( i, 1, N + 1 ) {
go[t][i][j] = go[t][go[t][i][j - 1]][j - 1];
gain[t][i][j] = gain[t][i][j - 1] + gain[t][go[t][i][j - 1]][j - 1];
lim[t][i][j] = MAX( 0ll, MIN( ( LL ) lim[t][i][j - 1], lim[t][go[t][i][j - 1]][j - 1] - gain[t][i][j - 1] ) );
}
}
int t = lg2 + 1;
rep( i, 1, N )
go[t][i][0] = W[i],
gain[t][i][0] = S[i];
gain[t][N + 1][0] = 0;
go[t][N + 1][0] = N + 1, fin = log2( N );
rep( j, 1, fin ) rep( i, 1, N + 1 ) {
go[t][i][j] = go[t][go[t][i][j - 1]][j - 1];
gain[t][i][j] = gain[t][i][j - 1] + gain[t][go[t][i][j - 1]][j - 1];
}
}
LL Simulate( int x, LL z ) {
for( int t = ( int ) log2( z ) ; t = lg2 ; t ++ ) {
for( int i = lg2 ; ~ i ; i -- )
if( z = lim[t][x][i] )
z += gain[t][x][i],
x = go[t][x][i];
if( x == N + 1 ) break;
if( S[x] ( 1 t ) || z = S[x] )
z += S[x], x = W[x];
else if( z S[x] )
z += P[x], x = L[x];
}
if( x != N + 1 ) {
int t = lg2 + 1;
for( int i = fin ; ~ i ; i -- )
if( go[t][x][i] != N + 1 )
z += gain[t][x][i], x = go[t][x][i];
z += S[x];
}
return z;
}

算法 4

#include cmath
#include cstdio
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 4e5 + 5, MAXLOG = 25;
templatetypename _T
void read( _T x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s  '0' || '9'  s ) { f = s == '-', s = getchar(); }
    while( '0' = s  s = '9' ) { x = ( x  3 ) + ( x  1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}
templatetypename _T
void write( _T x ) {
    if( x  0 ) putchar( '-' ), x = -x;
    if( 9  x ) write( x / 10 );
    putchar( x % 10 + '0' );
}
templatetypename _T
_T MIN( const _T a, const _T b ) {
    return a  b  a : b;
}
templatetypename _T
_T MAX( const _T a, const _T b ) {
    return a  b  a : b;
}
LL gain[MAXN][MAXLOG];
int go[MAXN][MAXLOG];
LL jmp[MAXN][MAXLOG];
int nxt[MAXN][MAXLOG], lim[MAXN][MAXLOG];
LL wei[MAXN][MAXLOG];
int bound[MAXN][MAXLOG], tar[MAXN][MAXLOG];
bool vis[MAXN];
int S[MAXN], P[MAXN], W[MAXN], L[MAXN];
int up, dn;
int N, Q, lg2, fin;
void DFS( const int u, const int t ) {
    if( ~ tar[u][t] || vis[u] ) return ;
    vis[u] = true;
    if( S[u]  ( 1  t ) ) {
        DFS( W[u], t );
        tar[u][t] = tar[W[u]][t];
        wei[u][t] = wei[W[u]][t] + S[u];
        bound[u][t] = MAX( 0, MIN( up - 1, bound[W[u]][t] ) - S[u] );
    } else {
        DFS( L[u], t ); 
        tar[u][t] = tar[L[u]][t]; 
        wei[u][t] = wei[L[u]][t] + P[u];
        bound[u][t] = MAX( 0, MIN( S[u] - 1, MIN( up - 1, bound[L[u]][t] ) - P[u] ) );
    }
}
void Init() {
    int mx = 0;
    for( int i = 0 ; i  N ; i ++ )
        mx = MAX( mx, S[i] );
    lg2 = log2( mx ), fin = log2( N );
    for( int t = 0 ; t = lg2 ; t ++ ) {
        up = ( 1  ( t + 1 ) ), dn = 1  t;
        for( int i = 0 ; i = N ; i ++ )
            tar[i][t] = -1, bound[i][t] = 0, vis[i] = false;
        for( int i = 0 ; i = N ; i ++ )
            if( i == N || ( dn = S[i]  S[i]  up ) )
                tar[i][t] = i, wei[i][t] = 0, bound[i][t] = INF;
        for( int i = 0 ; i = N ; i ++ ) DFS( i, t );
        for( int i = 0 ; i  N ; i ++ )
            if( dn = S[i]  S[i]  up ) {
                if( ~ tar[L[i]][t] ) {
                    nxt[i][0] = tar[L[i]][t]; 
                    jmp[i][0] = P[i] + wei[L[i]][t];
                    lim[i][0] = MAX( 0, MIN( MIN( up - 1 - P[i], S[i] - 1 ), 
                                             bound[L[i]][t] - P[i] ) );
                } else
                    nxt[i][0] = -1, jmp[i][0] = 0, lim[i][0] = 0;
            }
    }
    nxt[N][0] = N, lim[N][0] = 0;
    for( int j = 1 ; j = lg2 ; j ++ )
        for( int i = 0 ; i = N ; i ++ ) {
            int p = nxt[i][j - 1];
            if( p == -1 || nxt[p][j - 1] == -1 ) {
                nxt[i][j] = -1;
                jmp[i][j] = lim[i][j] = 0;
                continue;
            }
            nxt[i][j] = nxt[p][j - 1];
            jmp[i][j] = jmp[i][j - 1] + jmp[p][j - 1];
            lim[i][j] = MAX( 0ll, MIN( ( LL ) lim[i][j - 1], lim[p][j - 1] - jmp[i][j - 1] ) );
        }
    gain[N][0] = 0, go[N][0] = N;
    for( int i = 0 ; i  N ; i ++ )
        gain[i][0] = S[i], go[i][0] = W[i];
    for( int j = 1 ; j = fin ; j ++ )
        for( int i = 0 ; i = N ; i ++ )
            go[i][j] = go[go[i][j - 1]][j - 1],
            gain[i][j] = gain[i][j - 1] + gain[go[i][j - 1]][j - 1];
}
LL Query( int x, LL z ) {
    for( int t = 0 ; t = lg2 ; t ++ ) {
        if( z = ( 1  ( t + 1 ) ) ) continue;
        if( z  bound[x][t] || tar[x][t] == -1 ) continue;
        z += wei[x][t], x = tar[x][t];
        for( int i = lg2 ; ~ i ; i -- )
            if( ~ nxt[x][i]  z = lim[x][i] ) 
                z += jmp[x][i], x = nxt[x][i];
        if( x == N ) break;
        if( z  S[x] ) z += P[x], x = L[x];
        else z += S[x], x = W[x];
    }
    if( x != N ) {
        for( int i = fin ; ~ i ; i -- )
            if( go[x][i] != N )
                z += gain[x][i], x = go[x][i];
        z += S[x];
    }
    return z;
}
int main() {
    freopen( "reflection.in", "r", stdin );
    freopen( "reflection.out", "w", stdout );
    read( N ), read( Q );
    for( int i = 0 ; i  N ; i ++ ) read( S[i] );
    for( int i = 0 ; i  N ; i ++ ) read( P[i] );
    for( int i = 0 ; i  N ; i ++ ) read( W[i] );
    for( int i = 0 ; i  N ; i ++ ) read( L[i] );
    Init();
    while( Q -- ) {
        int a, b;
        read( a ), read( b );
        write( Query( a, b ) ), putchar( '\n' );
    }
    return 0;
}