NOIP 普及 2018 第一轮 第 30 题：用双向链表求右侧第一个更大元素位置：第 1 空

题目

对于一个 $1$ 到 $n$ 的排列 $P$（即 $1$ 到 $n$ 中每一个数在 $P$ 中出现了恰好一次），令 q[i] 为第 $i$ 个位置之后第一个比 P[i] 值更大的位置，如果不存在这样的位置，则 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;
}

①处应填（ ）

答案

a[x] = i

题解

考点定位

本题（完善程序「双向链表求右侧更大元素」第①空）考「倒序建链」,对应大纲 3.2.3 链表（难度【4】）。

程序思路：从右往左扫，链表 R[i] 存 i 右侧第一个更大元素的位置（不存在为 0），链按「更大元素」单调递减连接。

解题过程

①处倒序扫描时把 i 插入链头：

``cpp a[x] = i; // x 为链插入定位（依原卷变量） ``

答案：a[x] = i。

易错提醒

① 倒序处理保证「右侧已处理」；② 链表指针 R/数组 a 的双重含义要看原卷变量声明。