P9019 [USACO23JAN] Tractor Paths P

Problem

Luogu P9019 [USACO23JAN] Tractor Paths P

Solution

首先有一个显然的结论，区间 \(i\) 向右能到的区间是 \([i+1,RT_i]\)，向左能到的区间是 \([LT_i,i-1]\)。

根据这个考虑倍增。定义跳一步表示从当前区间去到最远能去的区间。设 \(f_{i,j}\) 表示区间 \(i\) 向右跳 \(j\) 步，最远到哪个区间，\(g_{i,j}\) 表示向左跳。

那么现在只需求出 \(f_{i,0}\) 和 \(g_{i,0}\) 就可以进行倍增。

设 \(l_i\) 表示第 \(i\) 个 L 向左最远到哪个区间，\(r_i\) 表示第 \(i\) 个 R 向右最远到哪个区间。对于 \(l_i\) 来说，只需要求出往右数，最靠近 \(i\) 的 R 是第几个 R，因为 R 越早出现表示对应的 L 也越早出现。这个值就是 \(l_i\)，\(r_i\) 就反过来计算，原理是一样的。

那么 \(f_{i,0}=r_i,g_{i,0}=l_i\)。

然后第一问就很好做了，就倍增往后跳就行了。

第二问设 \(cnt(l,r)\) 表示从 \(l\) 区间到 \(r\) 区间有多少特殊区间。不妨设第一问答案是 \(dis\)。

那么第二问答案 \(ans=cnt(x,x)+cnt(y,y)+\sum\limits_{i=1}^{dis-1} cnt(g_{y,dis-i},f_{x,i})\)。后面那一部分可以合并成几个倍增。所以在倍增中统计前缀和的和？

Code

#include<cstdio>
#include<cstring>
#define N 200005
using namespace std;
int n,q,now,cnt,ans1,ans2,l[N],r[N],sum[N],f[N<<1][18],g[N<<1][18],fs[N<<1][18],gs[N<<1][18];
char s[N<<1],vs[N];
int dis(int x,int y)
{
    if (x==y) return 0;
    int res=0;
    for (int i=17;i>=0;--i)
        if (f[x][i]!=-1&&f[x][i]<y) res+=(1<<i),x=f[x][i];
    return res+1;
}
int main()
{
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    cnt=0;now=1;
    for (int i=1;i<=2*n;++i)
    {
        if (s[i]=='L') cnt++;
        else r[now]=cnt,now++;
    }
    cnt=n+1;now=n;
    for (int i=2*n;i;--i)
    {
        if (s[i]=='R') cnt--;
        else l[now]=cnt,now--;
    }
    scanf("%s",vs+1);
    for (int i=1;i<=n;++i)
        sum[i]=sum[i-1]+vs[i]-'0';
    memset(f,-1,sizeof(f));
    memset(g,-1,sizeof(g));
    for (int i=1;i<n;++i)
        f[i][0]=r[i],fs[i][0]=sum[r[i]];
    for (int i=n;i>1;--i)
        g[i][0]=l[i],gs[i][0]=sum[l[i]-1];
    for (int j=1;j<=17;++j)
        for (int i=1;i<n;++i)
        {
            if (f[i][j-1]==-1) continue;
            f[i][j]=f[f[i][j-1]][j-1];
            if (f[i][j]!=-1) fs[i][j]=fs[i][j-1]+fs[f[i][j-1]][j-1];
        }
    for (int j=1;j<=17;++j)
        for (int i=n;i>1;--i)
        {
            if (g[i][j-1]==-1) continue;
            g[i][j]=g[g[i][j-1]][j-1];
            if (g[i][j]!=-1) gs[i][j]=gs[i][j-1]+gs[g[i][j-1]][j-1];
        }
    while (q--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        ans1=dis(x,y);ans2=vs[x]-'0'+vs[y]-'0';
        for (int i=17;i>=0;--i)
            if ((ans1-1)&(1<<i)) ans2+=fs[x][i],x=f[x][i];
        for (int i=17;i>=0;--i)
            if ((ans1-1)&(1<<i)) ans2-=gs[y][i],y=g[y][i];
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}