首页 > 代码库 > Codeforces gym Hello 2015 Div1 C and Div2 E
Codeforces gym Hello 2015 Div1 C and Div2 E
Codeforces gym Hello 2015 Div1 C and Div2 E
Codeforces gym 100570 problem C
Codeforces gym 100571 problem E
Problem
给一个N行M列的矩阵Ma，进行Q次（Q<=10）查询，每次给定一个K，问有多少子矩阵，满足最大值max - 最小值min <=K。
Limits
Time Limit(ms): 8000
Memory Limit(MB): 512
N, M: [1, 400]
Q: [1, 10]
Ma(i, j), K: [1, 10^9]
Solution
（Thanks ikbal）
如上图所说，每行枚举所有连续子列，则有(1+M)*M/2个；某一行的一个连续子列，在其余行也存在一个相同位置的连续子列，N行则有N个。每个连续子列都可以求出最大值max和最小值min，则这N个连续子列实则是N个序偶<max, min>。那么问题就转换成了：每次求出N个序偶中，有多少个连续序偶串满足max - min<=K，求(1+M)*M/2次。
枚举的复杂度是O(M^2)，而新的问题可以在线性时间内解决。
More
对于“每次求出N个序偶中，有多少个连续序偶串满足max - min<=K”，只需用two-pointers或者单调栈等方法与高效的RMQ方法配合，即可在O(N)复杂度内解决。换句话说，能线性解决，是利用了区间最值的两个性质。一，一个区间进行扩展，其最大值单调不降，最小值单调不升；而，一个区间进行收缩，其最大值单调不升，最小值单调不降。
尽量多优化。
Complexity
Time Complexity: O(Q*M*M*N)（不计RMQ复杂度）
Memory Complexity: O(N*M)
Source
Codeforces gym Hello 2015 Div1 C and Div2 E
Code
Codeforces gym Hello 2015 Div1 C and Div2 E From My Github
Codeforces gym Hello 2015 Div1 C and Div2 E
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。