Submission #71854688

---

Source Code Expand

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
const int maxn = 2e5 + 5;
class A
{
public:
    long long mxx=-1e18,mnx=1e18,mxy=-1e18,mny=1e18;
    A operator+(A that)
    {
        A ans;
        ans.mxx = max(mxx, that.mxx);
        ans.mxy = max(mxy, that.mxy);
        ans.mnx = min(mnx, that.mnx);
        ans.mny = min(mny, that.mny);
        return ans;
    }
};
class SegmentTree
{
public:
    long long   mxx[4 * maxn],mnx[4*maxn],mxy[4*maxn],mny[4*maxn];
    void push_up(int rt) //向上更新
    {
        mxx[rt] = max(mxx[rt * 2], mxx[rt * 2 + 1]);
        mxy[rt] = max(mxy[rt * 2], mxy[rt * 2 + 1]);
        mnx[rt] = min(mnx[rt * 2], mnx[rt * 2 + 1]);
        mny[rt] = min(mny[rt * 2], mny[rt * 2 + 1]);
    }

    void build(int l, int r, int rt) //从l到r建立线段树
    {
        if (l == r)
        {
            long long x,y;
            cin>>x>>y;
            mxx[rt]=mnx[rt]=x+y;
            mxy[rt]=mny[rt]=x-y;
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, rt * 2);
        build(mid + 1, r, rt * 2 + 1);
        push_up(rt);
    }

    void updata1(int x, pair<long long,long long> k, int l, int r, int rt) //线段树区间为从l到r，把区间x到y每个数+k
    {
        if (l==r)
        {
            mxx[rt]=mnx[rt]=k.first+k.second;
            mxy[rt]=mny[rt]=k.first-k.second;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid)
            updata1(x,  k, l, mid, rt * 2);
        else
            updata1(x,  k, mid + 1, r, rt * 2 + 1);
        push_up(rt);
    }

    A query(int x, int y, int l, int r, int rt) //线段树区间为从l到r，询问区间x到y的和
    {
        if (x <= l && y >= r)
            return {mxx[rt],mnx[rt],mxy[rt],mny[rt]};
        int mid = (l + r) >> 1;
        A ans;
        if (x <= mid)
            ans = query(x, y, l, mid, rt * 2);
        if (y > mid)
            ans=ans+ query(x, y, mid + 1, r, rt * 2 + 1);
        return ans;
    }

} st;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,q;
    cin>>n>>q;
    st.build(1,n,1);
    while (q--)
    {
        int op;
        cin>>op;
        if (op==1)
        {
            int loc;
            pair<long long,long long> k;
            cin>>loc>>k.first>>k.second;
            st.updata1(loc,k,1,n,1);
        }
        else
        {
            long long l,r,x,y;
            cin>>l>>r>>x>>y;
            auto now=st.query(l,r,1,n,1);
            long long ans=0;
            long long xx=x+y,yy=x-y;
            x=xx;
            y=yy;
            if (now.mxx>x)
                ans=max(ans,now.mxx-x);
            if (now.mnx<x)
                ans=max(ans,x-now.mnx);
            if (now.mxy>y)
                ans=max(ans,now.mxy-y);
            if (now.mny<y)
                ans=max(ans,y-now.mny);
            cout<<ans<<'\n';
        }
    }
}

Submission Info

Judge Result