专栏文章

题解：P4739 [CERC2017] Donut Drone

__gghack_
P4739题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimz75v0
此快照首次捕获于
2025/12/01 17:57
3 个月前
此快照最后确认于
2025/12/01 17:57
3 个月前
查看原文

前言：

NOIP2025 RP++。

分析：

首先不带修可以直接倍增，不再赘述。
现在带修了，倍增数组要动的就多了，所以我们应该思考怎么减少维护的信息量。
发现无论怎么走都会向右移动一步，考虑怎么利用一下。
我们考虑把路径拆成三段：往右边走直到到达第一列的，走完若干个贯穿全图的循环的，走完剩下步数的。
由于一定会向右移动，所以第一部分和第三部分移动量级是 O(c)\mathcal{O(c)} 的。考虑怎么优化第二部分，发现这一部分可以套用倍增，处理贯穿 2k2^k 次全图后位于第一列哪一行。也就是说，我们只需要快速处理贯穿一次全图后，会位于第一列哪一行即可。
这个显然是可以把路径劈成两半再合并的，暴力每次更新显然不能接受，可以使用线段树优化。具体的，每个节点维护 toxto_x 表示 [l,r][l,r] 列的部分，从 (x,l)(x,l) 进入，到达 (tox,r+1)(to_x,r+1)。维护是简单的，然后做完了。
CPP
# 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行的点会走到哪里即可。
// 发现每次相当于劈开路径再重新拼接，这个好像可以线段树

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...