给定两个长度为 $N$ 的整数数组 $A$ 和 $B$。
两数组的下标均从 $0$ 开始。
我们希望将数组 $A$ 变为数组 $B$。
为此，我们可以对数组 $A$ 进行任意次以下两种操作：
-
R l r：右刷操作。对于全部 $l \leq i \leq r$，令 $A_{i} = A_{l}$。例如，如果数组 $A$ 为 $\left[ 0, 1 , 2 , 3 , 4, 5 \right]$，那么R 2 4操作后，数组 $A$ 变为 $ \left[ 0, 1, 2, 2, 2, 5 \right]$。 -
L l r：左刷操作。对于全部 $l \leq i \leq r$，令 $A_{i} = A_{r}$。例如，如果数组 $A$ 为 $\left[ 0, 1 , 2 , 3 , 4, 5 \right]$，那么L 3 5操作后，数组 $A$ 变为 $\left[ 0, 1 , 2, 5, 5, 5 \right]$。
请你判断，我们能否将数组 $A$ 变为数组 $B$。
如果可以，给出一种具体方案。
输入格式
第一行包含整数 $N$。
第二行包含 $N$ 个整数，表示数组 $A$。
第三行包含 $N$ 个整数，表示数组 $B$。
输出格式
如果无法将数组 $A$ 变为数组 $B$，则输出一行 NO 即可。
如果可以将数组 $A$ 变为数组 $B$，那么第一行 YES，第二行输出一个整数 $K$，表示所需要的操作数量，接下来 $K$ 行，每行输出一个合法操作。
你必须保证 $K \leq N$。
如果方案不唯一，输出任意合理方案均可。
数据范围
$1 \leq N \leq 3 \times 10^{5}$
$1 \leq A_{i}, B_{i}, \leq 3 \times 10^{5}$
输入样例 1
3
3 1 2
3 1 1
输出样例 1
YES
1
R 1 2
输入样例 2
4
1 2 4 3
1 4 2 3
输出样例 2
NO
输入样例 3
4
2 1 4 3
2 1 4 3
输出样例 3
YES
0
本题可以分成两比分求解：
-
判断是否可以将数组 $A$ 刷成数组 $B$。
-
找到一种方案将数组 $A$ 刷成数组 $B$。
首先，判断是否可以将数组 $A$ 刷成数组 $B$。
在区间 $ \left[ l, r \right]$ 左刷或右刷时，$\forall i, j \in \left[ l, r \right]$，$A \left[ i \right] = A \left[ j \right]$。因此，如果 $\exists k \in \left[ l, r \right]$ 使得 $A \left[ k \right] \neq a \left[ l \right]$ 为左刷数组的起点或 $\exists k \in \left[ l, r \right]$ 使得 $A \left[ k \right] \neq A \left[ r \right]$ 为右刷数组的起点则数组 $A$ 一定不能被刷成 $B$。
例如，对于如下期望的两个操作，假设 $x \neq y$，如果先将 $x$ 向右刷则会使 $y_\mathrm{新} = x \neq y$，则将 $y$ 向左刷的操作不可行。
x y
| |
-----------x-x-x-|-x--x-x-x->
<-y-y-y-y-y-y---------
换言之，数组 $B$ 中的每一个元素必须按顺序出现在数组 $A$ 中。
为了方便计算，将数组 $B$ 中的元素存储在如下的一个结构体中，其中 $\mathtt{val}$ 表示这个元素的值，$\mathtt{start}$ 表示这个元素在 $B$ 中的起始下标，$\mathtt{end}$ 表示这个元素在 $B$ 中的终止下标。
struct B
{
int val;
int start, end;
};
vector<B> target;
遍历 $\mathtt{target}$ 中的每一个元素，同时从 $A$ 中从头到尾寻找该元素。如果该元素在 $A$ 中出现，则继续寻找 $\mathtt{target}$ 中的下一个元素。（注意：如下代码中的 $j$ 代表的是当前正在寻找的元素。因此，如果 $\mathtt{target}$ 中的元素在 $A$ 中依次出现，则 $j$ 的值为 $\mathtt{target}$ 最后一个元素的下标加 $1$，即 $\mathtt{target.size() + 1}$）
for (i = 0, j = 0; i < n && j < target.size(); i++)
{
if (a[i] == target[j].val)
{
j++;
}
}
if (j == target.size())
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
exit;
}
其次，找到一种将数组 $A$ 刷成数组 $B$ 的方案
为方便表示，将答案存储于如下的结构体中，其中 $\mathtt{type}$ 表示这种操作的类型，$\mathtt{start}$ 表示该操作在 $A$ 中的起始位置，$\mathtt{end}$ 表示该操作在 $A$ 中的终止位置。
struct Res
{
char type;
int start, end;
};
vector<Res> res;
由于数组 $B$ 中的每一个元素必须按顺序出现在数组 $A$ 中，重新遍历数组 $A$ 并到找这些依次出现的元素位置。这些元素的在 $A$ 中的位置和在 $B$ 中的位置可以分如下三种情况讨论：
情况 I：当 $x$ 在数组 $A$ 中的位置在 $x$ 在数组 $B$ 中的位置的左侧，如下图所示：
A x _ _ _ _ _ _ _ _ _ _ _ _
B _ _ _ x x x x x x _ _ _ _
将 $x$ 从 $i$ 开始向右刷直到 $x$ 在 $B$ 中的终止位置。
if (i <= target[j].start)
{
res.push_back({'R', i, target[j].end});
}
情况 II：当 $x$ 在数组 $A$ 中的位置在 $x$ 在数组 $B$ 中的位置的中间，如下图所示：
A _ _ _ _ _ _ _ x _ _ _ _ _ _ _
B _ _ _ x x x x x x x x _ _ _ _
将数组 $A$ 中的 $x$ 向左刷至 $x$ 在 $B$ 中的起始位置，向右刷至 $x$ 在 $B$ 中的终止位置。
else if (target[j].start < i && i < target[j].end)
{
res.push_back({'L', target[j].start, i});
res.push_back({'R', i, target[j].end});
}
情况 III：当 $x$ 在数组 $A$ 中的位置在 $x$ 在数组 $B$ 中的位置的右侧，如下图所示：
A _ _ _ _ _ _ _ _ _ _ x _ _
B _ _ _ x x x x x x _ _ _ _
将 $x$ 从 $i$ 开始向左刷直到 $x$ 在 $B$ 中的起始位置。
else if (i >= target[j].end)
{
res.push_back({'L', target[j].start, i});
}
注意，$\mathtt{res}$ 中的操作可能存在将 $x$ 由位置 $i$ 刷至位置 $i$ 的操作。将这种操作删除。
while (!res.empty() && res.back().start == res.back().end)
{
res.pop_back();
}
对于操作方向相同的操作，还需要针对如下的特殊情况排序：
对于右刷操作，如果先从 $x$ 开始刷，则会将 $y$ 覆盖掉，使得在 $y$ 的右刷操作无效。因此，右刷操作需要先进行起始坐标大的操作。
A _ _ _ x _ _ _ _ _ y _ _ _ _ _ _
| |
------------------------>
|------------------->
对于左刷操作，如果先从 $y$ 开始刷，则会将 $x$ 覆盖掉，使得在 $y$ 的左刷操作无效。因此，左刷操作需要先进行起始坐标小的操作。
A _ _ _ _ _ _ _ _ _ x _ _ _ _ _ y _ _ _ _ _ _
| |
<------------------
<---------------
排序函数如下：
bool cmp(const Res &A, const Res &B)
{
if (A.type == 'L' && B.type == 'L')
{
return A.end < B.end;
}
else
{
return A.start > B.start;
}
}
C++：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 3e6 + 10;
int n;
int a[N], b[N];
int i, j;
struct B
{
int val;
int start, end;
};
vector<B> target;
struct Res
{
char type;
int start, end;
};
vector<Res> res;
bool cmp(const Res &A, const Res &B)
{
if (A.type == 'L' && B.type == 'L')
{
return A.end < B.end;
}
else
{
return A.start > B.start;
}
}
int main()
{
cin >> n;
for (i = 0; i < n; i++)
{
cin >> a[i];
}
for (i = 0; i < n; i++)
{
cin >> b[i];
if (i == 0 || b[i] != b[i - 1])
{
target.push_back({b[i], i, i});
}
else
{
target.back().end = i;
}
}
// Part A
for (i = 0, j = 0; i < n && j < target.size(); i++)
{
if (a[i] == target[j].val)
{
j++;
}
}
if (j == target.size())
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
exit(0);
}
// Part B
for (i = 0, j = 0; i < n && j < target.size(); i++)
{
if (a[i] == target[j].val)
{
if (i <= target[j].start)
{
res.push_back({'R', i, target[j].end});
}
else if (target[j].start < i && i < target[j].end)
{
res.push_back({'L', target[j].start, i});
res.push_back({'R', i, target[j].end});
}
else if (i >= target[j].end)
{
res.push_back({'L', target[j].start, i});
}
while (!res.empty() && res.back().start == res.back().end)
{
res.pop_back();
}
j++;
}
}
sort(res.begin(), res.end(), cmp);
cout << res.size() << endl;
for (auto c : res)
{
cout << c.type << ' ';
cout << c.start << ' ';
cout << c.end << endl;
}
return 0;
}
