P6109 [Ynoi2009] rprmq1 题目背景 我谔谔 本题读入量约 13 MB,输出量约 7 MB,请选择合适的输入输出方法 题目描述 有一个 $n \times…
- User
P6109 [Ynoi2009] rprmq1
题目背景
我谔谔
本题读入量约 13 MB,输出量约 7 MB,请选择合适的输入输出方法
题目描述
有一个 的矩阵 ,初始全是 ,有 次修改操作和 次查询操作,先进行所有修改操作,然后进行所有查询操作。
一次修改操作会给出 ,代表把所有满足 且 的 元素加上一个值 。
一次查询操作会给出 ,代表查询所有满足 且 的 元素的最大值。
输入格式
第一行三个由空格分隔的整数 。
之后 行,每行给出五个整数 ,表示一次修改操作。
之后 行,每行给出四个整数 ,表示一次查询操作。
输出格式
输出 行,对每次查询操作输出一行一个数表示答案。
输入输出样例 #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。
对于另外 的数据,。
对于另外 的数据,。
对于另外 的数据,,。
对于另外 的数据,。
对于 的数据,,,,,。
- 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 与所有 (l_{1}, r_{1}+1))以及所有列坐标(包括 1 与所有 (l_{2}, r_{2}+1)),排序后去重。令映射函数为
[ idx_r(i)=\text{离散后的行号},\quad idx_c(j)=\text{离散后的列号}. ] -
构造二维差分数组。
用一个二维数组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
-
二维前缀和。
对离散化后的二维数组做行前缀和再列前缀和,即得到每个块的“值”。注意:由于原来每个块对应原区间长度不一(例如行区间长度为 (R[i+1]-R[i])),但是由于所有更新都是整体加值,“块内所有值均相同”。 -
构造二维 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 询问这一区间即可。(注意查询时有可能不“完全匹配”,这时还要枚举几个边界部分的块,但整体思路类似,与典型二维离散化查询类似。) -
输出答案。
下面给出一个 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++来实现上述算法。希望大家理解整个解法思路。
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.