题解：P11392 [JOI Open 2019] 三段跳び
Purslane
·
·
题解
Solution
感觉调整的东西错了啊，倒闭了 /ll
考虑分析最优情况下 (a,b,c) 的结构。如果 \exists a < i < b 使得 v_i \ge \min\{v_a,v_b\}，则可以将 a 和 b 中的一个替换为 i。
这样得出 \min\{v_a,v_b\} > \max_{a<i<b} v_i。这很类似 JOISC2017D，得到只有 O(n) 对可能的 (a,b)。
一对 (a,b) 确定后，它可以对 \ge 2b-a+1 的 c 都产生贡献。
随便扫描线，可以将问题转化为：
维护序列 a、b，有两种操作（b 序列给定，a 初始全是 0）
1 l r v，表示 a_i \leftarrow \max\{a_i,v\}，对 l \le i \le r。2 l r，询问 \max_{l \le i \le r} \{a_i+b_i\}。
这个东西看着就可以随便维护。
```cpp
#include<bits/stdc++.h>
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5e5+10;
int n,q,a[MAXN],mx[MAXN<<2],ma[MAXN<<2],tag[MAXN<<2];
void build(int k,int l,int r) {
if(l==r) return mx[k]=ma[k]=a[l],void();
build(lson,l,mid),build(rson,mid+1,r);
return mx[k]=max(mx[lson],mx[rson]),ma[k]=max(ma[lson],ma[rson]),void();
}
void push_down(int k,int l,int r) {
ma[lson]=max(ma[lson],mx[lson]+tag[k]),ma[rson]=max(ma[rson],mx[rson]+tag[k]);
tag[lson]=max(tag[lson],tag[k]),tag[rson]=max(tag[rson],tag[k]);
return ;
}
void update(int k,int l,int r,int x,int y,int v) {
if(x<=l&&r<=y) return ma[k]=max(ma[k],mx[k]+v),tag[k]=max(tag[k],v),void();
push_down(k,l,r);
if(x<=mid) update(lson,l,mid,x,y,v);
if(y>mid) update(rson,mid+1,r,x,y,v);
return ma[k]=max(ma[lson],ma[rson]),void();
}
int query(int k,int l,int r,int x,int y) {
if(x<=l&&r<=y) return ma[k];
push_down(k,l,r);
if(y<=mid) return query(lson,l,mid,x,y);
if(x>mid) return query(rson,mid+1,r,x,y);
return max(query(lson,l,mid,x,y),query(rson,mid+1,r,x,y));
}
int ans[MAXN];
vector<pair<int,int>> qr[MAXN];
vector<int> upd[MAXN];
int main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
ffor(i,1,n) cin>>a[i];
build(1,1,n),cin>>q;
ffor(i,1,q) {int l,r;cin>>l>>r,qr[l].push_back({r,i});}
stack<int> st;
ffor(i,1,n) {
while(!st.empty()&&a[i]>a[st.top()]) st.pop();
if(!st.empty()) upd[st.top()].push_back(i);
st.push(i);
}
while(!st.empty()) st.pop();
roff(i,n,1) {
while(!st.empty()&&a[i]>a[st.top()]) st.pop();
if(!st.empty()) upd[i].push_back(st.top());
st.push(i);
}
roff(i,n,1) {
for(auto id:upd[i]) if(2*id-i<=n) update(1,1,n,2*id-i,n,a[i]+a[id]);
for(auto pr:qr[i]) ans[pr.second]=max(ans[pr.second],query(1,1,n,i,pr.first));
}
ffor(i,1,q) cout<<ans[i]<<'\n';
return 0;
}
```