题解：CF2128B Deque Process
Technocy
·
·
题解
题意
# 思路
我们可以使用双指针 $l$ 和 $r$ 分别表示最左段和最右段的元素，并取 $l$ 和 $r$ 中的最值，然后更新端点，初始状态下我们可以先取最大值，用 $flag$ 来表示上一次取的是最大值还是最小值，那么就有 $2$ 种情况。
- 如果上次取的是最大值，即 $flag=1$，那么这一次我们就取最小值，并更新 $flag=0$。
- 如果上次取的是最小值，即 $flag=0$，那么这一次我们就取最大值，并更新 $flag=1$。
取完最值后，根据取的端点更新 $l$ 和 $r$ 直至 $l>r$，最后输出 $ans$ 即可。
# 证明
假设这一次我取的最大值是 $a_l$，那么下一次我要取的最小值就是 $a_{l+1}$ 和 $a_r$ 两者中的一个，因为这一次我取的最大值是 $a_l$，那么显然 $a_l>a_r$，此时我们分为两种情况讨论。
- $a_{l+1}<a_r$，那么我们就取 $a_{l+1}$ 为最小值，那么接下来就要在 $a_{l+2}$ 和 $a_r$ 之间取最大值。如果取 $a_{l+2}$，那么说明 $a_{l+2}>a_r>a_{l+1}$，显然满足不单调；如果取 $a_r$，同理也满足不单调。
- $a_r<a_{l+1}$，显然同 $a_{l+1}<a_r$ 的情况。
综上，当我们不断取左右端点的最值时最后得到的排列肯定是不单调的，证毕。
# Code
```cpp
#include<bits/stdc++.h>
#define endl "\n"
#define int long long
#define N 100086
using namespace std;
int t,n,a[N];
inline int read();
signed main(){
t=read();
while(t--){
string ans;
int f=0;
n=read();
for(int i=1;i<=n;i++) a[i]=read();
int r=n;
for(int i=1;i<=r;){
if(!f){//初始状态或上一次取最小值时让f=0，以便这次取最大值
if(a[r]>a[i]){
r--;
ans.push_back('R');
}else ans.push_back('L'),i++;
f=1;
}else{//同上
f=0;
if(a[r]<a[i]){
r--;
ans.push_back('R');
}else ans.push_back('L'),i++;//记得更新左右端点
}
}
cout<<ans<<endl;
}
return 0;
}
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x*f;
}
```