自动搬运

查看原文

来自洛谷，原作者为

	Graphcity 循此苦旅，终抵繁星。

搬运于2025-08-24 21:45:18，当前版本为作者最后更新于2021-10-03 16:57:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

发现顺推需要考虑非常多的东西，不妨来试试倒推。设 $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;
}