P7706 「Wdsr-2.7」文文的摄影布置
题目背景
作为幻想乡知名的记者射命丸文，文文常常需要为文文新闻采集相关的照片素材。
具体而言，文文会采集一大串的图片，用于为新的一期报纸提供图片。作为一份简短的快报，文文会从素材库中使用三张图片，第一张放在开头，第三张放在结尾，用于激发读者的阅读兴趣（毕竟，报纸的开头和结尾是最容易被看到的）；第二张，则是为了帮助读者理解相关内容。
可是作为无双风神，文文收集的照片实在是太多了，以至于一时半会儿处理不过来。按照惯例，文文找到了在一旁吃瓜的你，希望你能帮她解决困难。
题目描述
尽管图片非常多，但幸运的是，文文已经将它们排成了一列，从左到右分别编号为 \(1 \sim n\)，文文选取的三张图片，应该是一个长度为 \(\bf 3\) 的子序列。（不妨设选取的照片的序号为 \(i,j,k\) ，则必须要有 \(i<j<k\) ）。
此外，文文给每张照片定了一个吸引度 \(A_i\) 与大小 \(B_i\) 。
因为报纸版面太大会降低读者的兴趣，于是选定两张照片 \(i,k\) 后，规定必须选择最小的 \(B_j\)。
形式化地说，规定 \(\psi(i,k) = A_i + A_k - \min(B_j)\)，其中需要满足 \(i < j < k\)。
摸清了照片价值的计算，文文会告诉你共 \(m\) 个操作，可以分为以下三种：
-
\(\colorbox{f0f0f0}{\verb!1 x y!}\) ：照片的吸引度发生变化。文文要将 \(A_x\) 修改为 \(y\) 。
-
\(\colorbox{f0f0f0}{\verb!2 x y!}\) ：照片的大小发生变化。文文要将 \(B_x\) 修改为 \(y\) 。
-
\(\colorbox{f0f0f0}{\verb!3 l r!}\) ：文文打算利用素材库的第 \(l\) 到第 \(r\) 张中的图片，你要告诉她 \(\psi(x,y)\) 的最大值（ \(l\le x\le x+1<y \le r\) ）。
输入格式
第一行两个整数 \(n,m\)，分别表示照片数量和操作次数。
第二行 \(n\) 个整数，表示序列 \(A\)，描述每张照片的吸引度。
第三行 \(n\) 个整数，表示序列 \(B\)，描述每张照片的大小。
接下来 \(m\) 行，每行描述一个操作，格式如上所述。
输出格式
对于每个操作三，输出一行一个整数，表示答案。
输入输出样例 #1
输入 #1
6 6
1 4 2 3 5 6
5 3 4 1 6 7
3 2 5
3 1 6
1 2 3
3 1 6
2 6 1
3 1 6
输出 #1
8
9
8
8
说明/提示
数据范围及约定
-
对于 \(100\%\) 的数据：
\(1 \le n,m \le 5 \times 10^5\)。
\(1 \leq A_i,B_i,y \leq 10^8\)，\(1 \le x \le n\)，\(1 \le l \le r \le n\)。
保证 \(r-l+1 \geq 3\)，即询问的区间长度大于等于 \(3\)
#include<bits/stdc++.h>
#define wk(x) write(x),putchar(' ')
#define wh(x) write(x),putchar('\n')
#define int long long
#define mod 998244353
#define L (p<<1)
#define R (L|1)
#define MID ((l+r)>>1)
#define N 500005using namespace std;
int n,m,k,jk,ans,sum,num,cnt,tot;
int head[N],dis[N],vis[N],wis[N],f[N];void read(int &x)
{x=0;int ff=1;char ty;ty=getchar();while(!(ty>='0'&&ty<='9')){if(ty=='-') ff=-1;ty=getchar();}while(ty>='0'&&ty<='9')x=(x<<3)+(x<<1)+ty-'0',ty=getchar();x*=ff;return;
}void write(int x)
{if(x==0){putchar('0');return;}if(x<0){x=-x;putchar('-');}char asd[201];int ip=0;while(x) asd[++ip]=x%10+'0',x/=10;for(int i=ip;i>=1;i--) putchar(asd[i]);return;
}struct TT{int sum,maxl,maxr,MAXA,MINB;TT(){sum=maxl=maxr=MAXA=MINB=-1e18;}void F(){sum=maxl=maxr=MAXA=MINB=-1e18;}
}T[N<<2],Y[N][3];struct P{ void push(int p){T[p].MINB=min(T[L].MINB,T[R].MINB);T[p].MAXA=max(T[L].MAXA,T[R].MAXA);T[p].maxl=max(T[L].maxl,T[R].maxl);T[p].maxl=max(T[p].maxl,T[L].MAXA-T[R].MINB);T[p].maxr=max(T[L].maxr,T[R].maxr);T[p].maxr=max(T[p].maxr,T[R].MAXA-T[L].MINB);T[p].sum=max(max(T[L].sum,T[R].sum),max(T[L].MAXA+T[R].maxr,T[R].MAXA+T[L].maxl));return;}void build(int p,int l,int r){if(l==r){T[p].MAXA=dis[l];T[p].MINB=vis[l];T[p].sum=T[p].maxl=T[p].maxr=-1e18;return;}build(L,l,MID);build(R,MID+1,r);push(p);}void Get(int p,int l,int r,int x){if(l==r){T[p].MAXA=dis[l];T[p].MINB=vis[l];T[p].sum=T[p].maxl=T[p].maxr=-1e18;return;}if(MID>=x) Get(L,l,MID,x);else Get(R,MID+1,r,x);push(p);}TT qry(int p,int l,int r,int x,int y){if(x<=l&&r<=y) return T[p];int X=++cnt;Y[X][1].F();Y[X][2].F();Y[X][3].F(); if(MID>=x) Y[X][1]=qry(L,l,MID,x,y);if(MID<y) Y[X][2]=qry(R,MID+1,r,x,y);if(Y[X][1].MINB==-1e18) return Y[X][2];if(Y[X][2].MINB==-1e18) return Y[X][1];Y[X][3].MINB=min(Y[X][1].MINB,Y[X][2].MINB);Y[X][3].MAXA=max(Y[X][1].MAXA,Y[X][2].MAXA);Y[X][3].maxl=max(Y[X][1].maxl,Y[X][2].maxl);Y[X][3].maxl=max(Y[X][3].maxl,Y[X][1].MAXA-Y[X][2].MINB);Y[X][3].maxr=max(Y[X][1].maxr,Y[X][2].maxr);Y[X][3].maxr=max(Y[X][3].maxr,Y[X][2].MAXA-Y[X][1].MINB);Y[X][3].sum=max(max(Y[X][1].sum,Y[X][2].sum),max(Y[X][1].MAXA+Y[X][2].maxr,Y[X][2].MAXA+Y[X][1].maxl));return Y[X][3];}
}G;signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);read(n),read(m);for(int i=1;i<=n;i++) read(dis[i]);for(int i=1;i<=n;i++) read(vis[i]);G.build(1,1,n);while(m--){int x,y,op;read(op),read(x),read(y);if(op==1) dis[x]=y,G.Get(1,1,n,x);else if(op==2) vis[x]=y,G.Get(1,1,n,x);else cnt=0,wh(G.qry(1,1,n,x,y).sum);}return 0;
}