【題目敘述】https://codeforces.com/contest/1195/problem/E
【解題想法】Monotonic Queue (單調隊列)
【題目翻譯】
Seryozha開設了一門製作「Stepanovo休閒中心」高度圖的課程。他在地圖上放置了一個大小為 𝑛×𝑚 個單元格的矩形網格(網格的rows從北到南編號為1到 𝑛，網格的columns從西到東編號為1到 𝑚)。接著，他測量了每個網格(cell)在「雷賓斯克海平面」以上的平均高度，並獲得了一個尺寸為 𝑛×𝑚 的矩陣 (高度矩陣)。每個網格座標(𝑖, 𝑗)位於第𝑖行和第𝑗列的交點，高度為ℎ𝑖,𝑗。
Seryozha將在瀏覽器中查看他的工作結果。 Seryozha的電腦螢幕可以吻合大小為𝑎×𝑏 (1≤𝑎≤𝑛, 1≤𝑏≤𝑚)的子矩陣 (高度矩陣的子矩陣)。 Seryozha想要知道天氣如何影響娛樂中心。例如，如果下雨，雨水會聚集在哪裡。為此，他將在電腦螢幕上顯示的所有網格中找到「高度最小」的網格。 請幫助Seryozha計算在螢幕上可以看到的所有可能的「子矩陣的單元格的高度」之和。換句話說，您必須計算所有大小為𝑎×𝑏的子矩陣的最小高度之和。(𝑖, 𝑗)為左上角的座標。1≤𝑖≤𝑛−𝑎 + 1, 1≤𝑗≤𝑚−𝑏 +1。
題目給出整數 g0, x, y and z，產生 h[i][j] 的公式如下：
- 先用題目給的方程式產生 h 高度矩陣，左上角座標 (1, 1)。
- 基於 h 矩陣，逐列沿著column的方向(由西往東)掃描，建構出 row 矩陣。(資料填入row矩陣時，由上往下填。)
- 或者，由於座標是one-based，可以不用開新的row矩陣，改為「重複利用」h矩陣（從 h[0][ ] 開始填入資料。）
- deque 維護「單調遞增」資料，dq.front( )即為區間最小值。
- 基於 row 矩陣（或更新後的 h矩陣），逐列由西往東掃描，把區間最小值累加到 ans。
- 【細節提醒】
- (Line-6/12) 變數 g 和 ans 都需要宣告成 long long
- (Line-15/16) 依照題目給的公式產生 h矩陣
- (Line-33) 記得清空 deque
- (Line-22/35) 移除過時的資料
- (Line-25/38) 維護單調隊列資料的遞增性
- (Line-34) 留意更新後的 h矩陣的有效資料範圍
#include <iostream>
#include <deque>
using namespace std;
int n, m, a, b, x, y, z, g0, h[3005][3005];
long long ans;
deque <int> dq;
int main() {
cin >> n >> m >> a >> b;
cin >> g0 >> x >> y >> z;
long long last = g0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
h[i][j] = last;
last = (last * x + y) % z;
}
}
for (int i = 1; i <= n; i++){
// dq.clear();
for (int j = 1; j <= m; j++){
while (!dq.empty() && dq.front() <= j-b){
dq.pop_front();
}
while (!dq.empty() && h[i][dq.back()] > h[i][j]){
dq.pop_back();
}
dq.push_back(j);
h[i-1][j] = h[i][dq.front()];
}
}
for (int j = b; j <= m; j++){
dq.clear();
for (int i = 0; i < n; i++){
while (!dq.empty() && dq.front() <= i-a){
dq.pop_front();
}
while (!dq.empty() && h[dq.back()][j] > h[i][j]){
dq.pop_back();
}
dq.push_back(i);
h[i][j-b] = h[dq.front()][j];
}
}
for (int i = a-1; i < n; i++){
for (int j = 0; j <= m-b; j++){
ans += h[i][j];
}
}
cout << ans << "\n";
}