问题描述

对于一个 $1$ 到 $n$ 的排列 $p_i$（即 $1$ 到 $n$ 中每一个数在 $p_i$ 中出现了恰好一次），令 $q_i$ 为第 $i$ 个位置之后第一个比 $p_i$ 值更大的位置，如果不存在这样的位置，则 $q_i = n + 1$。举例来说，如果 $n = 5$ 且 $p$ 为 1 5 4 2 3 ，则 $q$ 为 2 6 6 5 6 。

下列程序读入了排列 $p_i$ ，使用双向链表求解了答案。试补全程序。

数据输入

第一个行一个整数 $n$ 。

第二行 $n$ 个整数 $p_i$，不会有重复的数。

数据输出

一行 n 个数 $q_i$，用空格隔开。

样例

6
2 3 1 6 4 5

2 4 4 7 6 7

解题思路

这条题是 csp-j 的真题。

如果是编程题，可以有很多方法解这道题的，我会倾向于用单调栈的算法的。但是，现在题目明确说了，要用链表的方法，而且代码写得很浓缩简练，要读懂并不容易。

题目里面有一个信息：所有的数字只出现了 1 次。因为是 n 个数，数字范围是 1 ~ n ,所以每个数都出现了一次，也不可能缺了某个数。

某个位置之后第一个比它大的数，可以想象，如果是 1 ，只要后面还有数字那就一定是后面的数字了。如果 1 是在最后，这是一个特殊情况，按照题目的意思，就是要输出 n+1 ，我们可以把特殊情况简单化，让 x[n+1] = n ，那么假设 x[n] = 1，也可以用一般性的情况来应对，还是输出 1 后面的数字。

然后，2 后面的第一个比 2 大的数字是什么呢？假设 2 后面的数字是不是 1 ，那就是输出后面的数字，如果 2 后面是 1 ，那就输出 1 后面的数字。

......

所以，如果把这 n 个数按照他们的顺序构建一个链表，我们先解决1 后面第一个比 1 大的数字的位置这个问题（方法很简单，就是输出 1 的后面位置），解决完这个问题，就把 1 删掉。删掉 1 的目的是为了方便解决2 后面第一个比 2 大的数字的位置这个问题，没有了 1 的存在，我们只需要看 2 后面指向的位置就可以了（所有的数字里只有 1 是比 2 小的，只要 1 不存在了，那么 2 后面的数字就是答案）。

解决完2 后面第一个比 2 大的数字的位置这个问题，我们又在链表中把 2 删掉，所以，我们很容易解决3 后面第一个比 3 大的数字的位置这个问题。因为 1 和 2 都被删掉了，剩下的数字都比 3 大，所以，3 后面的数字就是答案）。

.......

完成程序

#include <iostream>
using namespace std;

const int N = 100010;
int n;
int L[N], R[N], a[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        填空(1) ;
    }
    
    for (int i = 1; i <= n; ++i) {
        R[i] = 填空(2) ;
        L[i] = i - 1;
    }
    
    for (int i = 1; i <= n; ++i) {
        L[ 填空(3) ] = L[a[i]];
        R[L[a[i]]] = R[ 填空(4) ];
    }
    
    for (int i = 1; i <= n; ++i) {
    	cout << 填空(5) << " ";
    }
    
    cout << endl;
    return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}