Submission #71865097

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define int ll
const ll INF = 1e10;

class SegmentTreeMx{
private:
  std::vector<int> aint;
  int n;
 
  int join(int x, int y) {
    return std::max(x, y);
  }
  
  void _update(int node, int from, int to, int x, int val) {
    if(from < to) {
      int mid = (from + to) / 2;
      if(x <= mid)
        _update(node * 2, from, mid, x, val);
      else
        _update(node * 2 + 1, mid + 1, to, x, val);
      aint[node] = join(aint[node * 2], aint[node * 2 + 1]);
    } else
      aint[node] = val;
  }
 
  int _query(int node, int from, int to, int x, int y) {
    if(from == x && to == y) {
      return aint[node];
    } else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return _query(node * 2, from, mid, x, y);
      else if(mid + 1 <= x && mid + 1 <= y)
        return _query(node * 2 + 1, mid + 1, to, x, y);
      else
        return join(_query(node * 2, from, mid, x, mid),
                    _query(node * 2 + 1, mid + 1, to, mid + 1, y));
    }
  }
  
  void _print(int node, int from, int to) {
    if(from < to) {
      int mid = (from + to) / 2;
      _print(node * 2, from, mid);
      _print(node * 2 + 1, mid + 1, to);
    } else
      std::cout << aint[node] << " ";
  }
 
public:
  SegmentTreeMx(int n_) {
    n = n_;
    aint.resize(1 + 4 * n);
  }
  
  void update(int x, int val) {
    _update(1, 1, n, x, val);
  }
  
  int query(int x, int y) {
    return _query(1, 1, n, x, y);
  }
 
  void print() {
    std::cout << "Print array\n";
    _print(1, 1, n);
    std::cout << '\n';
  }
};

class SegmentTreeMn{
private:
  std::vector<int> aint;
  int n;
 
  int join(int x, int y) {
    return std::min(x, y);
  }
  
  void _update(int node, int from, int to, int x, int val) {
    if(from < to) {
      int mid = (from + to) / 2;
      if(x <= mid)
        _update(node * 2, from, mid, x, val);
      else
        _update(node * 2 + 1, mid + 1, to, x, val);
      aint[node] = join(aint[node * 2], aint[node * 2 + 1]);
    } else
      aint[node] = val;
  }
 
  int _query(int node, int from, int to, int x, int y) {
    if(from == x && to == y) {
      return aint[node];
    } else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return _query(node * 2, from, mid, x, y);
      else if(mid + 1 <= x && mid + 1 <= y)
        return _query(node * 2 + 1, mid + 1, to, x, y);
      else
        return join(_query(node * 2, from, mid, x, mid),
                    _query(node * 2 + 1, mid + 1, to, mid + 1, y));
    }
  }
  
  void _print(int node, int from, int to) {
    if(from < to) {
      int mid = (from + to) / 2;
      _print(node * 2, from, mid);
      _print(node * 2 + 1, mid + 1, to);
    } else
      std::cout << aint[node] << " ";
  }
 
public:
  SegmentTreeMn(int n_) {
    n = n_;
    aint.resize(1 + 4 * n);
  }
  
  void update(int x, int val) {
    _update(1, 1, n, x, val);
  }
  
  int query(int x, int y) {
    return _query(1, 1, n, x, y);
  }
 
  void print() {
    std::cout << "Print array\n";
    _print(1, 1, n);
    std::cout << '\n';
  }
};

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n, q;
    cin>>n>>q;

    ll x[n+5], y[n+5];
    SegmentTreeMx mxDif(n+5), mxAdd(n+5);
    SegmentTreeMn mnDif(n+5), mnAdd(n+5);
    for(int i=1; i<=n; i++){
        cin>>x[i]>>y[i];
        mxDif.update(i, x[i]-y[i]);
        mnDif.update(i, x[i]-y[i]);

        mxAdd.update(i, x[i]+y[i]);
        mnAdd.update(i, x[i]+y[i]);
    }

    while(q--){
        int type;
        cin>>type;

        if(type == 1){
            int idx;
            cin>>idx;

            cin>>x[idx]>>y[idx];
            mxDif.update(idx, x[idx]-y[idx]);
            mnDif.update(idx, x[idx]-y[idx]);

            mxAdd.update(idx, x[idx]+y[idx]);
            mnAdd.update(idx, x[idx]+y[idx]);
        }
        else{
            ll l, r, x, y;
            cin>>l>>r>>x>>y;

            ll dif = x-y;
            ll add = x+y;

            ll ans = -INF;
            // cout<<mxDif.query(l, r)<<' '<<mnDif.query(l, r)<<endl;
            // cout<<mxAdd.query(l, r)<<' '<<mnAdd.query(l, r)<<endl;
            ans = max(ans, abs(mxDif.query(l, r) - dif));
            ans = max(ans, abs(mnDif.query(l, r) - dif));
            ans = max(ans, abs(mxAdd.query(l, r) - add));
            ans = max(ans, abs(mnAdd.query(l, r) - add));
            cout<<ans<<endl;
        }
    }
	return 0;
}

Submission Info

Judge Result