题目翻译

我们称一个长度为 $n$ 的数组 $a$ 是 坏 的，当且仅当存在 $1 \le i \le n-4$ 使得以下条件之一成立：

• $a_i < a_{i+1} < a_{i+2} < a_{i+3} < a_{i+4}$
• $a_i > a_{i+1} > a_{i+2} > a_{i+3} > a_{i+4}$

一个数组是 好 的当且仅当它不是坏的。

你被给定一个排列 $p_1, p_2, \dots, p_n$。你必须进行 $n$ 轮操作。在每一轮，你必须删除当前剩余数组 $p$ 的最左端或最右端的元素。设 $q_i$ 为第 $i$ 轮被删除的元素。选择每一轮删除哪个方向的元素，使得最终得到的数组 $q$ 是好的。可以证明在给定约束下，总是存在这样的操作序列。

输出一个长度为 $n$ 的字符串 $s$，其中 $s_i = \text{L}$ 表示第 $i$ 轮删除左端元素，$s_i = \text{R}$ 表示删除右端元素。如果有多个解，输出任意一个。

解题思路

关键观察

如果构造出的 $q$ 满足 交替大小关系：

即奇数位置小于下一个偶数位置，偶数位置大于下一个奇数位置，那么任何连续 $5$ 个元素中必然同时包含上升和下降，不可能出现 $5$ 个连续递增或递减。因此这样的 $q$ 一定是好的。

构造方法

• 将操作轮次编号为 $1, 2, \dots, n$。
• 在第 $i$ 轮：
  • 若 $i$ 为奇数：删除当前剩余数组左、右两端中 较小 的那个元素。
  • 若 $i$ 为偶数：删除当前剩余数组左、右两端中 较大 的那个元素。

正确性证明

设第 $i$ 轮（奇数）时，剩余数组的两端元素为 $L$ 和 $R$。我们取较小者，不妨设 $L \le R$，则 $q_i = L$。移除 $L$ 后，新区间的左端点变为 $L'$（原 $L$ 右侧的元素），右端点仍为 $R$。

第 $i+1$ 轮（偶数）时，取当前两端的较大者 $\max(L', R)$。因为 $R \ge L$ 且 $L'$ 可能小于或大于 $R$，但 $\max(L', R) \ge R \ge L$。由于 $L$ 已被移除且元素互异，$\max(L', R)$ 不可能等于 $L$，因此 $\max(L', R) > L$，即 $q_{i+1} > q_i$。

类似地，若第 $i$ 轮为偶数，取两端较大者 $q_i = \max(L,R)$，不妨设 $R \ge L$，则 $q_i = R$。移除 $R$ 后，新区间右端点变为 $R'$（原 $R$ 左侧的元素），左端点仍为 $L$。第 $i+1$ 轮（奇数）取两端较小者 $\min(L, R')$，它一定小于等于 $L$，而 $L \le R = q_i$，且由于元素互异，$\min(L, R') < R$，故 $q_{i+1} < q_i$。

因此序列满足 $q_1 < q_2 > q_3 < q_4 > \dots$，从而不含连续 $5$ 个单调元素，是好的。

算法步骤

1. 初始化左指针 $l = 0$，右指针 $r = n-1$（使用 $0$ 索引）。
2. 初始化空字符串 $ans$。
3. 对于 $i = 1$ 到 $n$：
   • 若 $i$ 是奇数：
     • 如果 $p[l] < p[r]$，则 $ans$ 添加 'L'，$l \leftarrow l+1$；
     • 否则添加 'R'，$r \leftarrow r-1$。
   • 若 $i$ 是偶数：
     • 如果 $p[l] > p[r]$，则 $ans$ 添加 'L'，$l \leftarrow l+1$；
     • 否则添加 'R'，$r \leftarrow r-1$。
4. 输出 $ans$。

时间复杂度 $O(n)$，空间 $O(n)$，满足 $n$ 总和不超过 $2 \times 10^5$ 的限制。

代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> p(n);
        for (int i = 0; i < n; ++i) cin >> p[i];
        int l = 0, r = n - 1;
        string ans;
        for (int i = 1; i <= n; ++i) {
            if (i & 1) { // 奇数轮：取较小端
                if (p[l] < p[r]) {
                    ans += 'L';
                    ++l;
                } else {
                    ans += 'R';
                    --r;
                }
            } else { // 偶数轮：取较大端
                if (p[l] > p[r]) {
                    ans += 'L';
                    ++l;
                } else {
                    ans += 'R';
                    --r;
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

示例验证

以第一个样例 $n=7, p=[1,2,3,4,5,6,7]$ 运行上述算法：

• $i=1$（奇）：$p[0]=1 < p[6]=7$，取左 L，$l=1$，$q_1=1$。
• $i=2$（偶）：$p[1]=2 < p[6]=7$，取右 R，$r=5$，$q_2=7$。
• $i=3$（奇）：$p[1]=2 < p[5]=6$，取左 L，$l=2$，$q_3=2$。
• $i=4$（偶）：$p[2]=3 < p[5]=6$，取右 R，$r=4$，$q_4=6$。
• $i=5$（奇）：$p[2]=3 < p[4]=5$，取左 L，$l=3$，$q_5=3$。
• $i=6$（偶）：$p[3]=4 < p[4]=5$，取右 `R$，$r=3$，$q_6=5$。
• $i=7$（奇）：$l=3,r=3$，$p[3]=4$，任取 L，$q_7=4$。

得到 $q=[1,7,2,6,3,5,4]$，满足 $1<7>2<6>3<5>4$，无连续 $5$ 个单调，输出 LRLRLRL（实际为 LLRLRLR 或类似，但本题允许任意解）。与样例输出 RRRLLLL 不同，但也正确。