YACS20223月-洗牌

给定一个整数 n ，表示 n 张牌，牌的编号为 1 到 n 。

再给定一个洗牌置换 f_1,f_2 …,fn，进行一次洗牌操作时，应将第一号位置的牌交换到第 f_1 号位置，将第 i 号位置的牌交换到第 f_i 号位置。保证 ff 是一个 1 到 n 的排列（即 1 到 n 中的每个数字出现且只出现一次）。

一开始，牌的顺序为 1,2,⋯,n。给定一个整数 k，请输出经过 k 次洗牌后牌的顺序。

前置知识（倍增）：

举个例子，给定n个数，每次求一段连续范围的最小值，一共k次，如果直接暴力时间复杂度为O(nk)。但是实际上有更快的方式。

我们可已考虑对每个数求它之后2^{i的最小值（2}i格中包含他自己，下文所有之后也都一样），然后答案可有至多log2(n)个叠加而求出来，这个可以进行预处理，我们姑且叫它f数组。

举个例子：

n=6,k=2

数列：4 2 6 1 6 3

询问：1_4,24

所有f[k][0]=a[k]，这是因为k之后2^0=1个，只有他自己，所以最小值就是他自己。

对于所有f[k][1]=min(f[k][0],f[k+1][0])推出，远离不难理解就是k之后2^0个与k+20之后2^0个叠加起来，特别地，对于6他没有f[6][1]（他之后没有2个了）。

类似的对于所有f[k][2]=min(f[k][1],f[k+2][1]),4~6没有f[k][2]

而对于最后的答案：

第一个1~4的最小值可以直接而由f[1][2]得出为1

第二个2~5的最小值可以由min(f[2][1],f[5][0])得出为1

image

#include<bits/stdc++.h>

using namespace std;

int n,m,a[100005],f[100005][25];

int main(){

cin>>n>>m;//m就是询问次数，其他的和刚刚一样

for(int i=1;i<=n;i++){

cin>>a[i];

f[i][0]=a[i];//读入+初始化

}

int x=log(n)/log(2);//最大范围

//

接下来预处理

for(int i=1;i<=x;i++){//枚举刚刚说的2^i

for(int j=1;j<=n-(1<<i)+1;j++){//有不行的，刚刚解释过了

f[j][i]=min(f[j][i-1],f[j+(1<<(i-1))][i-1]);//转移

}

}

for(int i=1;i<=m;i++){

int l,r;cin>>l>>r;

int x2=log(r-l+1)/log(2);

cout<<min(f[l][x2],f[r-(1<<x2)+1][x2])<<" ";//求答案，由两个叠加起来来

}

return 0;

}