[AtCoder Regular Contest 060] E - Tak and Hotels

problem

luogu翻译

solution - 分块

肯定刚开始，我们很想暴力跳过去。事件复杂度取决于数据。

肯定不做把头拿给别人砍的事

这种跳法，让我想到了是否可以分块。

我又联想到了之前做的一道维护每个点跳出本块的下一个点信息CF1491H。

这里也这么做，暴力分块。

• 首先维护出每个点跳一步能最远跳多少，采取二分（另一尺取指针做法在倍增板块实现）

  用来在块内暴力互跳。

• 然后维护出每个点最少需要跳多少步才能跳出所属块，以及跳出的位置。

  从每个点开始一步一步跳，最多跳块长 $\sqrt{n}$ 步就跳出块了。

后面查询的时候，先把起点跳到终点的块内，这一过程最多暴力跳 $\sqrt{n}$ 个整块。

然后再暴力在一个块内跳到终点，这一过程最多暴力跳块长，也是 $\sqrt{n}$ 的。

时间复杂度 $O(n\log n+n\sqrt{n}+q\sqrt{n})$。

code - 分块

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
int n, Q, L;
int x[maxn], to[maxn], block[maxn], w[maxn], g[maxn];

int find( int pos ) {
	int l = pos + 1, r = n, ans = pos + 1;
	while( l <= r ) {
		int mid = ( l + r ) >> 1;
		if( x[mid] - x[pos] <= L ) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}

int main() {
	scanf( "%d", &n );
	for( int i = 1;i <= n;i ++ ) scanf( "%d", &x[i] );
	scanf( "%d %d", &L, &Q );
	for( int i = 1;i <= n;i ++ ) to[i] = find( i );
	int B = sqrt( n ), cnt = n / B + ( n % B != 0 );
	for( int i = 1;i <= n;i ++ ) block[i] = ( i - 1 ) / B + 1;
	for( int i = 1;i <= n;i ++ ) {
		int k = i, ans = 0;
		while( block[k] == block[i] ) k = to[k], ans ++;
		w[i] = ans, g[i] = k;
		if( i >= B * ( cnt - 1 ) + 1 ) w[i] --, g[i] --;
	}
	while( Q -- ) {
		int u, v, ans = 0;
		scanf( "%d %d", &u, &v );
		if( u > v ) swap( u, v );
		while( block[u] < block[v] ) ans += w[u], u = g[u];
		while( u < v ) ans ++, u = to[u];
		printf( "%d\n", ans );
	}
	return 0;
}

solution - 倍增

设 $f_{i,j}:i$ 点开始跳 $2^k$ 步最远能跳到哪儿。

初始化，就指针不断尺取扫，当 $i$ 增加时，指针只会右移，时间是线性的。

$f_{i,j}\leftarrow f_{f_{i,j-1},j-1}$ 预处理倍增数组。

后面直接跳就行了。

时间复杂度 $O(q\log n)$。

code - 倍增

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
int n, L, Q;
int x[maxn];
int f[maxn][20];

int main() {
	scanf( "%d", &n );
	for( int i = 1;i <= n;i ++ ) scanf( "%d", &x[i] );
	scanf( "%d %d", &L, &Q );
	for( int i = 1, k = 1;i <= n;i ++ ) {
		while( k < n and x[k + 1] - x[i] <= L ) k ++;
		f[i][0] = k;
	}
	for( int j = 1;( 1 << j ) <= n;j ++ )
		for( int i = 1;i + ( 1 << j ) - 1 <= n;i ++ )
			f[i][j] = f[f[i][j - 1]][j - 1];
	while( Q -- ) {
		int a, b, ans = 0;
		scanf( "%d %d", &a, &b );
		if( a > b ) swap( a, b );
		for( int i = 16;~ i;i -- ) 
			if( f[a][i] and f[a][i] < b ) ans += ( 1 << i ), a = f[a][i];
		printf( "%d\n", ans + 1 );
	} 
	return 0;
}