一道很有意思的线段树题。
第一步分析,我们要求最大的 \(a_i+a_k-\min{(b_j)}\),事实上我们可以直接省去这个 \(\min\) 因为要最大化这个东西,选出来的 \(b_j\) 必然是最小的,所以原题转化为给定 \(l,r\) 求 \(\max{(a_i-b_j+a_k)}\) 其中 \(i<j<k\)。
第二步分析,我们发现这是一个单点修改、区间查询的问题,遇到这种问题一般都从区间合并入手,我们考虑怎么合并两个区间。
将左右两个区间合并成上面一个大区间,我们有四种情况:
- \(i,j,k\) 均在左区间,那么答案即为左区间答案。
- \(i,j,k\) 均在右区间,那么答案即为右区间答案。
- \(i,j\) 在左区间,\(k\) 在右区间,那么答案即为左区间中最大的 \(a_i-b_j\ (i<j)\) 加上右区间中最大的 \(a_k\)。
- \(i\) 在左区间,\(j,k\) 在右区间,那么答案即为左区间中最大的 \(a_i\) 加上右区间中最大的 \(-b_j+a_k\ (j<k)\)。
发现我们很好用线段树维护 1、2 种情况和 3 的右区间和 4 的左区间。
第三步分析,我们需要维护 3 情况的左区间和 4 情况的右区间。
以 3 情况左区间为例,我们同样分成两个小区间,看如何合并:
- \(i,j\) 均在左区间,那么答案即为左区间答案。
- \(i,j\) 均在右区间,那么答案即为右区间答案。
- \(i\) 在左区间 \(j\) 在右区间,那么答案即为左区间中最大的 \(a_i\) 减去右区间中最小的 \(b_j\)。
4 情况的右区间同理。
于是我们发现,我们很容易就能用线段树维护区间中的最大 \(a_i\) 与区间中最小的 \(b_j\) 了。
于是这道题的各种信息就很好的用线段树维护了。
code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls(P) (P<<1)
#define rs(P) (P<<1|1)
const int inf=1e9,NR=5e5+5,SZ=4*NR;
int n,m;
int a[NR],b[NR];
struct node{
int mxa,mnb,ij,jk,w;
node():mxa(-inf),mnb(inf),ij(-inf),jk(-inf),w(-inf){}
}tree[SZ];
node operator +(node l,node r){
node res;
res.mxa=max(l.mxa,r.mxa),res.mnb=min(l.mnb,r.mnb);
res.ij=max(max(l.ij,r.ij),l.mxa-r.mnb),res.jk=max(max(l.jk,r.jk),r.mxa-l.mnb);
res.w=max(max(l.w,r.w),max(l.ij+r.mxa,l.mxa+r.jk));
return res;
}
void bld(int l,int r,int p){
if(l==r){tree[p].mxa=a[l],tree[p].mnb=b[l];return;}
int mid=l+r>>1;
bld(l,mid,ls(p)),bld(mid+1,r,rs(p));
tree[p]=tree[ls(p)]+tree[rs(p)];
}
void mfy(int l,int r,int x,int p){
if(l==r){tree[p].mxa=a[l],tree[p].mnb=b[l];return;}
int mid=l+r>>1;
if(x<=mid)mfy(l,mid,x,ls(p));
else mfy(mid+1,r,x,rs(p));
tree[p]=tree[ls(p)]+tree[rs(p)];
}
void qry(int l,int r,int s,int t,int p,node &num){
if(s<=l&&r<=t){num=num+tree[p];return;}
int mid=l+r>>1;
if(s<=mid)qry(l,mid,s,t,ls(p),num);
if(t>mid)qry(mid+1,r,s,t,rs(p),num);
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=n;++i)cin>>b[i];
bld(1,n,1);
for(int i=1;i<=m;++i){
int op,x,y;cin>>op>>x>>y;
node res;
if(op==1)a[x]=y,mfy(1,n,x,1);
if(op==2)b[x]=y,mfy(1,n,x,1);
if(op==3)qry(1,n,x,y,1,res),cout<<res.w<<endl;
}
return 0;
}
标签:Wdsr,int,题解,tree,mid,文文,答案,区间,op
From: https://www.cnblogs.com/agrumestly/p/17673944.html