文文的摄影布置

文文的摄影布置

题目链接：文文的摄影布置

维护左边的最大 A[i] - B[j] ，后右边最大的 A[k] - B[j] ，然后线段树区间合并的时候利用这个和某个区间的max更新答案即可。

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e5+10,inf=5e8;
int n,m,A[N],B[N];
struct node{int res,mi,mx,ls,rs;}t[N<<2];
#define mid (l+r>>1)
inline node merge(node a,node b){return node{max({a.ls&#,a.mx+b.s}),min(a.mi,b.mi),,b.mx),max({a.ls,b.-b.mi}),max({a.rs,b.-a.mi})};
}
void change(int p,int l,int r,int x){if(l==r){t[p]={-inf,B[l],A[l],-inf,-inf}; return ;}if(x<=mid) change(p<<1,l,mid,x);else change(p<<1|1,mid+1,r,x);t[p]=merge(t[p<<1],t[p<<1|1]);
}
node ask(int p,int l,int r,int ql,int qr){if(l==ql&&r==qr) return t[p];if(qr<=mid) return ask(p<<1,l,mid,ql,qr);else if(ql>mid) return ask(p<<1|1,mid+1,r,ql,qr);else return merge(ask(p<<1,l,mid,ql,mid),ask(p<<1|1,mid+1,r,mid+1,qr));
}
signed main(){cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d",&A[i]);for(int i=1;i<=n;i++) scanf("%d",&B[i]);for(int i=1;i<=n;i++) change(1,1,n,i);for(int i=1,op,x,y;i<=m;i++){scanf("%d %d %d",&op,&x,&y);if(op==1) A[x]=y,change(1,1,n,x);else if(op==2) B[x]=y,change(1,1,n,x);else printf("%dn",ask(1,1,n,x,y).res);}return 0;
}