#1190707 (PyPy3) No.3464 Max and Sum on Grid

• 問題: No.3464 Max and Sum on Grid
• ユーザー: tyawanmusi
• 提出日時: 2026-09-28 21:20:43
• 言語: PyPy3 (7.3.23 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 3,910 bytes
• コンパイル時間: 62 ms
• コンパイル使用メモリ: 83,312 KB
• 実行使用メモリ: 168,344 KB
• 最終ジャッジ日時: 2026-09-28 21:20:55
• 合計ジャッジ時間: 11,283 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	TLE * 1 -- * 9

ソースコード

class BinaryIndexedTree:
    def __init__(self, n):
        if isinstance(n, int):
            self.bit = [0] * n
        else:
            self.bit = n.copy()
            n = len(self.bit)
            for i in range(1, n + 1):
                j = i + (i & -i)
                if j <= n:
                    self.bit[j-1] += self.bit[i-1]

    def add(self, i, x):
        i += 1
        while i <= len(self.bit):
            self.bit[i-1] += x
            i += i & -i

    def sum_sub(self, r):
        total = 0
        while r:
            total += self.bit[r-1]
            r -= r & -r
        return total

    def sum(self, l, r):
        return self.sum_sub(r) - self.sum_sub(l)


class Mo_Base:
    def __init__(self, n):
        assert n >= 0
        self.n = n
        self.queries = []
        self._u = self._v = 0
        # 空区間 [0, 0) の状態を初期化する
        self.ans = 0

    def u_plus(self, u, v): raise NotImplementedError
    def u_minus(self, u, v): raise NotImplementedError
    def v_plus(self, u, v): raise NotImplementedError
    def v_minus(self, u, v): raise NotImplementedError

    def get_ans(self):
        return self.ans

    def add_query(self, u, v):
        self.queries.append((u, v, len(self.queries)))

    def solve(self, block_size=None):
        q = len(self.queries)
        if q == 0:
            return []
        bsize = max(1, int(self.n / q**0.5)) if block_size is None else block_size
        assert isinstance(bsize, int) and bsize > 0
        self.queries.sort(key=lambda x: (
            x[0] // bsize,
            x[1] if (x[0] // bsize) % 2 == 0 else -x[1]
        ))
        ans = [0] * q
        u, v = self._u, self._v
        u_plus, u_minus = self.u_plus, self.u_minus
        v_plus, v_minus = self.v_plus, self.v_minus
        get_ans = self.get_ans
        for target_u, target_v, q_i in self.queries:
            while v < target_v:
                v_plus(u, v)
                v += 1
            while u > target_u:
                u_minus(u, v)
                u -= 1
            while v > target_v:
                v_minus(u, v)
                v -= 1
            while u < target_u:
                u_plus(u, v)
                u += 1
            ans[q_i] = get_ans()
        self._u, self._v = u, v
        return ans

class Mo(Mo_Base):
    def __init__(self, n):
        if isinstance(n, int):
            super().__init__(n)
            self.a = [0] * n
        else:
            super().__init__(len(n))
            self.a = n

    def u_plus(self, u, v):
        self.ans += a[u] * cntb.sum(0, a[u] + 1) + sumb.sum(a[u] + 1, maxe)
        cnta.add(a[u], 1)
        suma.add(a[u], a[u])
        return

    def u_minus(self, u, v):
        # f(u, v) -> f(u-1, v)
        self.ans -= a[u-1] * cntb.sum(0, a[u-1] + 1) + sumb.sum(a[u-1] + 1, maxe)
        cnta.add(a[u-1], -1)
        suma.add(a[u-1], -a[u-1])
        return

    def v_plus(self, u, v):
        # f(u, v) -> f(u, v+1)
        self.ans += b[v] * cnta.sum(0, b[v] + 1) + suma.sum(b[v] + 1, maxe)
        cntb.add(b[v], 1)
        sumb.add(b[v], b[v])
        return

    def v_minus(self, u, v):
        # f(u, v) -> f(u, v-1)
        self.ans -= b[v-1] * cnta.sum(0, b[v-1] + 1) + suma.sum(b[v-1] + 1, maxe)
        cntb.add(b[v-1], -1)
        sumb.add(b[v-1], -b[v-1])
        return

import sys
input = sys.stdin.readline
maxe = 10**5 + 1
n, q = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
cnta = BinaryIndexedTree(maxe)
suma = BinaryIndexedTree(maxe)
cntb = BinaryIndexedTree(maxe)
sumb = BinaryIndexedTree(maxe)
mo = Mo(n)
for _ in range(q):
    l, d, r, u = map(int, input().split())
    mo.add_query(l-1, d-1)
    mo.add_query(l-1, u)
    mo.add_query(r, d-1)
    mo.add_query(r, u)
res = mo.solve()
for i in range(0, len(res), 4):
    ans = res[i+3] - res[i+2] - res[i+1] + res[i]
    print(ans)