Submission #71865825

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
using namespace std;
using ll = long long;
const ll INF = 1e18;

struct Node {
    ll U_max, U_min;
    ll V_max, V_min;
    Node() : U_max(-INF), U_min(INF), V_max(-INF), V_min(INF) {}
    Node(ll u, ll v) : U_max(u), U_min(u), V_max(v), V_min(v) {}
};

Node merge(const Node& l, const Node& r) {
    Node res;
    res.U_max = max(l.U_max, r.U_max);
    res.U_min = min(l.U_min, r.U_min);
    res.V_max = max(l.V_max, r.V_max);
    res.V_min = min(l.V_min, r.V_min);
    return res;
}

vector<Node> tree;
vector<ll> U, V;
int n;

void build(int p, int l, int r) {
    if (l == r) {
        tree[p] = Node(U[l], V[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    tree[p] = merge(tree[p * 2], tree[p * 2 + 1]);
}

void update(int p, int l, int r, int idx, ll u, ll v) {
    if (l == r) {
        tree[p] = Node(u, v);
        return;
    }
    int mid = (l + r) / 2;
    if (idx <= mid) update(p * 2, l, mid, idx, u, v);
    else update(p * 2 + 1, mid + 1, r, idx, u, v);
    tree[p] = merge(tree[p * 2], tree[p * 2 + 1]);
}

Node query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[p];
    int mid = (l + r) / 2;
    Node res;
    if (ql <= mid) res = merge(res, query(p * 2, l, mid, ql, qr));
    if (qr > mid) res = merge(res, query(p * 2 + 1, mid + 1, r, ql, qr));
    return res;
}

int main() {
    scanf("%d", &n);
    int q;
    scanf("%d", &q);
    U.resize(n + 1);
    V.resize(n + 1);

    for (int i = 1; i <= n; i++) {
        ll x, y;
        scanf("%lld%lld", &x, &y);
        U[i] = x + y;
        V[i] = x - y;
    }

    tree.resize(4 * n);
    build(1, 1, n);

    while (q--) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int i; ll x, y;
            scanf("%d%lld%lld", &i, &x, &y);
            update(1, 1, n, i, x + y, x - y);
        }
        else {
            int l, r; ll x, y;
            scanf("%d%d%lld%lld", &l, &r, &x, &y);
            Node nd = query(1, 1, n, l, r);
            ll u = x + y, v = x - y;
            ll d1 = max(u - nd.U_min, nd.U_max - u);
            ll d2 = max(v - nd.V_min, nd.V_max - v);
            printf("%lld\n", max(d1, d2));
        }
    }
    return 0;
}

Submission Info

Judge Result