题解：P4739 [CERC2017] Donut Drone

· · 题解

前言：

NOIP2025 RP++。

分析：

首先不带修可以直接倍增，不再赘述。

现在带修了，倍增数组要动的就多了，所以我们应该思考怎么减少维护的信息量。

发现无论怎么走都会向右移动一步，考虑怎么利用一下。

我们考虑把路径拆成三段：往右边走直到到达第一列的，走完若干个贯穿全图的循环的，走完剩下步数的。

由于一定会向右移动，所以第一部分和第三部分移动量级是 \mathcal{O(c)} 的。考虑怎么优化第二部分，发现这一部分可以套用倍增，处理贯穿 2^k 次全图后位于第一列哪一行。也就是说，我们只需要快速处理贯穿一次全图后，会位于第一列哪一行即可。

这个显然是可以把路径劈成两半再合并的，暴力每次更新显然不能接受，可以使用线段树优化。具体的，每个节点维护 to_x 表示 [l,r] 列的部分，从 (x,l) 进入，到达 (to_x,r+1)。维护是简单的，然后做完了。

# include <bits/stdc++.h>
# define int long long 
# define lid ( id << 1 )
# define rid ( id << 1 | 1 )
using namespace std ;
constexpr int N = 2005 ; 
int n , m , a[N * N] , Q , Rx = 1 , Ry = 1 ; 
int gid ( int x , int y ) { return ( x - 1 ) * m + y ;  }
int sb ( int a , int t ) {
    if ( a >= 1 && a <= t ) return a ; 
    if ( a == 0 ) return t ; if ( a == t + 1 ) return 1 ; 
    return a ; 
}
int nxt ( int x , int y ) {
    int p1 = gid ( x , sb ( y + 1 , m ) ) , 
    p2 = gid ( sb ( x - 1 , n ) , sb ( y + 1 , m ) ) , 
    p3 = gid ( sb ( x + 1 , n ) , sb ( y + 1 , m ) ) ; 
    if ( a[p1] > a[p2] && a[p1] > a[p3] ) return x ; 
    if ( a[p2] > a[p1] && a[p2] > a[p3] ) return sb ( x - 1 , n ) ; 
    if ( a[p3] > a[p1] && a[p3] > a[p2] ) return sb ( x + 1 , n ) ; 
    return 0 ;
}
struct node { int l , r , to[N] ; } tr[N << 2] ; 
void pup ( int id ) {
    for ( int i = 1 ; i <= n ; ++ i ) 
        tr[id].to[i] = tr[rid].to[tr[lid].to[i]] ; 
    return ; 
}
void build ( int id , int l , int r ) {
    tr[id].l = l , tr[id].r = r ;
    if ( l == r ) {
        for ( int i = 1 ; i <= n ; ++ i ) 
            tr[id].to[i] = nxt ( i , l ) ; 
        return ; 
    }
    int mid = ( l + r ) >> 1 ; build ( lid , l , mid ) , build ( rid , mid + 1 , r ) ; 

    return pup ( id ) , void () ;
} 
void alter ( int id , int x ) {
    if ( tr[id].l == tr[id].r && tr[id].l == x ) {
        for ( int i = 1 ; i <= n ; ++ i ) 
            tr[id].to[i] = nxt ( i , tr[id].l ) ; 
        return ; 
    }
    int mid = ( tr[id].l + tr[id].r ) >> 1 ; 
    ( x <= mid ? alter ( lid , x ) : alter ( rid , x ) ) ; 
    return pup ( id ) , void () ;     
}  
int aft[N][31] ; 
signed main () {
    ios::sync_with_stdio ( false ) , cin.tie ( 0 ) , cout.tie ( 0 ) , cin >> n >> m ; 
    for ( int i = 1 ; i <= n ; ++ i ) for ( int j = 1 ; j <= m ; ++ j ) cin >> a[ gid ( i , j ) ] ; 
    build ( 1 , 1 , m ) ; 
    for ( int i = 1 ; i <= n ; ++ i ) aft[i][0] = tr[1].to[i] ;
    for ( int i = 1 ; i < 31 ; ++ i ) for ( int j = 1 ; j <= n ; ++ j ) 
        aft[j][i] = aft[aft[j][i - 1]][i - 1] ; 
    cin >> Q ; while ( Q -- ) {
        string op ; cin >> op ; 
        if ( op == "move" ) {
            int k ; cin >> k ; 
            while ( k && Ry != 1 ) Rx = nxt ( Rx , Ry ) , ++ Ry , Ry = sb ( Ry , m ) , -- k ; 
            for ( int j = 30 ; ~ j ; -- j ) {
                int step = m * ( 1ll << j ) ; 
                if ( k - step < 0 ) continue ;
                k -= step , Rx = aft[Rx][j] ;  
            }
            while ( k ) Rx = nxt ( Rx , Ry ) , ++ Ry , Ry = sb ( Ry , m ) , -- k ; 
            cout << Rx << " " << Ry << "\n" ;
        }
        if ( op == "change" ) {
            int x , y , e ; cin >> x >> y >> e  ; 
            a[ gid ( x , y ) ] = e ; 
            alter ( 1 , sb ( y - 1 , m ) ) ; 
            for ( int i = 1 ; i <= n ; ++ i ) aft[i][0] = tr[1].to[i] ;
            for ( int i = 1 ; i < 31 ; ++ i ) for ( int j = 1 ; j <= n ; ++ j ) 
            aft[j][i] = aft[aft[j][i - 1]][i - 1] ; 
        }
    }   
    return 0 ;
}
// 简单的做法是根据修改裂成若干可以倍增的段，可以过，但是很慢。
// 一个重要观察是每次一定向右边走，可以将路程分成bf+rep+bf
// 那么只需要处理一个第一列第k行的点会走到哪里即可。
// 发现每次相当于劈开路径再重新拼接，这个好像可以线段树