「JOI Open 2019」三级跳
前言
我是菜逼，我是菜逼，我是菜逼！
题目
LOJ
讲解
牛逼性质题。性质就是考虑选前两个位置 \(i,j\)，如果存在一个位置 \(mid(i
而且不存在这样的 \(mid\) 的 \((i,j)\) 数对是 \(O(n)\) 级别。(注意断句)
然后知道这个就好办了，先单调栈求出所有的这些数对，然后把询问按左端点从大到小排序，从右往左地对每个位置 \(pos\) 维护以它为右端点的答案最大值，显然这个东西可以用线段树维护。
时间复杂度 \(O(n\log_2n)\)。
代码
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 500005;
int n,m,tl;
int a[MAXN],ans[MAXN],st[MAXN];
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
vector > Q[MAXN],o[MAXN];//(l,ID)
#define lc (x<<1)
#define rc (x<<1|1)
int val[MAXN<<2],tag[MAXN<<2],s[MAXN<<2];
void calc(int x,int v){
tag[x] = Max(tag[x],v);
s[x] = Max(s[x],val[x]+v);
}
void up(int x){s[x] = Max(s[lc],s[rc]);}
void down(int x){if(!tag[x])return;calc(lc,tag[x]);calc(rc,tag[x]);}
void Build(int x,int l,int r){
if(l == r){val[x] = a[l];return;}
int mid = (l+r) >> 1;
Build(lc,l,mid); Build(rc,mid+1,r);
val[x] = Max(val[lc],val[rc]);
}
void Modify(int x,int l,int r,int ql,int qr,int v){
if(ql > qr) return;
if(ql <= l && r <= qr){calc(x,v);return;}
int mid = (l+r) >> 1; down(x);
if(ql <= mid) Modify(lc,l,mid,ql,qr,v);
if(mid+1 <= qr) Modify(rc,mid+1,r,ql,qr,v);
up(x);
}
int Query(int x,int l,int r,int ql,int qr){
if(ql <= l && r <= qr) return s[x];
int mid = (l+r) >> 1,ret = 0; down(x);
if(ql <= mid) ret = Max(ret,Query(lc,l,mid,ql,qr));
if(mid+1 <= qr) ret = Max(ret,Query(rc,mid+1,r,ql,qr));
return ret;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read();
for(int i = 1;i <= n;++ i) a[i] = Read();
m = Read();
for(int i = 1;i <= m;++ i){
int l = Read(),r = Read();
Q[l].emplace_back(r,i);
}
for(int i = 1;i <= n;++ i){
while(tl && a[st[tl]] < a[i]) o[st[tl]].emplace_back(st[tl],i),--tl;
if(tl) o[st[tl]].emplace_back(st[tl],i);
st[++tl] = i;
}
Build(1,1,n);
for(int i = n;i >= 1;-- i){
for(auto &A : o[i]){
Modify(1,1,n,A.second*2-A.first,n,a[A.first]+a[A.second]);
}
for(auto &A : Q[i])
ans[A.second] = Query(1,1,n,i+2,A.first);
}
for(int i = 1;i <= m;++ i) Put(ans[i],'\n');
return 0;
}