題目描述

給定正整數 $n$ 和整數序列 $a_1,a_2,\dots ,a_{2n}$，在這 $2n$ 個數中，$1,2,\dots ,n$ 分別各出現恰好 $2$ 次。現在進行 $2n$ 次操作，目標是創建一個長度同樣為 $2n$ 的序列 $b_1,b_2,\dots ,b_{2n}$，初始時 $b$ 為空序列，每次可以進行以下兩種操作之一：

1. 將序列 $a$ 的開頭元素加到 $b$ 的末尾，并從 $a$ 中移除。
2. 將序列 $a$ 的末尾元素加到 $b$ 的末尾，并從 $a$ 中移除。

我們的目的是讓 $b$ 成為一個回文數列，即令其滿足對所有 $1\le i\le n$，有 $b_i=b_{2n+1?i}$。請你判斷該目的是否能達成，如果可以，請輸出字典序最小的操作方案，具體在【輸出格式】中說明。

輸入格式

每個測試點包含多組測試數據。

輸入的第一行，包含一個整數 $T$，表示測試數據的組數。對于每組測試數據：

第一行，包含一個正整數 $n$。
第二行，包含 $2n$ 個用空格隔開的整數 $a_1,a_2,\dots ,a_{2n}$。

輸出格式

對每組測試數據輸出一行答案。

如果無法生成出回文數列，輸出一行 -1，否則輸出一行一個長度為 $2n$ 的、由字符 L 或 R 構成的字符串（不含空格），其中 L 表示移除開頭元素的操作 1，R 表示操作 2。

你需要輸出所有方案對應的字符串中字典序最小的一個。

字典序的比較規則如下：長度均為 $2n$ 的字符串 $s_{1～2n}$ 比 $t_{1～2n}$ 字典序小，當且僅當存在下標 $1\le k\le 2n$ 使得對于每個 $1\le i<k$ 有 $s_i=t_i$ 且 $s_k<t_k$。

輸入輸出樣例 #1

輸入 #1

2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3

輸出 #1

LRRLLRRRRL
-1

輸入輸出樣例 #2

輸入 #2

見附件中的 palin/palin2.in

輸出 #2

見附件中的 palin/palin2.ans

說明/提示

【樣例解釋 #1】

在第一組數據中，生成的的 $b$ 數列是 $[4,5,3,1,2,2,1,3,5,4]$，可以看出這是一個回文數列。

另一種可能的操作方案是 LRRLLRRRRR，但比答案方案的字典序要大。

【數據范圍】

令 $\sum n$ 表示所有 $T$ 組測試數據中 $n$ 的和。

對所有測試點保證 $1\le T\le 100$，$1\le n,\sum n\le 5\times {10}^5$。

測試點編號	$T\le$	$n\le$	$\sum n\le$	特殊性質
$1～7$	$10$	$10$	$50$	無
$8～10$	$100$	$20$	$1000$	無
$11～12$	$100$	$100$	$1000$	無
$13～15$	$100$	$1000$	$25000$	無
$16～17$	$1$	$5\times {10}^5$	$5\times {10}^5$	無
$18～20$	$100$	$5\times {10}^5$	$5\times {10}^5$	有
$21～25$	$100$	$5\times {10}^5$	$5\times {10}^5$	無

特殊性質：如果我們每次刪除 $a$ 中兩個相鄰且相等的數，存在一種方式將序列刪空（例如 $a=[1,2,2,1]$）。

【hack 數據提供】
@潛在了H2O下面。

解題思路

• 核心問題在于如何安排操作序列，使得 $b$ 滿足回文性質。關鍵觀察如下：
• 回文約束：$b$ 的首尾必須相同，次首尾必須相同，依此類推。因此，序列 $a$ 中每個數字的兩次- - 出現必須被分配到 $b$ 的對稱位置上。
• 操作影響：操作 L 或 R 決定了元素進入 $b$ 的順序，從而影響對稱位置的配對。
• 字典序最小：優先選擇 L 操作（因為 L < R），但需保證最終能形成回文。

算法采用貪心策略：

• 初始化配對位置：預處理序列 $a$，為每個位置 $i$ 記錄其配對位置 $j$（即 $a_i=a_j$ 且 $i\ne j$）。
• 嘗試兩種起始操作：由于字典序要求，優先嘗試以 L 開頭（取 $a$ 的開頭元素），如果失敗再嘗試- - 以 R 開頭（取 $a$ 的末尾元素）。
• 模擬匹配過程：基于起始操作，將剩余位置劃分為兩個隊列（左隊列和右隊列），然后貪心地匹配位置對：
• 每次檢查隊列兩端的四種可能匹配：左隊首 vs 左隊尾、左隊首 vs 右隊尾、右隊首 vs 左隊尾、右隊首 vs 右隊尾。
• 如果匹配成功（即兩位置的數字相同），記錄操作并更新隊列；優先選擇能產生 L 操作的匹配以保持字典序最小。
• 構建操作序列：匹配過程中記錄前半部分操作（xian）和后半部分操作（ho），最終輸出為 xian 順序加上 ho 逆序。

算法正確性

