CF1195E OpenStreetMap 题解

很好的单调队列题。

---

题目传送门

题目意思：

给定一个 $n\times m$ 的矩阵，求出所有大小为 $a\times b$ 的子矩形中的最小值的和。

---

思路：

1. 通过题目给的要求建立二维数组 $h$。
2. 通过单调队列一行一行地扫，将扫出来地一个新的数组另存。
3. 再通过单调队列一列一列扫，这一次一边扫一遍求出 $ans$ 的值。最后输出即可。

---

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=9e6+10;
int n,m,a,b;
int x,y,z;
int g[N];
int h[3005][3005];
int hh[3005][3005];
int ans;
signed main()
{cin>>n>>m>>a>>b>>g[0]>>x>>y>>z;for(int i=1;i<=N;i++)g[i]=(g[i-1]*x+y)%z;for(int i=1;i<=n;i++)//建造高度数组for(int j=1;j<=m;j++)h[i][j]=g[(i-1)*m+j-1];for(int i=1;i<=n;i++)//扫行{deque<int>q;//双端队列for(int j=1;j<=m;j++){//如果超出窗口的范围了，就出队while(!q.empty()&&q.front()<=j-b)q.pop_front();//如果高度搞过枚举的高度，出队while(!q.empty()&&h[i][q.back()]>=h[i][j])q.pop_back();q.push_back(j);hh[i][j]=h[i][q.front()];//用新建的数组保存新的值}}for(int j=1;j<=m;j++)//扫列{deque<int>q;for(int i=1;i<=n;i++){//超出范围就出队while(!q.empty()&&q.front()<=i-a)q.pop_front();//不符合要求就出队while(!q.empty()&&hh[q.back()][j]>=hh[i][j])q.pop_back();q.push_back(i);if(i>=a&&j>=b)//保存答案ans+=hh[q.front()][j];}}cout<<ans;return 0;
}

---

完美撒花~