从左往右维护两个指针l,r表示离i最近的k个点的区间,预处理出每个点出发的后继,然后倍增。
#include<cstdio>
typedef long long ll;
const int N=1000010,BUF=20000000,OUT=8000000;
int n,k,i,l=1,r,f[N],g[N],t[N],Outn[20],Outcnt;ll m,a[N];char Buf[BUF],*buf=Buf,Out[OUT],*ou=Out;
inline ll read(){ll a=0;while(*buf<48)buf++;while(*buf>47)a=a*10+*buf++-48;return a;}
inline void write(ll x){
for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;
while(Outcnt)*ou++=Outn[Outcnt--];
*ou++=32;
}
int main(){
fread(Buf,1,BUF,stdin),n=read(),k=read(),m=read();
for(i=1;i<=n;a[i++]=read());
for(r=f[t[1]=1]=k+1,i=2;i<=n;i++){
while(r<n&&a[r+1]-a[i]<a[i]-a[l])l++,r++;
f[i]=a[r]-a[i]>a[i]-a[l]?r:l,t[i]=i;
}
while(m){
if(m&1){
for(i=1;i<=n;i++)g[i]=f[t[i]];
for(i=1;i<=n;i++)t[i]=g[i];
}
m>>=1;
for(i=1;i<=n;i++)g[i]=f[f[i]];
for(i=1;i<=n;i++)f[i]=g[i];
}
for(i=1;i<=n;i++)write(t[i]);
return fwrite(Out,1,ou-Out-1,stdout),0;
}