• 回文保證：匹配過程確保每個數字的兩次出現被分配到對稱位置，從而 $b$ 滿足 $b_i=b_{2n+1?i}$。
• 字典序最小：優先嘗試 L 開頭，且在匹配中優先選擇 L 操作（對應 xian 添加 L）。如果 L 開頭可行，直接輸出；否則嘗試 R 開頭，但需保證輸出方案是所有可行方案中字典序最小的。
• 可行性判斷：如果兩種起始操作均失敗，則輸出 -1。
• 復雜度分析
• 時間復雜度：每組數據時間復雜度為 $O(n)$。預處理配對位置 $O(n)$，匹配過程每個元素處理一次 $O(n)$。總時間復雜度 $O(\sum n)$，滿足數據范圍 $\sum n\le 5\times 10^5$。
• 空間復雜度：$O(n)$，用于存儲序列、配對位置和隊列。

代碼實現解析

• 以下是基于題目所給代碼的關鍵步驟解釋（代碼已優化）：
• 預處理配對：使用數組 zhiqianshu 記錄數字首次出現的位置，duiyinweizhi[i] 存儲位置 $i$ 的配對位置。
• 起始操作嘗試：調用 solve(‘L’) 優先嘗試 L 開頭；若失敗，再調用 solve(‘R’)。
• 匹配模擬：
• 根據起始操作初始化左隊列（剩余位置的開頭部分）和右隊列（剩余位置的末尾部分）。
• 循環檢查隊列兩端的四種匹配：
• 若左隊首與左隊尾匹配，添加兩個 L 操作（記錄到 xian 和 ho）。
• 若左隊首與右隊尾匹配，添加 L（xian）和 R（ho）。
• 若右隊首與左隊尾匹配，添加 R（xian）和 L（ho）。
• 若右隊首與右隊尾匹配，添加兩個 R 操作（記錄到 xian 和 ho）。
• 若無法匹配，返回失敗。
• 輸出操作序列：順序輸出 xian 中的操作，逆序輸出 ho 中的操作（確保整體操作序列正確）。

示例分析

• 以樣例輸入 $n=5$，$a=[4,1,2,4,5,3,1,2,3,5]$ 為例：

• 預處理配對：位置 $1$ 和 $4$ 均為 $4$，位置 $2$ 和 $7$ 均為 $1$，依此類推。

• 起始操作 L：取 $a[1]=4$，配對位置為 $4$。剩余位置劃分為左隊列 $[2,3]$、右隊列 $[10,9,8,7,6,5]$。

• 匹配過程：

• 左隊首 $2$（$a[2]=1$）與右隊尾 $5$（$a[5]=5$）不匹配；但左隊首 $2$ 與右隊尾 $7$（$a[7]=1$）匹配，添加 L（xian）和 R（ho）。

• 更新隊列后，繼續匹配，最終得到 xian = [‘L’, ‘R’, ‘R’, ‘L’, ‘L’]，ho = [‘R’, ‘R’, ‘R’, ‘R’, ‘L’]。

• 輸出序列：xian 順序輸出 “LRRLL”，ho 逆序輸出 “RRRRL”（即 “LRRLL” + “RRRRL” = “LRRLLRRRRL”）。

• 對于 $n=3$，$a=[3,2,1,2,1,3]$：

• 嘗試 L 開頭（取 $a[1]=3$，配對位置 $6$），但剩余位置無法完成匹配。

• 嘗試 R 開頭（取 $a[6]=3$，配對位置 $1$），剩余位置仍無法匹配，輸出 -1。

詳細代碼

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int a[N*2],zhiqianshu[N*2],duiyinweizhi[N*2],n;
bool solve(char cc)
{deque<int>zuokuohao,youkuohao;vector<int>xian,ho;xian.push_back(cc=='L'?0:6);ho.push_back(0);if (cc=='L'){for(int i=2;i<duiyinweizhi[1];i++) zuokuohao.push_back(i);for(int i=n;i>duiyinweizhi[1];i--) youkuohao.push_back(i);} else{for(int i=1;i<duiyinweizhi[n];i++) zuokuohao.push_back(i);for(int i=n-1;i>duiyinweizhi[n];i--) youkuohao.push_back(i);}while(zuokuohao.size()>0||youkuohao.size()>0){int x1=zuokuohao.size()?zuokuohao.front():0;int x2=youkuohao.size()?youkuohao.front():0;int y1=zuokuohao.size()?zuokuohao.back():0;int y2=youkuohao.size()?youkuohao.back():0;if(duiyinweizhi[x1]==y1){xian.push_back(0);ho.push_back(0);zuokuohao.pop_front();zuokuohao.pop_back();}else if(duiyinweizhi[x1]==y2){xian.push_back(0);ho.push_back(6);zuokuohao.pop_front();youkuohao.pop_back();}else if(duiyinweizhi[x2]==y1){xian.push_back(6);ho.push_back(0);youkuohao.pop_front();zuokuohao.pop_back();}else if(duiyinweizhi[x2]==y2) {xian.push_back(6);ho.push_back(6);youkuohao.pop_front();youkuohao.pop_back();} elsereturn false;}for(vector<int>::iterator it=xian.begin();it!=xian.end();it++)cout<<char('L'+*it);for(vector<int>::reverse_iterator it=ho.rbegin();it!=ho.rend();it++)cout<<char('L'+*it);cout<<'\n';return true;
}
signed main()
{	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int _;cin>>_;while (_--){cin>>n;memset(zhiqianshu,0,sizeof(zhiqianshu));n*=2;duiyinweizhi[0]=-1;for (int i=1;i<=n;i++){cin>>a[i];if(zhiqianshu[a[i]]){duiyinweizhi[zhiqianshu[a[i]]]=i;duiyinweizhi[i]=zhiqianshu[a[i]];}elsezhiqianshu[a[i]]=i;}if(!solve('L')&&!solve('R'))cout<<"-1"<<'\n';}return 0;
}