Lanterns (dp 紫 线段树 二分 维护dp)
Lanterns - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
让所有点被覆盖，那么状态可以设计成覆盖一段前缀，并且中间不允许出现断点
由于CF崩了，所以暂时没提交代码。
记f(i) 为前 i 个灯笼点亮的最长前缀。
由于答案具有保留性，所以单调性成立。
由此推转移方程。
共鸣：i 与 t (i > t) 号灯，可以完全覆盖1至i ，条件 f(t)>= i - a[i] -1 至少自给自足。
max_range(l,r) 区间[l,r]最大的i + a[i]
- f(i) = f(i-1) 如果前i-1盏灯无法覆盖i
- 反之则让f(i) = max(f(i-1),i+a[i])
- 第三种情况，二分找最早的共鸣点 取max(i-1,max_range(t+1,i-1))
对于第二种情况，我们在3中特判。
from i ：i如果往左看，from i 到 i-1 就向右看。
如果要回退，即L则让from i = t;因为第一个可能不向右看的就是
t+1，i之内的都向右看，倒着赋值即可。
AC 代码
#include<bits/stdc++.h>
using namespace std;
struct node{
int id,mx;
};
struct sgt{
int a[1000100];
int mx[4000100];
int id[4000100];
void build(int p,int l,int r){
if(l == r){
mx[p] = a[l];
id[p] = l;
return;
}
int mid = (l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
if(mx[p*2]>mx[p*2+1]){
mx[p] = mx[p*2];
id[p] = id[p*2];
}
else{
mx[p] = mx[p*2+1];
id[p] = id[p*2+1];
}
}
void update(int p,int L,int R,int ID,int x){
if(L == R){
mx[p] = x;
return;
}
int mid = (L+R)/2;
if(ID <= mid)update(p*2,L,mid,ID,x);
else update(p*2+1,mid+1,R,ID,x);
if(mx[p*2]>mx[p*2+1]){
mx[p] = mx[p*2];
id[p] = id[p*2];
}
else{
mx[p] = mx[p*2+1];
id[p] = id[p*2+1];
}
}
node query(int p,int L,int R,int l,int r){
if(l > r)return node{0,0};
if(l == L&&R == r){
return node{id[p],mx[p]};
}
int mid = (L+R)/2;
if(r <= mid){
return query(p*2,L,mid,l,r);
}
else if(l > mid){
return query(p*2+1,mid+1,R,l,r);
}
else{
node LL = query(p*2,L,mid,l,mid);
node RR = query(p*2+1,mid+1,R,mid+1,r);
if(LL.mx > RR.mx){
return LL;
}
else{
return RR;
}
}
}
int found(int l,int r,int L,int R,int q){
if(query(1,L,R,l,r).mx < q)return -1;
if(l == r)return l;
int mid = (l+r)/2;
int Lrange = query(1,L,R,l,mid).mx;
int Rrange = query(1,L,R,mid+1,r).mx;
if(Lrange < q&& Rrange < q){
return -1;
}
else if(Lrange >= q){
return found(l,mid,L,R,q);
}
else{
return found(mid+1,r,L,R,q);
}
}
}t1,t2;
int t;
int a[300010];
int f[300010];
char res[300010];
int from[300010];
int main(){
cin>>t;
while(t--){
int n;
cin>>n;
for(int i = 1;i <= n;i++){
cin>>a[i];
f[i] = 0;
t2.a[i] = i + a[i];
t1.a[i] = 0;
}
t1.build(1,1,n);//维护f i
t2.build(1,1,n);//维护i + a[i]
f[0] = f[1] = 0;
for(int i = 2;i <= n;i++){
if (!a[i]) { f[i] = f[i - 1];from[i] = i; continue; }
int t = lower_bound(f, f + i, i - a[i] - 1) - f;//找最早的共鸣点
from[i] = t;//L
if (t == i) f[i] = f[i - 1];//
else{
f[i] = max(i-1, t2.query(1,1,n,t+1,i-1).mx);
if (f[i - 1] > f[i]) f[i] = f[i - 1], from[i] = i;//R
if (f[i - 1] >= i && i + a[i] > f[i]) {
f[i] = i + a[i];
from[i] = i;//R
}
}
}
if(f[n] < n){
cout<<"NO"<<endl;
}
else {
puts("YES");
int cur = n;
while (cur) {
if (from[cur] == cur) res[cur] = 'R', --cur;
else {
res[cur] = 'L';
fill(res + from[cur] + 1, res + cur, 'R');
cur = from[cur];
}
}
res[n + 1] = 0; puts(res + 1);
}
}
}
原文地址：https://blog.csdn.net/2301_77025310/article/details/142426505
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！