Lanterns
_ANIG_
·
·
个人记录
传送门
先考虑 dp 状态。如果只存一个 0/1 太浪费了。
可以发现最后一个位置一定是 'L'，所以可以想到把 f_n 定义为考虑了前 n 个，其中第 n 个为 ‘L’，然后枚举上一个 'L' 的位置转移。
dp 要存的东西也就比较好想了：最左边的没有被照亮的灯笼编号最大能是多少。
考虑如何从 f_i 转移到 f_n。
如果 n 这个位置能把第 f_i 个位置的空位填了，也就是 n-p_n\le f_i，则从 1 到 n 这些地方显然已经被填满了，而这中间的点都是 'R'，所以当前能填到的点是中间所有能填到的点的最大值。则贡献为 \max(\max\limits_{i<j<n}j+p_j+1,n+1)。
还有种情况是 n 不能直接填到 f_i，但是 f_i>i，并且 i-f_i 之间有个 'R' 的灯笼能填掉 f_i，并且能一直往右顺着填到 n。
可以先预处理每个数往右连着最多能填到哪，记为 g_i，则如果 n\le g_{f_i-1}，也要贡献，贡献的值同上。
如果 n 填不掉 i，则最左边的空还是 f_i，贡献为 f_i。
时间复杂度 $O(n\log n)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
int n,t,p[N],f[N],lst[N],g[N],qz[N],zd[N],fs[N][20];
vector<char>rs;
deque<int>q;
int gets(int l,int r){
if(l>r)return 0;
int k=__lg(r-l+1);
return max(fs[l][k],fs[r-(1<<k)+1][k]);
}
signed main(){
cin>>t;
while(t--){
q.clear();
cin>>n;
for(int i=1;i<=n;i++)scanf("%lld",&p[i]),f[i]=0,fs[i][0]=i+p[i]+1;
for(int i=1;i<=18;i++)for(int j=1;j<=n-(1<<i)+1;j++)fs[j][i]=max(fs[j][i-1],fs[j+(1<<i-1)][i-1]);
for(int i=n;i>=1;i--){
if(!p[i])g[i]=i;
else if(i+p[i]>n)g[i]=n+1;
else g[i]=g[i+p[i]];
}
f[0]=1;
for(int i=1;i<=n;i++){
int mx=0;
f[i]=qz[i-1];lst[i]=zd[i-1];
if(i-p[i]<=f[i-1]){
if(i>f[i])lst[i]=i-1,f[i]=i;
}
while(q.size()&&g[f[q.front()]-1]<i)q.pop_front();
if(q.size())if(gets(q.front()+1,i-1)>f[i])lst[i]=q.front(),f[i]=gets(q.front()+1,i-1);
int l=0,r=i-1;
while(l<r){
int mid=l+r>>1;
if(f[mid]>=i-p[i])r=mid;
else l=mid+1;
}
if(f[l]>=i-p[i]&&gets(l+1,i-1)>f[i])lst[i]=l,f[i]=gets(l+1,i-1);
if(f[i]>qz[i-1])qz[i]=f[i],zd[i]=i;
else qz[i]=qz[i-1],zd[i]=zd[i-1];
if(f[i]>i+1)q.push_back(i);
}
if(f[n]<=n){
puts("NO");
continue;
}
puts("YES");
int nw=n;
rs.clear();
while(nw>0){
int t=lst[nw];
rs.push_back('L');
for(nw-=1;nw>t;nw--)rs.push_back('R');
}
for(int i=n-1;i>=0;i--)putchar(rs[i]);
puts("");
}
}
```