UOJ180 【UR #12】实验室外的攻防战题解

题意：

经过跳蚤侦察兵的勘察，跳蚤国王发现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$ 右侧的操作都要经过 $v$ ，所以 $u$ 始终在 $v$ 的左侧。

可以证明，当且仅当不存在任意一对 $u < v$ ，

满足 $A$ 中 $u$ 在 $v$ 左侧而 $B$ 中 $v$ 在 $u$ 右侧时，原序列一定存在合法的解。

证明设 $n$ 元置换 $\varphi$ 满足 $\varphi(b_i)=i$ 。

记序列 $A’ = \{\varphi(a_1),\varphi(a_2),\cdots,\varphi(a_n)\}$ 。

考虑对 $A’$ 冒泡排序，使其变为 $B’=\{\varphi(b_1),\varphi(b_2),\cdots,\varphi(b_n)\} = \{1,2,\cdots ,n\}$

考察每次交换，设交换了 $u,v$ （$u$ 在 $v$ 左侧），则在 $A’$ 中为 $\varphi(u),\varphi(v)$ 且 $\varphi(u) > \varphi(v)$

由 $\varphi(u) > \varphi(v)$ 以及 $\varphi$ 的定义可知，在 $B$ 中，$u$ 在 $v$ 的右边。

由条件可知 $u > v$ （否则矛盾）可知这一次交换可以成功进行，进而每次均可行。$\square$

于是我们只需要判断是否存在这样的 $u < v$ 即可。

记 $p_{a_i} = i, q_{b_i} = i$ ，则问题转化为判断是否存在 $u < v$ 满足 $p_u < p_v \, \land \, q_u > q_v$ 。

这就是一个二维数点问题。考虑固定 $v$ ，用树状数组维护 $[1,p_v)$ 的前缀 $q$ 最大值即可。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define lowbit(x) ((x) & (-(x)))
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))

int n, a[N], b[N], tr[N];
void add(int x, int v) { for(int i = x; i <= n; i += lowbit(i)) up(tr[i], v); }
int qry(int x, int r = 0) { for(int i = x; i; i -= lowbit(i)) up(r, tr[i]); return r; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; int x;
    rep(i, 1, n) { cin >> x; a[x] = i; }
    rep(i, 1, n) { cin >> x; b[x] = i; }
    for(int i = 1; i <= n; add(a[i], b[i]), i++)
        if(qry(a[i]) > b[i]) return cout << "NO\n", 0;
    return cout << "YES\n", 0;
}