P9019 [USACO23JAN] Tractor Paths P 题解

难度其实绝对不止蓝题。

先考虑第一问。维护任意两点之间的最短路是困难的，难以 dp 或是采取其它方法解决。难以算最短路就转换思路，考虑从 \(x\) 走 \(p\) 步能走到哪。考虑到这个东西是有单调性的，也就是说对于 \(x<y<z\)，从 \(x\) 能走到 \(z\) 一定能从 \(x\) 走到 \(y\)。那么这个东西可以倍增解决。设 \(f_{i,j}\) 表示从 \(i\) 走 \(2^j\) 步最远能到哪里，倍增转移就可以了。

对于第二问，simple 的想法是枚举 "特殊点" \(i\)，检查是否有 \(dis(x,i)+dis(i,y)=dis(x,y)\)。这样就有了 \(O(n^2)\) 的做法。对于正解，考虑优化，发现这样做复杂度不优的原因是枚举一个 \(i\) 的同时本质上还枚举了其它的 "特殊点"。考虑复杂度 \(O(n\log n)\) 怎么做。显然的想法是仍然要用倍增优化。发现可行的点集形成一个区间，于是我们设 \(p_{i,j}\) 表示从 \(i\) 向前走 \(2^j\) 步最远可以到的 "特殊点" 的个数，\(q_{i,j}\) 表示从 \(i\) 向后走 \(2^j\) 步最远可以到的 "特殊点" 的个数，那么对于 \(x\rightarrow y\)，距离为 \(d\)，答案就是 \(\sum p_{x,k}-q_{y,d-k}\) 这样一个东西。那么这个东西看上去不好维护，然而考虑对于 \(j\) 这一维前缀和处理，表示 \([i,i+2^0],[i,i+2^1],\cdots,[i,i+2^j]\) 所有区间的特殊点个数和，这样一来事实上维护了从 \(1\) 到最终距离的总和，于是用两个前缀和相减就得到了答案。

代码：

#include <bits/stdc++.h>
#define N 200005
#define M 20
using namespace std;
int n, q;
string s, S;
int ls[N], lt, rs[N], rt;
int rk[N << 1];
int sum[N]; 

int f[N][M], g[N][M];
int sf[N][M], sg[N][M];

int get_dis(int x, int y) {
	int ans = 0;
	for (int i = M - 1; ~i; --i)
		if (f[x][i] < y)
			x = f[x][i], ans += (1 << i);
	return ans + 1;
}
int main() {
	cin >> n >> q;
	cin >> s;
	s = " " + s;
	for (int i = 1; i <= (n << 1); i++) {
		if (s[i] == 'L')
			ls[++lt] = i, rk[i] = lt;
		else
			rs[++rt] = i, rk[i] = rt;
	}
	cin >> S;
	S = " " + S;
	for (int i = 1; i <= n; i++)
		sum[i] = sum[i - 1] + S[i] - '0';
	for (int i = 1; i <= n; i++) {
		int l = i, r = n, mid = 0, as = 0;
		while (l <= r) {
			mid = (l + r) >> 1;
			if (ls[mid] <= rs[i])
				as = mid, l = mid + 1;
			else
				r = mid - 1; 
		}
		f[i][0] = as;
		sf[i][0] = sum[as];
		l = 1, r = i, mid = 0, as = 0;
		while (l <= r) {
			mid = (l + r) >> 1;
			if (rs[mid] >= ls[i])
				as = mid, r = mid - 1;
			else
				l = mid + 1;
		}
		g[i][0] = as;
		sg[i][0] = sum[as - 1];
	}
	for (int j = 1; j < M; j++)
		for (int i = 1; i <= n; i++) {
			f[i][j] = f[f[i][j - 1]][j - 1];
			sf[i][j] = sf[i][j - 1] + sf[f[i][j - 1]][j - 1];
			g[i][j] = g[g[i][j - 1]][j - 1];
			sg[i][j] = sg[i][j - 1] + sg[g[i][j - 1]][j - 1];
		}
	while (q--) {
		int x, y;
		scanf("%d%d", &x, &y);
		int ds = get_dis(x, y);
		cout << ds << " ";
		int ans = S[x] + S[y] - 2 * '0';
		for (int i = M - 1; ~i; --i)
			if (((ds - 1) >> i) & 1) {
				ans += sf[x][i];
				x = f[x][i];
				ans -= sg[y][i];
				y = g[y][i];
			}				
		cout << ans << "\n";
	}
	return 0;
}