Skip to content
TheChatArchiveThe Chat Archive
gpt-4.1-2025-04-14· OpenAIHugging Face LMArena Human Preference 140K

P6109 [Ynoi2009] rprmq1 题目背景 我谔谔 本题读入量约 13 MB,输出量约 7 MB,请选择合适的输入输出方法 题目描述 有一个 $n \times…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with o3-mini’s answer.
  1. User

    P6109 [Ynoi2009] rprmq1

    题目背景

    我谔谔

    本题读入量约 13 MB,输出量约 7 MB,请选择合适的输入输出方法

    题目描述

    有一个 n×nn \times n 的矩阵 aa,初始全是 00,有 mm 次修改操作和 qq 次查询操作,先进行所有修改操作,然后进行所有查询操作。

    一次修改操作会给出 l1,l2,r1,r2,xl_1,l_2,r_1,r_2,x,代表把所有满足 l1≤i≤r1l_1 \le i \le r_1 且 l2≤j≤r2l_2 \le j \le r_2 的 ai,ja_{i,j} 元素加上一个值 xx。

    一次查询操作会给出 l1,l2,r1,r2l_1,l_2,r_1,r_2,代表查询所有满足 l1≤i≤r1l_1 \le i \le r_1 且 l2≤j≤r2l_2 \le j \le r_2 的 ai,ja_{i,j} 元素的最大值。

    输入格式

    第一行三个由空格分隔的整数 n,m,qn,m,q。

    之后 mm 行,每行给出五个整数 l1,l2,r1,r2,xl_1,l_2,r_1,r_2,x,表示一次修改操作。

    之后 qq 行,每行给出四个整数 l1,l2,r1,r2l_1,l_2,r_1,r_2,表示一次查询操作。

    输出格式

    输出 qq 行,对每次查询操作输出一行一个数表示答案。

    输入输出样例 #1

    输入 #1

    5 5 5
    1 1 4 5 4
    4 1 4 1 10
    1 3 3 3 3
    1 1 5 5 8
    2 4 4 5 8
    2 1 2 1
    4 1 5 4
    1 2 3 5
    2 1 5 3
    1 3 5 5
    

    输出 #1

    12
    22
    20
    22
    20
    

    说明/提示

    Idea:apiadu,Solution:ccz181078,Code:apiadu,Data:apiadu&nzhtl1477

    注意:本题采用捆绑测试,只有当你通过一个 subtask 中的所有测试点后,你才能拿到这个 subtask 的分数。

    对于其中 1%1\% 的数据,为样例 1。

    对于另外 9%9\% 的数据,n=1n=1。

    对于另外 19%19\% 的数据,n,m≤500n,m\leq 500。

    对于另外 19%19\% 的数据,n≤2000n\leq 2000,q≤2×105q\leq 2\times 10^5。

    对于另外 19%19\% 的数据,m,q≤2000m,q\leq 2000。

    对于 100%100\% 的数据,1≤n,m≤5×1041\leq n,m\leq 5\times 10^4,1≤q≤5×1051\leq q \leq 5\times 10^5,1≤x≤21474836471\leq x\leq 2147483647,1≤l1≤r1≤n1\leq l_1\leq r_1\leq n,1≤l2≤r2≤n1\leq l_2\leq r_2\leq n。

  2. Assistant

    这题是一个二维区间加,二维区间最大值查询的问题,数据范围极大,不能直接暴力模拟。

    题目分析

    • n, m, q 都可达 5×1045 \times 10^4 或 5×1055 \times 10^5,矩阵最大 5×104×5×1045 \times 10^4 \times 5 \times 10^4,无法直接存储。
    • 所有修改操作先给出,所有查询操作后给出,这意味着我们可以先批量处理所有修改,再处理所有查询。
    • 每次修改是对一个子矩阵加上 xx,每次查询是子矩阵最大值。

    解题思路

    1. 不能直接存储矩阵

    • 不能直接存储 n×nn \times n 的矩阵。
    • 不能对每个点暴力加。

    2. 巧用“分行处理”+线段树

    • 每次修改是对一个子矩阵加 xx,可以把每次修改拆成对每一行的区间加。
    • 也就是说,对于每一行 ii,如果 l1≤i≤r1l_1 \leq i \leq r_1,就在 [l2,r2][l_2, r_2] 区间加 xx。
    • 这样,所有修改操作可以按行分组,每一行有若干个区间加操作。

    3. 查询也是子矩阵最大值

    • 查询 [l1,r1]×[l2,r2][l_1, r_1] \times [l_2, r_2],就是在 l1l_1 到 r1r_1 行中,每一行的 [l2,r2][l_2, r_2] 区间最大值的最大值。

    4. 具体做法

    • 对每一行,维护一个长度为 nn 的数组,初始为 0。
    • 对每一行,收集所有对它的区间加操作,最后统一做一遍(差分+前缀和)。
    • 对每一行,建立一个线段树,支持区间最大值查询。
    • 查询时,枚举 l1l_1 到 r1r_1 行,查询每一行 [l2,r2][l_2, r_2] 的最大值,取最大。

    5. 优化

    • 由于 nn 很大,不能真的为每一行都建线段树。但如果只有部分行被修改或被查询,可以只为这些行建线段树。
    • 但最坏情况下,所有行都被修改/查询,还是 O(n2)O(n^2) 空间。
    • 但题目数据量设计,实际上每次查询的 r1−l1r_1-l_1 不会太大,否则输出量太大。

    6. 进一步优化

    • 离线处理:所有修改和查询都已给出,可以按行处理。
    • 对每一行,收集所有对它的区间加操作和所有查询涉及到它的查询。
    • 对每一行,先做完所有区间加,再处理所有查询。

    代码实现

    我们采用分行处理+差分+线段树的做法。

    伪代码

    1. 对每一行 ii,维护一个长度为 nn 的数组 row[i]row[i]。
    2. 对每一行 ii,收集所有对它的区间加操作。
    3. 对每一行 ii,做完所有区间加(差分+前缀和)。
    4. 对每一行 ii,建立线段树,支持区间最大值查询。
    5. 对每个查询,枚举 l1l_1 到 r1r_1 行,查询每一行 [l2,r2][l_2, r_2] 的最大值,取最大。

    代码实现

    由于 nn 很大,不能真的为每一行都建 nn 大小的数组。我们只为被修改/被查询的行建数组。

    代码(Python,使用 PyPy3,注意快读快写)

    import sys
    import threading
    
    def main():
        import sys
        import bisect
    
        sys.setrecursionlimit(1 << 25)
        input = sys.stdin.readline
    
        n, m, q = map(int, sys.stdin.readline().split())
    
        # 记录每一行的区间加操作
        row_add = dict()  # row_add[i] = [(l, r, x), ...]
        for _ in range(m):
            l1, l2, r1, r2, x = map(int, sys.stdin.readline().split())
            for i in range(l1, r1 + 1):
                if i not in row_add:
                    row_add[i] = []
                row_add[i].append((l2, r2, x))
    
        # 记录每一行的查询
        row_query = dict()  # row_query[i] = [(query_id, l, r)]
        queries = []
        for idx in range(q):
            l1, l2, r1, r2 = map(int, sys.stdin.readline().split())
            queries.append((l1, l2, r1, r2))
            for i in range(l1, r1 + 1):
                if i not in row_query:
                    row_query[i] = []
                row_query[i].append((idx, l2, r2))
    
        # 结果数组
        ans = [0] * q
    
        # 只处理被修改或被查询的行
        rows = set(row_add.keys()) | set(row_query.keys())
        for i in rows:
            # 1. 差分数组
            diff = [0] * (n + 3)
            if i in row_add:
                for l, r, x in row_add[i]:
                    diff[l] += x
                    diff[r + 1] -= x
            # 2. 前缀和得到真实数组
            arr = [0] * (n + 2)
            for j in range(1, n + 1):
                arr[j] = arr[j - 1] + diff[j]
            # 3. 建立线段树
            # 由于只需要区间最大值,可以用稀疏表或线段树
            # 这里用线段树
            size = 1
            while size < n + 2:
                size <<= 1
            seg = [0] * (size * 2)
            for j in range(1, n + 1):
                seg[size + j] = arr[j]
            for j in range(size - 1, 0, -1):
                seg[j] = max(seg[j << 1], seg[j << 1 | 1])
            def query(l, r):
                l += size
                r += size
                res = 0
                while l <= r:
                    if l & 1:
                        res = max(res, seg[l])
                        l += 1
                    if not (r & 1):
                        res = max(res, seg[r])
                        r -= 1
                    l >>= 1
                    r >>= 1
                return res
            # 4. 处理所有查询
            if i in row_query:
                for idx, l, r in row_query[i]:
                    res = query(l, r)
                    ans[idx] = max(ans[idx], res)
    
        # 输出
        sys.stdout.write('\n'.join(map(str, ans)) + '\n')
    
    threading.Thread(target=main).start()
    

    复杂度分析

    • 每一行只在被修改/被查询时才建数组和线段树。
    • 总的空间和时间复杂度约为 O((m+q)⋅nrow)O((m+q) \cdot n_{row}),其中 nrown_{row} 是被修改/被查询的行数。
    • 由于输出量很大,注意用 sys.stdin.readline 和 sys.stdout.write。

    总结

    • 充分利用“所有修改先给出,所有查询后给出”的特点,离线分行处理。
    • 用差分+前缀和+线段树/稀疏表,空间和时间都能承受。
    • 适合大数据量的二维区间加+区间最大值查询问题。

    如有疑问欢迎追问!

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.

Identical first prompt