[CF1476F]Lanterns

subject

Portal to CF

Ideas

First of all, this is a $\mathtt{d}\mathtt{p}$ problem . Then we need to find the recursive subproblem .

Generally, the case of a particular value will be enumerated . For example, the last lantern . Consider which lanterns it covers ？ The unlighted lanterns are discrete , no way . Then you can consider who covers it .

You might as well set up lanterns $j$ Covered it . that $(j,n]$ All the lanterns illuminate the lanterns on the left , The illuminated lantern continues to illuminate to the left , Until some $p_i=0$ stop it （ I can't see the left ）. There's only one left $[1,i)$ My lantern is not illuminated , See if they can light up internally .

This is a $\mathcal{O}(n^2)$ Of . be aware $\mathtt{d}\mathtt{p}$ Values are $\mathtt{b}\mathtt{o}\mathtt{o}\mathtt{l}$ type , Consider changing it to $\mathtt{i}\mathtt{n}\mathtt{t}$ type , So as to reduce the information that needs to be processed during the transfer —— Obviously, it's using $\mathtt{i}\mathtt{n}\mathtt{t}$ Dynamically achieve “ The illuminated lantern continues to illuminate to the left ” The process of , Just store the number of lanterns that are illuminated .

Of course, there is no need for recursion , Direct recursion . Say it completely , remember $f(i)$ For the former $i$ The longest prefix length that a lantern can illuminate . There are two kinds of transfer , Corresponding to the original enumeration $j$ And continue to iterate back to illuminate .

• Take whatever you like $j⩾i$ Satisfy $j-p_j⩽f(i-1)+1$, be $f(j)$ You can use ${\max }_{t=i}^{j-1}t+p_t$ to update . Specially , if $j=i$, use $(j-1)$ to update .
• if $f(i-1)⩾i$, be $f(i)$ You can use $\max \{f(i-1),i+p_i\}$ to update .

The most interesting thing is , The first kind of transfer does not need to $f(i-1)$ To update , Because it was originally when it could not continue to illuminate , You need to enumerate again $j$ . Understand from the formula , It's just $f(i-1)<i$ We need to consider the first kind of transfer , here $t=i$ Have already let $\max$ Take a larger value .

At this time, use the form filling method . For one $j$, Its optimal $i$ The smaller the better ; So the goal is to find the smallest $i$ Satisfy $f(i-1)⩾j-p_j-1$ . Monotonic stack can be achieved by two points . Query the maximum value to $\mathtt{S}\mathtt{T}$ surface , Or any data structure . Time complexity $\mathcal{O}(n\log n)$ .

Code

#include <cstdio> // JZM yydJUNK!!!
#include <iostream> // XJX yyds!!!
#include <algorithm> // XYX yydLONELY!!!
#include <cstring> // (the STRONG long for LONELINESS)
#include <cctype> // ZXY yydSISTER!!!
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
    
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void getMax(int &x, const int &y){
    
	if(x < y) x = y;
}

const int MAXN = 300005;
int p[MAXN];
namespace ST{
    
	const int LOGN = 19;
	int st[LOGN][MAXN], logtwo[MAXN];
	void init(int n){
    
		rep(i,2^(logtwo[1]=0),n) logtwo[i] = logtwo[i>>1]+1;
	}
	void build(int n){
    
		rep(i,1,n) st[0][i] = i+p[i];
		rep(j,0,LOGN-2) rep(i,1,n-(2<<j)+1)
			st[j+1][i] = max(st[j][i],st[j][i+(1<<j)]);
	}
	inline int query(const int &l, const int &r){
    
		const int &k = logtwo[r-l+1];
		return max(st[k][l],st[k][r-(1<<k)+1]);
	}
}

int best[MAXN], dp[MAXN], sta[MAXN], top;
void paint(int x){
    
	if(!x) return ;
	if(best[x] == -1){
    
		paint(x-1), putchar('R');
		return ; // covered
	}
	paint(best[x]);
	rep(i,best[x]+1,x-1) putchar('R');
	putchar('L'); // x is chosen to be left
}

bool cmp(const int &x, const int &y){
    
	return dp[x] < y;
}
int main(){
    
	ST::init(MAXN-1);
	for(int T=readint(); T; --T){
    
		int n = readint();
		rep(i,1,n) p[i] = readint();
		ST::build(n), sta[0] = top = 0;
		for(int i=1; i<=n; ++i){
    
			sta[top+1] = i; // force best[i] = i
			dp[i] = (dp[i-1] >= i) ? max(dp[i-1],i+p[i]) : 0;
			best[i] = *lower_bound(sta,sta+top+1,i-p[i]-1,cmp);
			int got = (best[i] == i) ? -1 : ((best[i] == i-1) ?
				i-1 : ST::query(best[i]+1,i-1)); // at least j-1
			if(dp[i] < got) dp[i] = got; else best[i] = -1;
			if(dp[sta[top]] < dp[i]) sta[++ top] = i;
		}
		if(dp[n] < n) puts("NO");
		else puts("YES"), paint(n), putchar('\n');
	}
	return 0;
}