提出 #71860102

---

ソースコード 拡げる

import sys

input = sys.stdin.readline
INF = 10**18

class SegTree:
    def __init__(self, size_exp:int, op, ele):
        self.size = 1 << size_exp  
        self.op = op
        self.ele = ele
        self.tree = [self.ele] * (2 * self.size)

    def update(self, p: int, x: int):
        p += self.size
        self.tree[p] = x
        
        # 親に向かって更新
        while p > 1:
            p //= 2
            self.tree[p] = self.op(self.tree[2*p], self.tree[2*p+1])

    def get(self, l: int, r: int):
        l += self.size
        r += self.size
        
        # 左右から結果を集めるリストではなく、直接演算していく
        res_l = self.ele
        res_r = self.ele
        
        while l < r:
            if l % 2 == 1:
                res_l = self.op(res_l, self.tree[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res_r = self.op(self.tree[r], res_r)
            l //= 2
            r //= 2
            
        return self.op(res_l, res_r)


N,Q = map(int,input().split())
XY = [list(map(int, input().split())) for _ in range(N)]


size_exp = (N-1).bit_length()
#T1: x + y, T2: x - y, T3: -x + y, T4: -x - y
T1 = SegTree(size_exp, max, -INF)
T2 = SegTree(size_exp, max, -INF)
T3 = SegTree(size_exp, max, -INF)
T4 = SegTree(size_exp, max, -INF)


for i in range(N):
    x, y = XY[i]
    T1.update(i, x + y)
    T2.update(i, x - y)
    T3.update(i, -x + y)
    T4.update(i, -x - y)



for _ in range(Q):
    query = list(map(str, input().split()))
    
    if query[0] == '1':
        # 1 i x y : 更新
        i = int(query[1]) - 1 # 0-indexed
        x = int(query[2])
        y = int(query[3])
        
        T1.update(i, x + y)
        T2.update(i, x - y)
        T3.update(i, -x + y)
        T4.update(i, -x - y)
        
    else:
        # 2 L R x y : クエリ
        L = int(query[1]) - 1 # 0-indexed
        R = int(query[2])     
        x = int(query[3])
        y = int(query[4])
        
        #最大値を取得
        v1 = T1.get(L, R)
        v2 = T2.get(L, R)
        v3 = T3.get(L, R)
        v4 = T4.get(L, R)
        
        # 式に合わせて計算し、最大を取る
        # max( (Xi+Yi)-(x+y), (Xi-Yi)-(x-y), (-Xi+Yi)-(-x+y), (-Xi-Yi)-(-x-y) )
        ans = -INF
        ans = max(ans, v1 - (x + y))
        ans = max(ans, v2 - (x - y))
        ans = max(ans, v3 - (-x + y))
        ans = max(ans, v4 - (-x - y))
        
        print(ans)

提出情報

ジャッジ結果