P7706

Aryper · 2021-11-16 17:49:33 · 个人记录

「Wdsr-2.7」文文的摄影布置

没赋初值。。。100pts \rightarrow 20pts。。。

然后这题就是一道线段树题。所以说线段树的精髓就在于传参和节点存储信息的类型，类似于 DP。

我们定义 A(\omega) 表示区间 \omega 内的最大的 A 的值，B(\omega) 表示区间 \omega 内的最小的 B 的值。然后就是一些辅助的参数，X(\omega) 表示区间内最大的 A_l-B_r，且（l<r）；Y(\omega) 表示区间内最大的 A_r-B_l，且（l<r）。最后是价值参数 Val(\omega)。

我们现在着手考虑转移就可以了：

然后传参就完了。

还要赋初值。

时间复杂度 O((n+m)\log n)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=5e5,inf=0x3f3f3f3f3f3f3f3f;

ll n,m,op,x,y;

ll a[N+5],b[N+5];

struct sgt{
    ll l,r,A,B,X,Y,Val;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define A(x) tree[x].A
    #define B(x) tree[x].B
    #define X(x) tree[x].X
    #define Y(x) tree[x].Y
    #define Val(x) tree[x].Val
}tree[N*4+5];

void build(ll p,ll l,ll r) {
    l(p)=l;r(p)=r;A(p)=-inf;B(p)=-inf;
    X(p)=-inf;Y(p)=-inf;Val(p)=-inf;
    if(l==r) {A(p)=a[l];B(p)=b[l];return;}
    ll mid=(l+r)>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    A(p)=max(A(p<<1),A(p<<1|1));
    B(p)=min(B(p<<1),B(p<<1|1));
    X(p)=max(max(X(p<<1),X(p<<1|1)),A(p<<1)-B(p<<1|1));
    Y(p)=max(max(Y(p<<1),Y(p<<1|1)),A(p<<1|1)-B(p<<1));
    Val(p)=max(max(Val(p<<1),Val(p<<1|1)),
    max(X(p<<1)+A(p<<1|1),A(p<<1)+Y(p<<1|1)));
}

void chga(ll p,ll x,ll y) {
    if(l(p)==r(p)) {A(p)=y;return;}
    ll mid=(l(p)+r(p))>>1;
    if(x<=mid) chga(p<<1,x,y);
    if(x>mid) chga(p<<1|1,x,y);
    A(p)=max(A(p<<1),A(p<<1|1));
    B(p)=min(B(p<<1),B(p<<1|1));
    X(p)=max(max(X(p<<1),X(p<<1|1)),A(p<<1)-B(p<<1|1));
    Y(p)=max(max(Y(p<<1),Y(p<<1|1)),A(p<<1|1)-B(p<<1));
    Val(p)=max(max(Val(p<<1),Val(p<<1|1)),
    max(X(p<<1)+A(p<<1|1),A(p<<1)+Y(p<<1|1)));
}

void chgb(ll p,ll x,ll y) {
    if(l(p)==r(p)) {B(p)=y;return;}
    ll mid=(l(p)+r(p))>>1;
    if(x<=mid) chgb(p<<1,x,y);
    if(x>mid) chgb(p<<1|1,x,y);
    A(p)=max(A(p<<1),A(p<<1|1));
    B(p)=min(B(p<<1),B(p<<1|1));
    X(p)=max(max(X(p<<1),X(p<<1|1)),A(p<<1)-B(p<<1|1));
    Y(p)=max(max(Y(p<<1),Y(p<<1|1)),A(p<<1|1)-B(p<<1));
    Val(p)=max(max(Val(p<<1),Val(p<<1|1)),
    max(X(p<<1)+A(p<<1|1),A(p<<1)+Y(p<<1|1)));
}

sgt ask(ll p,ll l,ll r) {
    if(l(p)>=l&&r(p)<=r) return tree[p];
    ll mid=(l(p)+r(p))>>1;
    sgt L,R,res;
    if(l>mid) return ask(p<<1|1,l,r);
    if(r<=mid) return ask(p<<1,l,r);
    L=ask(p<<1,l,r);R=ask(p<<1|1,l,r);
    res.A=max(L.A,R.A);
    res.B=min(L.B,R.B);
    res.X=max(max(L.X,R.X),L.A-R.B);
    res.Y=max(max(L.Y,R.Y),R.A-L.B);
    res.Val=max(max(L.Val,R.Val),max(L.X+R.A,L.A+R.Y));
    return res;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=n;i++) {
        a[i]=read();
    }

    for(ll i=1;i<=n;i++) {
        b[i]=read();
    }

    build(1,1,n);

    while(m--) {
        op=read();x=read();y=read();
        if(op==1) {
            chga(1,x,y);
        }
        if(op==2) {
            chgb(1,x,y);
        }
        if(op==3) {
            writeln(ask(1,x,y).Val);
        }
    }

    return 0;
}