2020ICPC·小米 网络选拔赛第二场 C-Data Structure Problem

Data Structure Problem

题意

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;
}