题解【SR2.7-T2】【文文的摄影布置】

囧仙 · 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)\}

题解

在下文中，不妨记一段区间 [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 又可以分为如下三类：
P(\omega)=\max\{P(\alpha),P(\beta),X(\alpha)-Y(\beta)\}
同理，我们可以得到 Q(\omega) 的维护方法。

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

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;
}

题解 【SR2.7-T2】【文文的摄影布置】

题目大意

题解

参考代码

题解【SR2.7-T2】【文文的摄影布置】