自动搬运

查看原文

来自洛谷，原作者为

	unicorn1220 这个家伙很菜，什么也没有留下

搬运于2025-08-24 23:06:57，当前版本为作者最后更新于2025-08-07 11:37:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[JOI Open 2019] Triple Jump

题意

给定一个长为 $N$ 的序列 $A$。有 $Q$ 个查询，每次给定 $L,R$，求出满足以下条件的三元组 $(i,j,k)$ 使得 $A_i+A_j+A_k$ 最大。

• $L \leq i<j<k \leq R$
• $j-i \leq k-j$

题解

暴力枚举情况太多，所以考虑去掉某些无需枚举的情况。

什么时候可以扔掉一个情况 $p_1(i_1,j_1,k_1)$ 呢？当存在一个 $p_2(i_2,j_2,k_2)$ 一定不劣于 $p_1$ 时。

这里的不劣于，需要考虑两个条件。第一，$p_2$ 的贡献一定要比 $p1$ 大。第二，如果 $p1$ 对于一组 $(L,R)$ 合法，那么 $p2$ 也合法，即区间 $[i_2,k_2]$ 被 $[i_1,k_1]$ 包含。

也就是说，满足 $A_{i_1}+A_{j_1}+A_{k_1} \leq A_{i_2}+A_{j_2}+A_{k_2}$，且 $i_1 \leq i_2 < k_2 \leq k_1$。

然而，这种约束情况一不太好找，二过于苛刻，可能会导致去掉的情况不够多。

我们观察 $j-i \leq k-j$ 这个式子，显然当我们钦定 $i,j$ 时，$k$ 的取值范围是一个后缀，准确来说是 $[2j-i,n]$。这样的话，如果我们缩小区间 $[i,j]$，那么 $k$ 的取值范围一定是只会变大的。

我们惊奇的发现，这个缩小后的区间，正好对应了 $p2$。于是我们把约束条件中的 $k$ 去掉，变成 $A_{i_1}+A_{j_1} \leq A_{i_2}+A_{j_2}$，且 $i_1 \leq i_2 < j_2 \leq j_1$。这时，$i,j$ 的贡献保证了不劣，而因为 $p2$ 的区间 $[i_2,j_2]$ 更小，所以 $k_2$ 的取值范围更大，也就保证了不劣。

现在来看还剩下多少有用情况。上面的式子意味着对于 $i,j$，如果他们之间存在 $i'$ 使得 $A_i < A_{i'}$ 或 $A_j < A_{i'}$，那么 $(i,j)$ 就会被 $(i',j)$ 替代，它就没用了。即有用区间可以表示为 $[i,j]$ 使得 $\min(a[i],a[j]) > \max^{j-1}_{k=i+1}(a[k])$。我们令 $L_i$ 为 $i$ 之前最后一个比 $A_i$ 大的 $A_{L_i}$， $R_i$ 为 $i$ 之后第一个比 $A_i$ 大的 $A_{R_i}$。此时，所有的 $(L_i,i]$ 和 $[i,R_i)$ 即可描述所有的有用情况，最多 $2n$ 种。

这么少的情况可以直接用线段树维护。对于所有有用情况 $(l_i,r_i)$ ,区间 $[2j-i,n]$ 的所有数都可以获得 $A_{l_i}+A_{r_i}$ 的贡献，取 $\max$ 加上原本的数即为答案。而 $L_i,R_i$ 可以随便用单调栈维护。加上查询总复杂度为 $O((n+q)\log n)$。

最后，在处理询问时，有用区间应该按左端点降序插入线段树，同时边插边把当前左端点的询问做了，因为我们要保证插入线段树的区间也在询问范围内。

代码放个主函数吧。

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);scanf("%lld",&Q);
    for(int i=1,ai,bi;i<=Q;i++) scanf("%lld%lld",&ai,&bi),ask[ai].push_back(make_pair(bi,i));
    for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&a[i]>a[q.top()]) q.pop();
        if(!q.empty()) qj[q.top()].push_back(i);
        q.push(i);
    }//找Li
    while(!q.empty()) q.pop();
    for(int i=n;i>=1;i--)
    {
         while(!q.empty()&&a[i]>a[q.top()]) q.pop();
        if(!q.empty()) qj[i].push_back(q.top());
        q.push(i);
    }//找Ri
    for(int i=n;i>=1;i--)//倒着插入
    {
        for(int j:qj[i]) update(1,1,n,2*j-i,n,a[j]+a[i]);
        for(auto j:ask[i]) ans[j.second]=query(1,1,n,i,j.first);
    }
    for(int i=1;i<=Q;i++) printf("%lld\n",ans[i]);
    return 0;
}