P10297 [CCC 2024 S3] Swipe

Swipe is a new mobile game that has recently become very popular. In each level of Swipe, you are given two sequences $A$ and $B$ of length $N$. The goal of each level is to turn array $A$ into array $B$. There are now two types of swipe operations that can be applied to $A$. - Swipe right: choose an interval $[l, r]$, and for every $l \leq i \leq r$, set $A_i = A_l$. - Swipe left: choose an interval $[l, r]$, and for every $l \leq i \leq r$, set $A_i = A_r$. For example, initially $A = [0, 1, 2, 3, 4, 5]$. If we perform a swipe right on interval $[2, 4]$, the sequence becomes $[0, 1, 2, 2, 2, 5]$. If we perform a swipe left on interval $[3, 5]$, the sequence becomes $[0, 1, 2, 5, 5, 5]$. Note that the sequence is indexed starting from $0$. Unfortunately, the game has some issues and may contain levels that cannot be cleared. Determine whether it is possible to transform array $A$ into array $B$. If it is possible, output any sequence of swipe operations that transforms $A$ into $B$.

The first line contains a positive integer $N$, the length of the two sequences. The second line contains $N$ integers from $A$, separated by spaces. The third line contains $N$ integers from $B$, separated by spaces.

If there exists a sequence of operations that can turn $A$ into $B$, output `YES` on the first line; otherwise output `NO`. If you output `YES` on the first line, then the next line contains a non-negative integer $K$ ($K \leq N$), the number of swipes. In the next $K$ lines, each line contains three space-separated values: $D_j$, $l_j$, and $r_j$. $D_j$ is `R` or `L`, indicating whether the $j$-th operation is a swipe right or a swipe left. $l_j$ and $r_j$ are the left and right endpoints of the swipe, and must satisfy $0 \leq l_j \leq r_j < N$.

**This problem uses bundled testdata.** For all testdata, it is guaranteed that $1 \leq N \leq 3 \times 10^5$, and $1 \leq A_i, B_i \leq 3 \times 10^5$. The following table shows the distribution of the $15$ points: | Points | Range of $N$ | Range of $A_i$ and $B_i$ | | :-: | :-: | :-: | | $2$ | $N = 2$ | $1 \leq A_i, B_i \leq 3$ | | $4$ | $1 \leq N \leq 8$ | $1 \leq A_i, B_i \leq 8$ | | $4$ | $1 \leq N \leq 500$ | $1 \leq A_i, B_i \leq 3000$ | | $5$ | $1 \leq N \leq 3 \times 10^5$ | $1 \leq A_i, B_i \leq 3 \times 10^5$ | Note that for a subtask worth $M$ points, if you only answer the first line correctly, you can get $\left\lfloor\dfrac M2\right\rfloor$ points. Translated by ChatGPT 5