25 July 2014

# 题目

#### `Problem Description`

``````A new technology about suffix array called compressed suffix array is being researched.Let SA be the suffix array for string T. In the base case, we denote SA by SA0, and let n0=n be the number of its entries. For simplicity in exposition, we assume that n is a power of 2. In the inductive phase k, we start with suffix array SAk, which is available by induction. It has nk=n/(2^k) entries and stores a permutation of {1,2,...,nk}. (Intuitively, this permutation is that resulting from sorting the suffixes of T whose suffix pointers are multiple of 2^k.)

We run two main steps to transform SAk into an equivalent but more succinct representation:

Step 1. We define a function Fik, where Fik(i)=j if and only if SAk[i] is odd and SAk[j]=SAk[i]+1.
In summary, for 1<=i<=nk, we have Fik(i)=j, if SAk[i] mod 2 = 1 and SAk[j]=SAk[i]+1
Fik(i)=i, otherwise.

Step 2. Pack together the even values from SAk and divide each of them by 2. The resulting values form a permutation of {1,2,...,nk+1}, where nk+1=nk/2=n/2^(k+1). Store them into a new suffix array SAk+1 entries, and remove the old suffix array SAk.

The following example illustrates the effect of a single application of Steps 1-2.
SA0:
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
Fi0:
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
SA1:
8 14 5 2 12 16 7 15 6 9 3 10 13 4 1 11

Fik can be stored in a particular way in O(n) bits, and SAk+1 occupy half space of SAk, So we can compress the suffix array by repeat steps 1-2. Now, the question is, if we have known SAk+1 and Fik, how can we get the SAk?
``````

#### `Input`

``````You will be given a number of cases in the input. Each case starts with a line containing n. The first line contains a positive integer n, which is a power of 2, (2<=n<=2^14)
Followed by 2 lines.
The first line contains n integers represent for Fik.
The second line contains k integers (k=n/2) represent for SAk+1.
The input terminates with EOF.
``````

#### `Output`

``````For each input data set output one line, contains the numbers of SAk (each number are separated by a space).
``````

#### `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
``````

# 解题思路

``````题目意思是给出 Fi0 和 SA1，“解压缩”出 SA0.

SA0[] 中的偶数值知道了，接下来就好办了。因为压缩的时候奇数的位置记录是转化为使用偶数的位置来储存的，这时候只需要知道奇数对应的偶数在哪，找出来再转换回来（即偶数值减 1）即可。也就是说如果 Fi0[i] != 0（表示 SA0[i] 为奇数），那么 Fi0[i] 所代表的奇数所对应的偶数就储存在 SA0[Fi0[i]] 里面，这个偶数值减 1 就能求出奇数的值了。
``````