数组索引与反向索引建立技巧（排列专用）

适用场景：给定 1~n 的排列（每个数恰好出现一次），快速定位数值位置。

1. 两个基本概念

• 正向索引（位置 → 值） 下标代表位置，值代表该位置上的数。 ```cpp pos[i] = x; // 位置 i 上的数值是 x 反向索引（值 → 位置）

下标代表数值，值代表该数值出现的位置。
```cpp
a[x] = i;     // 数值 x 出现在位置 i

1. 建立方法（核心技巧）

for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    // 正向：位置 i → 值 x
    pos[i] = x;
    // 反向：值 x → 位置 i（最常用技巧）
    a[x] = i;
}

1. 为什么要建反向索引？ 想按数值从小到大遍历，直接循环 x = 1 ~ n 直接 a[x] 就能拿到该数值所在位置 时间复杂度 O (n)，比排序更快、代码更短
2. 本题中的作用 输入排列：1 5 4 2 3 建立反向索引后： a[1] = 1 a[2] = 4 a[3] = 5 a[4] = 3 a[5] = 2 循环 i=1~n 依次拿到位置： 1 → 4 → 5 → 3 → 2 即 “从小到大数值对应的下标序列”。
3. 一句话记忆 数组下标当位置 → 正向索引 数组下标当数值 → 反向索引 排列题目几乎都用 a[x] = i 快速映射数值与位置。

【NOIP2018】简单链表，初赛最后一题

#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 = l; 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;
}


/*

输入： 
5
1 5 4 2 3
输出：
2 6 6 5 6
*/

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com