【USACO23JAN_Pt T1】Tractor Paths 题解

· · 题解

【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;
}