【题目】

对于一个 \(1\) 到 \(n\) 的排列 \(P\) （即 \(1\) 到 \(n\) 中每一个数在 \(P\) 中出现了恰好一次）。

令 \(q[i]\) 为第 \(i\) 个位置之后第一个比 \(P\) 值更大的位置，如果不存在这样的位置，则 \(q[i]=n+1\) 。

举例来说，如果 \(n=5\) 且 \(P\) 为 \(1 5 4 2 3\) ，则 \(q\) 为 \(2 6 6 5 6\) 。

下列程序读入了排列 \(P\) ，使用双向链表求解了答案。试补全程序。

#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;
        ① ;
    }
    
    for (int i = 1; i <= n; ++i) {
        R[i] = ② ;
        L[i] = i - 1;
    }
    
    for (int i = 1; i <= n; ++i) {
        L[ ③ ] = L[a[i]];
        R[L[a[i]]] = R[ ④ ];
    }
    
    for (int i = 1; i <= n; ++i) {
    	cout << ⑤ << " ";
    }
    
    cout << endl;
    return 0;
}

【解析】

先说说这道题怎么拿链表解决。

先找到最小的元素，是第1位的1，它右边不论是几都肯定比它大，所以这一位的答案就是右侧的第2位。
 此时把它从链表中删除，让前一位直接指向后一位。

再在链表中找到最小的元素，是第4位的2，它右边不论是几都比它大，所以这一位的答案是第5位。
 再从链表中把2删除，让前一位指向后一位。

继续这个过程，找到最小的元素是第5位的3，它右侧的元素肯定比它大，因此这一位的答案是第6位。
 然后从链表中把3删除，让前一位指向后一位。

继续，最小的元素是第3位的4，它右侧的元素（第6位）比它大，这一位答案是6。
         从链表中删除4。

最后只剩第2位的5，右侧（第6位）比它大，这一位答案是6。把它删除后，整个操作结束。

最终的答案就是过程中记录下的数据，第1位是2，第4位是5，第5位是6，第3位是6，第2位是6，
即答案数组2 6 6 5 6。

程序用的是双向链表， \(L\) 和 \(R\) 相当于分别存储了每个元素的上一位和下一位。
这样有什么好处呢？副产品会更多。
最终不止知道每个元素后面比它大的第一个元素在哪，还能知道前面比它大的第一个元素在哪。
第2个for循环，显然它是先把ii对应到a[i]，再对应到L和R数组，为什么呢？为了去掉每轮都要先寻找最小值的过程。先存一下第1小、第2小、第3小……的值依次出现在哪儿，每轮就能直那一位。

第1题：

\(a[x]=i\) 因为正好是1~n的排列
\(x\) 就表示第 \(x\) 小的数
\(a[x]=i\)表示第 \(x\) 小的数出现的位置
\(p\) 数组：\(1 5 4 2 3\)
\(a\) 数组：\(1 4 5 3 2\)

即最小的数出现在第1位，第2小在第4位……

第2题：

\(i+1\)
L记录前面第一个更大值的位置
R记录后面第一个更大值的位置
根据最值更新链表的过程，定位到当前的最小值后，就要从双向链表中将它删除。
\(i\)表示的是当前要找第\(i\)小的数，它的实际位置是 \(a[i]\) ，所以 \(i\) 与链表操作无直接关系，都是与 \(a[i]\) 有关。
要让前一位和后一位直接互相指向，用自己的前一位更新后一位的前一位，用自己的后一位更新前一位的后一位。

第3题：

\(R[a[i]]\)

第4题：

\(a[i]\)
我们假定位置 \(i\) 后边的最大数字的位置为 \(i+1\)，然后从最小的 \(1\) 开始更新，让 \(1\) 所在位置的前一位直接指向 \(1 \) 的后一位（ \(1\) 不可能是 \(1\) 所在位置的前一位的后边的第一个最大的，相当于删除了 \(1\)）。从小到大循环删除所有的不合法假定，剩下的就是答案。

第5题：

\(R[i]\)
\(R\)记录后面第一个更大值的位置