$1237B$ - 平衡隧道

这个问题可以通过多种方法解决，以下是其中一种。

假设汽车在时间点 $1,2,\dots,n$ 离开隧道，并设 $c_i$ 为汽车 $a_i$ 离开隧道的时间。

例如，在第一个示例中，我们有 $a = \langle 3,5,2,1,4 \rangle$ 和 $b = \langle 4,3,2,5,1 \rangle$。那么 $c = \langle 2,4,3,5,1 \rangle$：汽车 $3$ 第一个进入并在时间 $2$ 离开，所以 $c_1 = 2$；汽车 $5$ 第二个进入并在时间 $4$ 离开，所以 $c_2 = 4$；依此类推。

注意 $c$ 是一个排列，它不仅可以在 $O(n)$ 时间内找到，而且对我们非常有用。结果表明，我们可以使用 $c$ 轻松判断汽车 $a_i$ 是否必须被罚款。

具体来说，如果 $c_i$ 小于 $\max(c_1, c_2, \dots, c_{i-1})$，则汽车 $a_i$ 必须被罚款。

为什么呢？回顾一下：如果存在一辆更早进入隧道并且更晚离开隧道的汽车，那么汽车 $a_i$ 就必须被罚款。如果有一辆车更早进入隧道，那它一定是某个 $a_j$ 且 $j < i$。如果它更晚离开隧道，则必须满足 $c_j > c_i$。

因此，现在我们只需从左到右遍历，维护 $c_1, c_2, \dots, c_{i-1}$ 的最大值，并将其与 $c_i$ 进行比较。总复杂度为 $O(n)$。

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    --a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    --b[i];
  }
  vector<int> pos(n);
  for (int i = 0; i < n; i++) {
    pos[b[i]] = i;
  }
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    c[i] = pos[a[i]];
  }
  int mx = -1, ans = 0;
  for (int i = 0; i < n; i++) {
    if (c[i] > mx) {
      mx = c[i];
    } else {
      ++ans;
    }
  }
  cout << ans << '\n';
  return 0;
}