问题分析

本题要求通过从序列 $a$ 的两端取数构造回文序列 $b$，需要找到字典序最小的操作方案。关键在于每个数字恰好出现两次，这为构造回文提供了可能性。

核心思路

算法框架：贪心 + 双指针模拟

• 预处理：记录每个数字两次出现的位置

• 两种初始情况：分别尝试首元素匹配和尾元素匹配

• 贪心扩展：每次选择字典序最小的可行操作

关键数据结构

int l[N], r[N];  // 记录每个数字两次出现的位置
int ans[N * 2];  // 记录操作序列，1表示L，2表示R

算法详解

1.预处理阶段

for (int i = 1; i <= n + n; i++) {
    if (!l[a[i]])
        l[a[i]] = i;    // 第一次出现的位置
    else
        r[a[i]] = i;    // 第二次出现的位置
}

2.第一种情况：首元素匹配

void work1() {
    int L = 2, R = n + n;
    ans[1] = 1;         // 第一步取左端
    ans[n + n] = 1;     // 最后一步对应位置也取左端
    int tpl = r[a[1]], tpr = r[a[1]];  // 第一个数字的匹配位置
    
    for (int i = 1; i < n; i++) {
        // 四种可能的扩展方式，按字典序优先尝试
        if (r[a[L]] == tpl - 1)
            tpl--, L++, ans[start++] = 1, ans[end--] = 1;
        else if (r[a[L]] == tpr + 1)
            tpr++, L++, ans[start++] = 1, ans[end--] = 2;
        else if (l[a[R]] == tpl - 1)
            tpl--, R--, ans[start++] = 2, ans[end--] = 1;
        else if (l[a[R]] == tpr + 1)
            tpr++, R--, ans[start++] = 2, ans[end--] = 2;
        else
            return;  // 无法扩展
    }
    print();
}

3.第二种情况：尾元素匹配

void work2() {
    int L = 1, R = n + n - 1;
    ans[1] = 2;         // 第一步取右端
    ans[n + n] = 1;     // 最后一步对应位置取左端
    int tpl = l[a[n + n]], tpr = l[a[n + n]];  // 最后一个数字的匹配位置
    
    // 扩展逻辑与work1相同
    // ...
}

算法正确性证明

1.回文构造原理

每个数字出现两次，正好可以对称放置

每次操作确定一对对称位置的值

维护的 tpl 和 tpr 表示当前已确定的最左和最右匹配位置

2.字典序最优性

优先尝试 L 操作（字典序更小）

四种扩展方式按字典序排列：

• L...L

• L...R

• R...L

• R...R

3.完备性

只考虑两种初始情况：

Case 1：第一个数字与最后一个数字匹配

Case 2：最后一个数字与第一个数字匹配 覆盖了所有可能的回文构造起点。

复杂度分析

时间复杂度

• 预处理：$O(n)$

• 每种情况模拟：$O(n)$

• 总复杂度：$O(\sum n)$，满足数据范围要求

空间复杂度

$O(n)$ 存储位置信息和答案

样例分析

样例1：4 1 2 4 5 3 1 2 3 5

成功找到解：LRRLLRRRRL

构造的序列：[4, 5, 3, 1, 2, 2, 1, 3, 5, 4]

关键优化

• 双指针维护：$L$ 和 $R$ 指针表示当前可操作的范围

• 位置追踪：tpl 和 tpr 记录已匹配的区间边界

• 提前终止：无法扩展时立即返回，避免无效计算

总结

本题通过巧妙的贪心策略和双指针技术，在 $O(n)$ 时间内解决了回文序列构造问题。算法的核心在于利用数字出现两次的特性，维护匹配区间并优先选择字典序小的操作。两种初始情况的枚举确保了不会遗漏可行解，而贪心的扩展顺序保证了字典序最优性。

AC代码

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

const int N = 5e5 + 10;
int T;
int n;
int a[N * 2];
int l[N], r[N];
int ans[N * 2];
bool flag;
void print() {
    flag = 1;

    for (int i = 1; i <= n + n; i++)
        cout << (ans[i] == 1 ? 'L' : 'R');

    cout << '\n';
}
void work1() {
    int L = 2, R = n + n;
    ans[1] = 1;
    ans[n + n] = 1;
    int tpl = r[a[1]], tpr = r[a[1]], start = 2, end = 2 * n - 1;

    for (int i = 1; i < n; i++) {
        if (r[a[L]] == tpl - 1)
            tpl--, L++, ans[start++] = 1, ans[end--] = 1;
        else if (r[a[L]] == tpr + 1)
            tpr++, L++, ans[start++] = 1, ans[end--] = 2;
        else if (l[a[R]] == tpl - 1)
            tpl--, R--, ans[start++] = 2, ans[end--] = 1;
        else if (l[a[R]] == tpr + 1)
            tpr++, R--, ans[start++] = 2, ans[end--] = 2;
        else
            return;
    }

    print();
    return;
}
void work2() {
    int L = 1, R = n + n - 1;
    ans[1] = 2;
    ans[n + n] = 1;
    int tpl = l[a[n + n]], tpr = l[a[n + n]], start = 2, end = 2 * n - 1;

    for (int i = 1; i < n; i++) {
        if (r[a[L]] == tpl - 1)
            tpl--, L++, ans[start++] = 1, ans[end--] = 1;
        else if (r[a[L]] == tpr + 1)
            tpr++, L++, ans[start++] = 1, ans[end--] = 2;
        else if (l[a[R]] == tpl - 1)
            tpl--, R--, ans[start++] = 2, ans[end--] = 1;
        else if (l[a[R]] == tpr + 1)
            tpr++, R--, ans[start++] = 2, ans[end--] = 2;
        else
            return;
    }

    print();
    return;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    //freopen("palin.in", "r", stdin);
    //freopen("palin.out", "w", stdout);
    cin >> T;

    while (T--) {
        flag = 0;
        memset(l, 0, sizeof l);
        memset(r, 0, sizeof r);
        cin >> n;

        for (int i = 1; i <= n + n; i++)
            cin >> a[i];

        for (int i = 1; i <= n + n; i++) {
            if (!l[a[i]])
                l[a[i]] = i;
            else
                r[a[i]] = i;
        }

        work1();

        if (flag)
            continue;

        work2();

        if (flag)
            continue;

        cout << -1 << '\n';
    }

    return 0;
}