当前位置：首页 > news >正文

Lanterns (dp 紫线段树二分维护dp)

news 来源：原创 2024/9/22 18:07:44

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 it2.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;//Lif (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;//Rif (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);}}
}