JOI2019 Triple Jump题解

· · 题解

题意：

给出长度为 n 的数组 a ，求三元组最大和，满足三元组严格升序且后两者差大于前两者差。

用 (I,J,K) 分别表示其对应三元组中哪一个元素，考虑有效的点对 (i,j) 个数。

发现对于每一个区间内的答案所对应的 (i,j) 一定为一个子区间内的最大与次大值。

对于区间 [i,j] ，若无右端点限制，这个区间内的 (I,J) 最优值一定为最大与次大值。原因显然。

而所有区间的最大值与次大值点对数的数量级是 \mathrm{O(n)} 的。（相同数值按照下标定优先级）

这里的证明可以考虑单调栈过程。寻找这些对也可以直接通过单调栈求解。

然后我们现在得到了 \mathrm{O(n)} 对点对。怎么求答案呢。

我们可以把询问离线下来，按照下标顺序依次将点对丢进集合处理其对答案贡献。

可以这样维护：

枚举左端点，计算每一个位置作为 k 的答案。所有以当前点为 I 的点对 (i,j) 对每一个合法位置造成的贡献。合法位置是一个后缀。

设 b_x 表示上面说的以 x 为 K 的最大贡献，这个贡献的格式是 b_x=max(b_x,a_x+val) ，后面的 val 是 a_i+a_j ，对同一对点对 (i,j) 是定值。这个可以直接线段树维护。查询就直接区间最值即可。

int pre[N],suf[N];

int stk[N],tot;
int a[N];

struct Seg_Tree{
    int t[N<<2],mx[N<<2];
    int tag[N<<2];
    void pushup(int x){
        t[x]=max(t[ls],t[rs]);
        t[x]=max(t[x],mx[x]+tag[x]);
    }
    void pushdown(int x){
        if(tag[ls]<tag[x]){
            tag[ls]=tag[x];
            t[ls]=max(t[ls],mx[ls]+tag[ls]);
        }
        if(tag[rs]<tag[x]){
            tag[rs]=tag[x];
            t[rs]=max(t[rs],mx[rs]+tag[rs]);
        }
    }
    void update(int x,int l,int r,int L,int R,int val){
        if(L<=l&&r<=R){
            tag[x]=max(tag[x],val);
            t[x]=max(t[x],tag[x]+mx[x]);
        }else{
            pushdown(x);
            if(L<=mid)
                update(ls,l,mid,L,R,val);
            if(R>mid)
                update(rs,mid+1,r,L,R,val);
            pushup(x);
        }
    }
    int query(int x,int l,int r,int L,int R){
        if(L<=l&&r<=R)
            return t[x];
        pushdown(x);
        int ans=0;
        if(L<=mid)
            ans=max(ans,query(ls,l,mid,L,R));
        if(R>mid)
            ans=max(ans,query(rs,mid+1,r,L,R));
        return ans;
    }
    void build(int x,int l,int r){
        tag[x]=0;
        if(l==r)
            t[x]=mx[x]=a[l];
        else{
            build(ls,l,mid);
            build(rs,mid+1,r);
            mx[x]=max(mx[ls],mx[rs]);
        }
    }
}T;

pir p[N<<1];

struct Que{
    int l,r,id;
    bool operator<(Que &ano)const{
        return l>ano.l;
    }
}Q[N];

int ans[N];

signed main(){
    int n=read(),q=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=n;i++){
        while(tot>0&&a[stk[tot]]<a[i])
            suf[stk[tot--]]=i;
        pre[i]=stk[tot];
        stk[++tot]=i;
    }
    for(int i=1;i<=n;i++){
        if(pre[i])
            p[++tot]={pre[i],i};
        if(suf[i])
            p[++tot]={i,suf[i]};
    }
    sort(p+1,p+1+tot);
    for(int i=1;i<=q;i++)
        Q[i]={read(),read(),i};
    sort(Q+1,Q+1+q);
    T.build(1,1,n);
    for(int l=n,nw=tot,nwq=1;l>=1&&nw>=1;l--){
        while(p[nw].fi==l){
            int L=p[nw].se+(p[nw].se-p[nw].fi),R=n;
            nw--;
            if(L>R)
                continue;
            T.update(1,1,n,L,R,a[p[nw+1].fi]+a[p[nw+1].se]);
        }
        while(Q[nwq].l==l){
            ans[Q[nwq].id]=T.query(1,1,n,Q[nwq].l,Q[nwq].r);
            nwq++;
        }
    }
    for(int i=1;i<=q;i++)
        print(ans[i]),pc('\n');
    return 0;
}