自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:32:21，当前版本为作者最后更新于2021-06-06 21:30:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目大意

给定两个长度均为 $n$ 的数组 $A_i$ 和 $B_i$ 。有 $m$ 次操作，每次操作将 $A_x$ 修改为 $y$ 或者将 $B_x$ 修改为 $y$ 或者求出

$$\max_{x\le i<j\le y} \{A_i+A_j-\min_{i < k < j}(B_k)\} $$

$1\le n,m\le 5\times 10^5$ 。

题解

在下文中，不妨记一段区间 $[x,y]$ 上的答案为 $\Psi(x,y)$ ，也就是

$$\Psi(x,y)=\max_{x\le a<b<c\le y} \{A_a-B_b+A_c\}$$

那么对于每次询问，问题转化为了计算 $\Psi(x_i,y_i)$ 的值。考虑使用线段树解决本题。特别地，下文中记 $\Psi(\omega)$ 表示线段树上节点 $\omega$ 对应的区间求得的 $\Psi$ 值。

非常自然的想法是，每个节点都要维护它所代表的这段区间的最优解。也就是说，假如一个节点 $\omega$ 维护了区间 $[l,r]$ ，那么它就要存储 $\Psi(l,r)$ 。问题在于，怎么从它的两个子节点 $\alpha,\beta$ 的 $\Psi$ 值更新到它本身。

• 首先考虑最优的 $a,b,c$ 在同一个儿子中的情况。显然，这样对答案的更新就是 $\max\{\Psi(\alpha),\Psi(\beta)\}$ 。

• 然后考虑 $a$ 在 $\alpha$ 中，而 $c$ 在 $\beta$ 中的情况。考虑第二张照片在哪。可以发现，假如第二张照片在 $\alpha$ 中，那么 $c$ 的最优解必定是 $\beta$ 中 $A$ 的值最大的那个元素。同理，假如第二张照片在 $\beta$ 中，那么 $a$ 的最优解必定是 $\alpha$ 中 $A$ 的值最大的那个元素。而维护 每个节点对应区间上的 $\max \{A_i\}$ 是相当容易的。

  于是，问题转化为了在一个节点维护的区间中，这样的两个值：

  $$\max_{l\le a<b\le r}\{A_a-B_b\}$$ $$\max_{l\le b<c\le r}\{A_c-B_b\}$$

  不妨分别记为 $P(\omega)$ 和 $Q(\omega)$ 。考虑怎么从它的左右儿子上转移过来。

  对于 $P(\omega)$ ，其最优的 $a,b$ 又可以分为如下三类：

  • $a,b$ 都在左儿子 $\alpha$ 中。这部分的贡献为 $P(\alpha)$ 。

  • $a,b$ 都在右儿子 $\beta$ 中。这部分的贡献为 $P(\beta)$ 。

  • $a$ 在左儿子中，而 $b$ 在右儿子中。显然这部分贡献应该是左儿子中 $A$ 的最大值减去右儿子中 $B$ 的最小值。不妨把一个节点维护的区间上 $A_i$ 的最大值记为 $X(\omega)$ ，而 $B_i$ 的最小值记为 $Y(\omega)$ ，那么有：

  $$P(\omega)=\max\{P(\alpha),P(\beta),X(\alpha)-Y(\beta)\} $$

  同理，我们可以得到 $Q(\omega)$ 的维护方法。

最终，我们能得到所有东西的转移方程式：

$$\begin{gathered} X(\omega)=\max\{X(\alpha),X(\beta)\},Y(\omega)=\min\{Y(\alpha),Y(\beta)\} \cr \begin{aligned} P(\omega) &=\max\{P(\alpha),P(\beta),X(\alpha)-Y(\beta)\} \cr Q(\omega) &=\max\{Q(\alpha),Q(\beta),X(\beta)-Y(\alpha)\} \cr \end{aligned} \cr \Psi(\omega)=\max\{\Psi(\alpha),\Psi(\beta),P(\alpha)+X(\beta),X(\alpha)+Q(\beta)\} \end{gathered}$$

对于查询操作，我们只要把涉及到的区间从左往右一个一个合并起来，再查询它的 $\Psi$ 值就行了。具体可以见代码。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =5e8,MAXN=5e5+3,SIZ=MAXN*4;
int A[MAXN],B[MAXN];
#define lc(t) (t<<1)
#define rc(t) (t<<1|1)
struct Node{
    int a,b,p,q,w; Node():a(-INF),b(INF),p(-INF),q(-INF),w(-INF){}
    Node operator +(Node t){
        Node r; r.a=max(a,t.a),r.b=min(b,t.b),r.w=max(w,t.w);
        r.p=max(t.p,max(p,a-t.b)),r.q=max(q,max(t.q,t.a-b));
        r.w=max(r.w,max(p+t.a,a+t.q)); return r;
    }
}W[SIZ];
void sst(int t,int l,int r,int p){
    if(l==r) W[t].a=A[l],W[t].b=B[l]; else {
        int c=l+r>>1; p<=c?sst(lc(t),l,c,p):sst(rc(t),c+1,r,p);
        W[t]=W[lc(t)]+W[rc(t)];
    }
}
void qry(int t,int l,int r,int a,int b,Node &o){
    if(a<=l&&r<=b) o=o+W[t]; else {
        int c=l+r>>1;
        if(a<=c) qry(lc(t),l  ,c,a,b,o);
        if(b> c) qry(rc(t),c+1,r,a,b,o);
    }
}
void bld(int t,int l,int r){
    if(l==r){W[t].a=A[l],W[t].b=B[l]; return;}
    int c=l+r>>1; bld(lc(t),l,c),bld(rc(t),c+1,r);
    W[t]=W[lc(t)]+W[rc(t)];
}
int n,q,m,p;
int qread(){
    int w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
int main(){
    n=qread(),m=qread(); up(1,n,i) A[i]=qread(); up(1,n,i) B[i]=qread();
    bld(1,1,n); up(1,m,i){
        int op=qread(),x=qread(),y=qread(); Node r; switch(op){
            case 1: A[x]=y,sst(1,1,n,x); break;
            case 2: B[x]=y,sst(1,1,n,x); break;
            case 3: qry(1,1,n,x,y,r),printf("%d\n",r.w);
        }
    }
    return 0;
}