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;
}