RE求查错
查看原帖
RE求查错
210719
Violet___Evergarden楼主2021/10/3 15:32
#include <iostream>
using namespace std;
const int kMaxN=1e5+1;
int p[kMaxN],st[kMaxN][26];
int n,m,q;
int ans[kMaxN],at[kMaxN];
int main()
{
cin>>n>>m>>q;
for(int i=1;i<=m;i++)
{
  cin>>p[i];
  p[i]--;
  st[i][0]=p[i];
}
for(int i=m+1;i<=n;i++)
{
  st[i][0]=i-1;
}
for(int i=1;i<=25;i++)//算st表
{
  for(int j=1;j<=n;j++)
  {
    st[j][i]=st[st[j][i-1]][i-1];
  }
}
for(int i=1;i<=m;i++)
{
  int x=i,ci=0;
  for(int j=25;j>=0;j--)
  {
    if(st[x][j]==0)continue;
    x=st[x][j];
    ci+=(1<<j);
  }
  ans[ci+1]=i;
}
for(int i=m+1;i<=n;i++)
{
  int x=i;
  int ci=m;
  for(int j=25;j>=0;j--)
  {
    if((1<<j)<=ci)
    {
      x=st[x][j];
      ci-=(1<<j);
    }
  }
  at[x]=i;
}
int cnt=m;
for(int i=1;i<=n;i++)
{
  if(at[i]!=0)
  {
    ans[++cnt]=at[i];
  }
}
while(q--)
{
  int x;
  cin>>x;
  x=n-x+1;
  cout<<ans[x]<<"\n";
}
return 0;
}
2021/10/3 15:32
加载中...