题解：P11392 [JOI Open 2019] 三级跳 / Triple Jump

· · 题解

[JOI Open 2019] Triple Jump

题意

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

题解

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

什么时候可以扔掉一个情况 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;
}