题意
bobo有两个数组,现在他想要给他们执行下面的不同操作
1.+ x y 把的值改为
2.+ x y 把的值改为
3.+ x 求出,其中c[i]满足
分析
发现比较棘手的是操作三。仔细分析一下,虽然要取一个最大值,但是得到的无外乎都是这种形式。再化简一下,设 ,那么都是的形式,会发现,这个式子取最大值时,只与有关,也就是说,我们只需要维护的a数组与b数组前缀和的差的最大值
代码
#include<bits/stdc++.h> #define inf 1e15 #define ll long long #define ls now<<1 #define rs now<<1|1 using namespace std; const int N=4e5+10; int n,m; ll a[N],b[N],sum[N]; struct ci { int l,r; ll ma,tag; }t[N<<2]; inline void pd(int now) { if(!t[now].tag) return; t[ls].ma+=t[now].tag; t[rs].ma+=t[now].tag; t[ls].tag+=t[now].tag; t[rs].tag+=t[now].tag; t[now].tag=0; } inline void build(int now,int l,int r) { t[now].tag=0; t[now].l=l;t[now].r=r; if(l==r) { t[now].ma=a[l]-sum[l]; return; } int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); t[now].ma=max(t[ls].ma,t[rs].ma); } inline void upd(int now,int x,int y,ll d) { int l=t[now].l,r=t[now].r; if(l>=x&&r<=y) { t[now].ma+=d;t[now].tag+=d; return; }pd(now); int mid=(l+r)>>1; if(x<=mid) upd(ls,x,y,d); if(y>mid) upd(rs,x,y,d); t[now].ma=max(t[ls].ma,t[rs].ma); } inline ll ask(int now,int x,int y) { int l=t[now].l,r=t[now].r; if(l>=x&&r<=y) return t[now].ma; pd(now); int mid=(l+r)>>1;ll val=-inf; if(x<=mid) val=ask(ls,x,y); if(y>mid) val=max(val,ask(rs,x,y)); return val; } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++) { scanf("%lld",&b[i]); sum[i]=sum[i-1]+b[i]; } build(1,0,n); for(int i=1;i<=m;i++) { int e;scanf("%d",&e); if(e==1) { ll x,y;scanf("%lld%lld",&x,&y); upd(1,x,x,-a[x]+y);a[x]=y; } if(e==2) { ll x,y;scanf("%lld%lld",&x,&y); upd(1,x,n,b[x]-y);b[x]=y; } if(e==3) { ll x;scanf("%lld",&x); printf("%lld\n",ask(1,0,x)+a[x]-ask(1,x,x)); } } } return 0; }