自动搬运

查看原文

来自洛谷，原作者为

	PersistentLife **

搬运于2025-08-24 22:44:39，当前版本为作者最后更新于2023-02-04 23:17:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【USACO23JAN_Pt T1】Tractor Paths

cnblogs

容易发现，对于每个区间 $i$，存在一个数 $R_i$ 满足 $i$ 能往右跳到 $[i+1,R_i]$ 中的所有区间，且 $R_i$ 递增；类似的存在一个数 $L_i$ 满足 $i$ 往左能跳到 $[i-1,L_i]$ 中的所有区间，且 $L_i$ 递增。

第一问是简单的，倍增求解即可。

第二问考虑枚举在跳第几步的时候离开最优路径去走到一个关键点。令 $f(k,i)$ 表示从 $i$ 往右跳 $k$ 步最大跳到的编号是什么， $g(k,i)$ 表示 $i$ 往左跳 $k$ 步最小跳到的编号是多少，$cnt(l,r)$ 表示编号在 $[l,r]$ 之间有多少个关键点，第一问的答案是 $dis$。则第二问的答案是 $cnt(a,a)+cnt(b,b)+\sum_{i=1}^{ans-1} cnt(g(b,ans-i),f(a,i))$。这些区间是不交的（如果两个区间有交，则 $dis$ 并不是最短路径），拆成前缀和用倍增维护即可，复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,Q;
char S[400005],W[400005];
int L[200005],R[200005];
int bl[200005],sum[200005];
int f[18][200005],g[18][200005];
int dist(int u,int v)
{
	if(u==v) return 0;
	int ans=0;
	for(int k=17;k>=0;k--) if(f[k][u]!=-1&&f[k][u]<v) ans+=(1<<k),u=f[k][u];
	return ans+1; 
}
int sr[18][200005],sl[18][200005];
void solve()
{
	scanf("%d%d",&n,&Q);
	scanf("%s",S+1);
	int cntL=0,nowL=1;
	for(int i=1;i<=2*n;i++)
	{
		if(S[i]=='L') cntL++;
		else R[nowL]=cntL,nowL++;
	}
	int cntR=n+1,nowR=n;
	for(int i=2*n;i>=1;i--)
	{
		if(S[i]=='R') cntR--;
		else L[nowR]=cntR,nowR--;
	}
	scanf("%s",W+1);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+W[i]-'0';
	memset(f,-1,sizeof(f)),memset(g,-1,sizeof(g));
	for(int i=1;i<n;i++) f[0][i]=R[i],sr[0][i]=sum[R[i]];
	for(int i=n;i>=2;i--) g[0][i]=L[i],sl[0][i]=sum[L[i]-1];
	for(int k=1;k<18;k++) for(int i=1;i<n;i++) if(f[k-1][i]!=-1) 
	{
		f[k][i]=f[k-1][f[k-1][i]];
		if(f[k][i]!=-1) sr[k][i]=sr[k-1][i]+sr[k-1][f[k-1][i]];
	}
	for(int k=1;k<18;k++) for(int i=n;i>=2;i--) if(g[k-1][i]!=-1)
	{
		g[k][i]=g[k-1][g[k-1][i]];
		if(g[k][i]!=-1) sl[k][i]=sl[k-1][i]+sl[k-1][g[k-1][i]];
	}
	while(Q--)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		int ans1=dist(u,v),ans2=0;
		ans2+=W[u]-'0'+W[v]-'0';
		for(int k=17;k>=0;k--) if((ans1-1)&(1<<k)) ans2+=sr[k][u],u=f[k][u];
		for(int k=17;k>=0;k--) if((ans1-1)&(1<<k)) ans2-=sl[k][v],v=g[k][v];
		printf("%d %d\n",ans1,ans2);
	}
}
signed main()
{
	int _=1;
//	cin>>_;
	while(_--) solve();
	return 0;
}