题解【P3098】[USACO13DEC]The Bessie Shuffle G

· · 题解

发现顺推需要考虑非常多的东西，不妨来试试倒推。设 Pre_i 表示现在的第 i 张牌是上一轮的第 Pre_i 张牌。以样例为例，Pre_1=2,Pre_2=3,Pre_3=1。

如果一张牌它现在是第一位（也就是要被淘汰了），那么它上一轮就在第 Pre_1+1=3 位（因为上一轮也淘汰了一个，所以要加上 1），上上轮就在第 Pre_3+1=2 位，以此类推，倒数第三轮它就到了第 4 位，走出了洗牌环节。再后来，每往后一轮它就会往后一位，直到第一轮洗牌完后停止。

这个东西可以用倍增来处理，设 f(i,j) 表示现在在第 i 位的牌往后 2^j 轮后的位置。特别地，f(i,j)=m+1 表示它走出了洗牌环节。

这样，对于每一个询问，我们只要知道它要被淘汰时 / 到最后一轮洗牌的开始位置，再往前推，就可以得到它的初始位置。分两种情况讨论：

时间复杂度 O(m\log n+q\log^2n)。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=1e5;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

int n,m,q,P[Maxn+5],Pre[Maxn+5];
int f[Maxn+5][40]; // 倍增数组

inline int Check(int x,int y,int z)
{
    if(y==z+1) return 1;
    Rof(i,30,0)
        if(y>=(1<<i)) x=f[x][i],y-=(1<<i);
    return (x==m+1);
}
inline int Count(int x)
{
    int Rnd=min(n-m,n-x); // 需要进行的轮数
    int l=1,r=Rnd+1,Start=(x<m)?m-x+1:1; // Start:开始位置
    while(l<r)
    {
        int mid=(l+r)/2;
        if(Check(Start,mid,Rnd)) r=mid;
        else l=mid+1;
    }
    if(l==Rnd+1) // 没有走出去
    {
        x=Start;
        Rof(i,30,0)
            if(Rnd>=(1<<i)) x=f[x][i],Rnd-=(1<<i);
        return Pre[x];
    }
    else return min(n,m+1+Rnd-l); // 走出去了
}

int main()
{
    n=read(),m=read(),q=read(),Pre[m+1]=m+1;
    For(i,1,m) P[i]=read(),Pre[P[i]]=i;
    For(i,1,m+1) f[i][0]=min(m+1,Pre[i]+1);
    For(j,1,30)
        For(i,1,m+1) f[i][j]=min(m+1,f[f[i][j-1]][j-1]);
    while(q--)
    {
        int x=read();
        printf("%d\n",Count(x));
    }
    return 0;
}