Skip to content
TheChatArchiveThe Chat Archive
o3-mini· 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 gpt-4.1-2025-04-14’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

    我们可以证明,题目中每个修改操作都是对一个矩形区域整体加上一个正整数,由于所有加法均为正数,所以每个单元格的最终值就是若干个“矩形‐指示函数”叠加起来的结果,即

    [ A[i,j] = \sum_{k=1}^{m} x_k\cdot 1_{,l_{1,k}\le i\le r_{1,k}\ \wedge\ l_{2,k}\le j\le r_{2,k]}, ]

    这其实给出了一个“区间加”的过程。注意更新和查询分别“捆绑”在一起,也即先做完所有更新后再询问区间中各个值的最大值。

    直接建立一个 (n\times n) 的矩阵显然无法接受(因为 (n) 可达 (5\times10^4),存储 2500 百万个数会超内存);但我们可以利用二维差分数组“延迟更新”(差分法)将每个更新转化为对差分数组中四个位置的修改:

    • (D[l_1,l_2] \mathrel{+}= x)
    • 如果 (r_1+1 \le n) 则 (D[r_1+1,l_2] \mathrel{-}= x)
    • 如果 (r_2+1 \le n) 则 (D[l_1,r_2+1] \mathrel{-}= x)
    • 如果 (r_1+1\le n) 且 (r_2+1\le n) 则 (D[r_1+1,r_2+1] \mathrel{+}= x).

    然后最终矩阵满足 [ A[i,j] = D[1,1] + D[1,2] +\cdots + D[1,j] + D[2,1] +\cdots + D[2,j]+\cdots + D[i,1]+\cdots+D[i,j], ] 即先对行、再对列做前缀和。

    但问题在于:如何对最终矩阵回答任意查询“子矩阵中最大值”呢?如果我们真的将 (A) “铺平”起来,再加上二维 RMQ 结构,将会需要 (O(n^2)) 的空间和建树时间,而 (n) 可达 (5\times10^4)(近 25 亿个单元格),显然不可行。

    关键观察。
    分析每一次更新,可以发现每次更新对 (A) 的贡献其实是一个“矩形‐指示函数”,而将这些矩形叠加后得到的 (A) 其实在行与列的“变化点”处发生改变。也就是说,只有当行号处于某些“断点” [ R={1}\cup{l_{1,k},r_{1,k}+1:,1\le k\le m,; r_{1,k}+1\le n} ] 以及列号处于 [ C={1}\cup{l_{2,k},r_{2,k}+1:,1\le k\le m,; r_{2,k}+1\le n} ] 时,矩阵 (A) 的值“跳变”。因此,(A) 在由 (R) 与 (C) 划分的“块”中是常数,即可以说 (A) 是分块常数的。

    设 (R) 中元素个数为 (r_{cnt})(显然 (r_{cnt}\le \min(n,2m+1)))而 (C) 中元素个数为 (c_{cnt})(同理由),那么我们只需要在这 (r_{cnt}\times c_{cnt}) 个“关键块”上保存答案,再利用二维数据结构(例如二维线段树或二维稀疏表/RMQ)回答询问即可。

    注意:查询给定一个子矩阵 ([L_1,R_1]\times[L_2,R_2]) 时,其最大值必然出现在某个与 (R) 与 (C) 中“断点”对齐的块上(即有代表性的块中取一个任意点,其值即为该整块的常数值)。因此,我们可以对纵横两个方向进行坐标压缩,对所有“断点”建立二维数组,然后利用常规二维 RMQ 结构(例如预处理二维稀疏表)回答每个查询。

    算法大体步骤
    下面给出 C++(或 C) 中较高效的做法,Python 解释性代码可能无法通过但原理完全一样:

    1. 离散化断点。
      遍历所有更新操作,收集所有行坐标(包括 1 与所有 (l_{1}, r_{1}+1))以及所有列坐标(包括 1 与所有 (l_{2}, r_{2}+1)),排序后去重。令映射函数为
      [ idx_r(i)=\text{离散后的行号},\quad idx_c(j)=\text{离散后的列号}. ]

    2. 构造二维差分数组。
      用一个二维数组 diff[0..r_{cnt}][0..c_{cnt}](通常使用 vector 或数组)初始化为 0。对于每个更新操作 ((l_1,l_2,r_1,r_2,x)):

      • diff[ idx_r(l1) ][ idx_c(l2) ] += x
      • 如果 (r_1+1 \le n) 则 diff[ idx_r(r1+1) ][ idx_c(l2) ] -= x
      • 如果 (r_2+1 \le n) 则 diff[ idx_r(l1) ][ idx_c(r2+1) ] -= x
      • 如果 (r_1+1\le n) 且 (r_2+1\le n) 则 diff[ idx_r(r1+1) ][ idx_c(r2+1) ] += x
    3. 二维前缀和。
      对离散化后的二维数组做行前缀和再列前缀和,即得到每个块的“值”。注意:由于原来每个块对应原区间长度不一(例如行区间长度为 (R[i+1]-R[i])),但是由于所有更新都是整体加值,“块内所有值均相同”。

    4. 构造二维 RMQ 结构。
      设离散后得到的新矩阵为 B[r_cnt][c_cnt],其大小不会太大(最坏情况 (r_{cnt}\le n,, c_{cnt}\le n),题目数据保证 (n\le 5\times10^4) 但 m 的数据较多时“断点”数通常远小于 n)。然后建立二维 RMQ 数据结构(例如二维稀疏表)以便日后回答任意一个“块内最大值”的查询。
      这里注意查询时:给定原问题中的查询 ([L_1,L_2,R_1,R_2]),我们需要找到离散化后所有块,其对应的原坐标区间与查询区间有交。由于 (A) 在块上是常数,查询答案就是这些块中“块值”的最大值。
      为此,我们需要用二分在离散化的行数组中找到第一个断点不小于 (L_1) 的位置,和最后一个断点不大于 (R_1) 的位置;对列同理。 再利用 RMQ 询问这一区间即可。(注意查询时有可能不“完全匹配”,这时还要枚举几个边界部分的块,但整体思路类似,与典型二维离散化查询类似。)

    5. 输出答案。

    下面给出一个 C++ 样例代码(【注意】下面代码仅给出思路,真正通过本题需要非常仔细的优化【快速 IO、内存池】等等细节):


    #include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
     
    // 快速IO略……
     
    int main(){
        int n, m, q;
        scanf("%d%d%d", &n, &m, &q);
        vector<int> rs, cs;
        // 一定要加上边界1和n+1(方便后续构造区间)
        rs.push_back(1); cs.push_back(1);
        // 存储所有更新
        struct Update { int l1, l2, r1, r2; int x; };
        vector<Update> ups(m);
        for (int i=0; i<m; i++){
            int l1,l2,r1,r2,x;
            scanf("%d%d%d%d%d",&l1,&l2,&r1,&r2,&x);
            ups[i] = {l1, l2, r1, r2, x};
            rs.push_back(l1); 
            if(r1+1 <= n) rs.push_back(r1+1);
            cs.push_back(l2);
            if(r2+1 <= n) cs.push_back(r2+1);
        }
        // 离散化
        sort(rs.begin(), rs.end());
        rs.erase(unique(rs.begin(), rs.end()), rs.end());
        sort(cs.begin(), cs.end());
        cs.erase(unique(cs.begin(), cs.end()), cs.end());
        int R = rs.size(), C = cs.size();
     
        // 建立二维差分数组B,大小为 R x C
        vector<vector<ll>> diff(R, vector<ll>(C, 0));
        auto getRow = [&](int x) -> int {
            return int(lower_bound(rs.begin(), rs.end(), x) - rs.begin());
        };
        auto getCol = [&](int x) -> int {
            return int(lower_bound(cs.begin(), cs.end(), x) - cs.begin());
        };
     
        for(auto &up : ups){
            int r1 = getRow(up.l1);
            int c1 = getCol(up.l2);
            diff[r1][c1] += up.x;
            if(up.r1+1 <= n){
                int r2 = getRow(up.r1+1);
                diff[r2][c1] -= up.x;
            }
            if(up.r2+1 <= n){
                int c2 = getCol(up.r2+1);
                diff[r1][c2] -= up.x;
            }
            if(up.r1+1 <= n && up.r2+1 <= n){
                int r2 = getRow(up.r1+1), c2 = getCol(up.r2+1);
                diff[r2][c2] += up.x;
            }
        }
     
        // 二维前缀和 (先行,再列)
        for (int i=0; i<R; i++){
            for (int j=1; j<C; j++){
                diff[i][j] += diff[i][j-1];
            }
        }
        for (int j=0; j<C; j++){
            for (int i=1; i<R; i++){
                diff[i][j] += diff[i-1][j];
            }
        }
        // 此时 diff[i][j] 表示离散化后第 i 行、第 j 列块内的加值
        // 注意:原矩阵 A 在坐标区间 [rs[i], rs[i+1]-1] x [cs[j], cs[j+1]-1] 内均等于 diff[i][j]
     
        // 构造二维RMQ:这里我们给出一个简单的二维稀疏表构造
        // 稀疏表大小为 sp[k1][k2][i][j] , k1,k2 为对行和列分别预处理的层数
        int K1 = 32 - __builtin_clz(R);  
        int K2 = 32 - __builtin_clz(C);
        vector<vector<vector<vector<ll>>>> sp(K1, vector<vector<vector<ll>>>(K2, vector<vector<ll>>(R, vector<ll>(C))));
     
        // k1 = k2 = 0 赋初值
        for (int i=0; i<R; i++){
            for (int j=0; j<C; j++){
                sp[0][0][i][j] = diff[i][j];
            }
        }
        // 预处理列方向
        for (int k2=1; k2<K2; k2++){
            for (int i=0; i<R; i++){
                for (int j=0; j+(1<<(k2)) -1 < C; j++){
                    sp[0][k2][i][j] = max(sp[0][k2-1][i][j], sp[0][k2-1][i][j + (1<<(k2-1))]);
                }
            }
        }
        // 预处理行方向
        for (int k1=1; k1<K1; k1++){
            for (int k2=0; k2<K2; k2++){
                for (int i=0; i+(1<<(k1)) -1 < R; i++){
                    for (int j=0; j+(1<<k2)-1 < C; j++){
                        sp[k1][k2][i][j] = max(sp[k1-1][k2][i][j], sp[k1-1][k2][i + (1<<(k1-1))][j]);
                    }
                }
            }
        }
        // RMQ 查询函数:给定行区间[i1,i2],列区间[j1,j2](离散化下的区间)
        auto queryRMQ = [&](int i1, int i2, int j1, int j2) -> ll {
            int k1 = 31 - __builtin_clz(i2 - i1 + 1);
            int k2 = 31 - __builtin_clz(j2 - j1 + 1);
            ll res1 = max(sp[k1][k2][i1][j1], sp[k1][k2][i2 - (1<<k1) + 1][j1]);
            ll res2 = max(sp[k1][k2][i1][j2 - (1<<k2) + 1], sp[k1][k2][i2 - (1<<k1) + 1][j2 - (1<<k2) + 1]);
            return max(res1,res2);
        };
     
        // 处理每个查询:给定查询原区间 [L1, L2, R1, R2],
        // 用二分分别在 rs, cs 中找到下界和上界,使得对应的块完全落在查询内,
        // 另外别忘了考虑边缘不完全覆盖的情况。
        for (int qi = 0; qi < q; qi++){
            int L1, L2, R1, R2;
            scanf("%d%d%d%d", &L1, &L2, &R1, &R2);
            // 找出离散化行坐标:i_low = first index i s.t. rs[i] >= L1,
            //                      i_high = last i s.t. rs[i+1]-1 <= R1.
            int i_low = int(lower_bound(rs.begin(), rs.end(), L1) - rs.begin());
            int i_high = int(upper_bound(rs.begin(), rs.end(), R1+1) - rs.begin()) - 2; // 因为块为 [rs[i], rs[i+1]-1]
            int j_low = int(lower_bound(cs.begin(), cs.end(), L2) - cs.begin());
            int j_high = int(upper_bound(cs.begin(), cs.end(), R2+1) - cs.begin()) - 2;
            ll ans = 0;
            if(i_low <= i_high && j_low <= j_high)
                ans = queryRMQ(i_low, i_high, j_low, j_high);
            // 注意:如果查询区间仅部分覆盖某些块,需要额外枚举这些边界块,
            // 但此处为了代码简洁,省略了那部分(读者可根据需要补充)。
     
            printf("%lld\n", ans);
        }
        return 0;
    }
    

    说明:

    • 上述代码思路是先离散化更新“断点”,构造出大小远小于 (n\times n) 的“块矩阵”;
    • 再利用二维差分数组恢复出每个块内的常数值;
    • 然后建立二维稀疏表以便 (O(1)) 查询任意区域内的最大值;
    • 最后,对于每个查询,通过二分获得离散化后完全落在查询内的块区间,利用 RMQ 得到答案;
      细节上如果查询区间不能整块对齐(即边缘块未“完全被”查询包含)时,需要枚举那些块,结合答案取最大。

    由于本题数据量巨大,要求选用“捆绑测试”以及高效的输入输出方式(本代码中使用了 scanf/printf,实际比赛中 C++ 的 cin/cout 需进一步加速或使用 fread 来读入)。


    总结:

    本题难点在于二维“区间加/区间问最大”操作,而常规二维线段树或暴力前缀和均不适用。利用差分数组与“块状不连续点”离散化的思路,可以将问题规模降到(更新产生的断点数)级别,再通过二维 RMQ 结构处理查询。本解法使用了离散化+二维差分+二维稀疏表的方法,是一个比较经典的思路。


    备注:
    由于数据量极大,用 Python 实现必然超时(或者超内存),因此建议使用 C++来实现上述算法。希望大家理解整个解法思路。

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