压缩后缀数组
Description
Input
Output
Sample Input
32
2 2 14 15 18 23 7 8 28 10 30 31 13 14 15 16 17 18 7 8 21 10 23 13 16 17 27 28 21 30 31 27
8 14 5 2 12 16 7 15 6 9 3 10 13 4 1 11
Sample Output
15 16 31 13 17 19 28 10 7 4 1 21 24 32 14 30 12 18 27 9 6 3 20 23 29 11 26 8 5 2 22 25
Data Constraint
Hint
【数据规模】
对于20%的数据,有2<=n<=2^6。
对于100%的数据,有2<=n<=2^14。
解析:刚开始看上去极为复杂,但仔细看看:其实题意就是给两个由一个数列拓展出来的数列,还原成原来的数列就好了。
#include <iostream>
using namespace std;
int b[100001],c[100001],a[100001];
int main()
{
int n;
cin>>n;
for (int i=1;i<=n;i++)
cin>>b[i];
int l=0;
for (int i=1;i<=n/2;i++)
{
cin>>c[i];
}
for (int i=1;i<=n;i++)
if (b[i]==i)
a[i]=c[++l]*2;
for (int i=1;i<=n;i++)
{
if (!a[i])
a[i]=a[b[i]]-1;
cout<<a[i]<<" " ;
}
}