noip2018j1t23.md

NOIP 2018 J1 T23 | 双向链表 单调队列 - WedJul10 2024

NOIP 2018 普及组初赛试题：对于一个 $1$ 到 $n$ 的排列 $P$（$1$ 到 $n$ 中每一个数在 $P$ 中出现了恰好一次），令 $Q_i$ 为第 i 个位置之后第一个比 $P_i$ 值更大的位置，如果不存在这样的位置，则 $Q_i=n+1$. 给定 $P$，求 $Q$.

样例输入

5 1 5 4 2 3

样例输出

2 6 6 5 6

做法 1

原题当然是程序完善，但我只想讲这个线性算法.

建双向链表，第 i 个节点的值是 $P_i$，从小到大删掉所有节点，节点 i 在删掉前一刻，两侧都剩下比它大的. 而删节点只会影响两侧节点的指针，它自己的不会变. 删完后每个节点的 R 指针记为所求. 为了从小到大删点，定义 a[i] 表示数字 i 在链表的位置.

这个算法改改就能算{之后/之前}最近的{更大/更小}值的位置.

#include <iostream>
const int N = 100010;
int n, L[N], R[N], a[N];
int main() {
    using std::cin; cin >> n;
    for (int i = 1, x; i <= n; ++i)
        cin >> x, a[x]=i;
    for (int i = 1; i <= n; ++i)
        R[i] = i+1, L[i] = i-1;
    for (int i = 1; i <= n; ++i) {
        L[R[a[i]]] = L[a[i]];
        R[L[a[i]]] = R[a[i]];
    }
    for (int i = 1; i <= n; ++i)
    	std::cout << R[i] << " ";
    std::cout << '\n';
}

做法 2

单调队列，代码略。这个方法和 $P_i$ 的取值无关。