经过跳蚤侦察兵的勘察，跳蚤国王发现 picks 博士的防御工事有着 $n$ 处薄弱点，于是他把他的跳蚤大军分成了 $n$ 支小队，并打算让它们分别进攻每一个薄弱点。但是因为战场混乱，这 $n$ 支小队的位置被打乱了，重新整队之后，跳蚤国王发现第 $i$ 个位置的小队编号为 $A_i$ (显然 $A$ 是一个排列)。
经过计算，跳蚤国王发现，让第 $i$ 个位置的小队编号为 $B_i$ 时，他的军队可以发挥出最大的战斗力 (保证 $B$ 也是一个排列)。
跳蚤国王可以发出指令来改变小队们的排列顺序，每一次，他都会报出一个整数 $i(1 \leq i < n)$。如果排在第 $i$ 个位置的小队编号大于第 $i+1$ 个位置的小队，那么这两支小队会交换顺序，否则这一个命令将会被忽略。
现在跳蚤国王希望他的军队能够发挥出最强大的战斗力，于是他想要知道是否存在一种指令序列，使得小队们可以按照排列 $B$ 的方式排列。
但是因为小队数目实在是太多，跳蚤国王一时间也没有看出答案。于是他派跳蚤绑架来了你——这附近最著名的民间科学家来帮他计算这个问题的答案。
第一行包含一个正整数 $n$ ($n \leq 10^5$)。
接下来两行，每行 $n$ 个正整数，分别描述排列 $A$ 和排列 $B$。
对于每组数据，如果存在这样的指令序列，输出 YES，否则输出 NO (请注意大小写)。
稍加观察可以发现，对于两个数 $u < v$，若在排列 $A$ (原排列) 中 $u$ 在 $v$ 的左边，则在后面的变化中 $u$ 一定在 $v$ 的左边。
反之，如果某一步 $u$ 跑到 $v$ 右边去了，由于只能交换相邻的数对，那么这一步 $u, v$ 一定是相邻的。而相邻元素的交换必须满足左边大于右边，于是矛盾，故 $u$ 永远在 $v$ 的左边。
于是，如果在排列 $A$ 中，(存在 $u < v$) $u$ 在 $v$ 的左边，而在排列 $B$ 中，$u$ 在 $v$ 的右边，这样是一定无法满足要求的。
然后你又惊奇地发现，这居然又是一个充要条件！
下面证明，如果不存在 $u < v$，满足在 $A$ 中 $u$ 在 $v$ 的左边，在 $B$ 中 $u$ 在 $v$ 的右边，则原序列一定满足要求。
我们建立映射 $f : \{1, 2, \cdots, n\} \to \{1, 2, \cdots, n\}$，满足 $f(b_i) = i$。
令序列 $A' = \left[ f(a_1), f(a_2), \cdots, f(a_n) \right]$，我们对序列 $A'$ 进行冒泡排序，使得变成 $B' = \left[ f(b_1), f(b_2), \cdots, f(b_n) \right] = \left[ 1, 2, \cdots, n \right]$。
考虑每次交换，设 $A$ 中 (对应的) 相邻元素为 $u, v$ ($u$ 在 $v$ 的左边)，则在 $A'$ 中则为 $f(u), f(v)$ 且 $f(u) > f(v)$。
由 $f(u) > f(v)$ 及 $f$ 的定义知，在 $B$ 中，$u$ 在 $v$ 的右边。由条件，$u > v$ (否则与 $u < v$ 矛盾)。
因此这一次交换可以成功进行。从而每一次交换均可成功进行，证毕。
这样一来，我们只需判断是否存在 $u < v$，使得在 $A$ 中 $u$ 在 $v$ 的左边，在 $B$ 中 $u$ 在 $v$ 的右边。
令 $\alpha, \beta$ 为 $A, B$ 的逆置换 (即 $\alpha_{A_i} = i, \beta_{B_i} = i$)，那么就转化为判断是否存在 $u < v$ 满足 $\alpha_u < \alpha_v \wedge \beta_u > \beta_v$。
这就是一个经典的二维数点问题，可以使用树状数组解决 (具体方法是，固定 $u$，记录 $\beta_u$ 关于 $\alpha_u$ 的前缀最大值)。
总时间复杂度 $O \left( n \log n \right)$。
#include <bits/stdc++.h>
#define N 100005
#define lowbit(x) (x & -x)
int n;
int a[N], b[N], x[N];
inline void up(int &x, const int y) {x < y ? x = y : 0;}
void adj(int h, int v) {for (; h <= n; h += lowbit(h)) up(x[h], v);}
int pre(int h) {int s = 0; for (; h; h -= lowbit(h)) up(s, x[h]); return s;}
int main() {
int i, j;
scanf("%d", &n);
for (i = 1; i <= n; ++i) scanf("%d", &j), a[j] = i;
for (i = 1; i <= n; ++i) scanf("%d", &j), b[j] = i;
for (i = 1; i <= n; adj(a[i], b[i]), ++i)
if (pre(a[i]) > b[i]) return puts("NO"), 0;
return puts("YES"), 0;
}
无