@[hnxxwpf](/user/700122) RMQ:你好
by 菜のcrzOvO @ 2024-04-06 19:39:06
单调队列可能是绿蓝，但RMQ绝对是黄或水绿
by 菜のcrzOvO @ 2024-04-06 19:39:44
顶天绿这种，甚至还没有qwq
by Genius_Star @ 2024-04-06 19:39:59
A+B 大部分写法思维难度较大，且难度巨大，并且需注意许多细节，建议升黑。
by _Ad_Astra_ @ 2024-04-06 19:40:53
我独立做不出这个题，支持楼主捏 qwq
by sqrtDataStructure @ 2024-04-06 19:41:22
@[hnxxwpf](/user/700122) 这思维大？码量大？感觉挺一眼的
by xiaoxiaoyyds @ 2024-04-06 19:43:11
@[xiaoxiaoyyds](/user/793036) 你好强%%%%%
by sqrtDataStructure @ 2024-04-06 19:44:00
@[xiaoxiaoyyds](/user/793036) ```
#include<iostream>
#include<list>
using namespace std;
int a,b,k,g[1001][1001],ax1[1001][1001],ax2[1001][1001],in1[1001][1001],in2[1001][1001],ans = 0x3f3f3f3f;
list<int> xax,xin,yax,yin;
int main(){
scanf("%d%d%d",&a,&b,&k);
for(int i = 1;i <= a;++i){
for(int j = 1;j <= b;++j){
scanf("%d",&g[i][j]);
if(!xax.empty() && xax.front()<j-k+1) xax.pop_front();
while(!xax.empty() && g[i][xax.back()]<=g[i][j]) xax.pop_back();
xax.push_back(j);
if(!xin.empty() && xin.front()<j-k+1) xin.pop_front();
while(!xin.empty() && g[i][xin.back()]>=g[i][j]) xin.pop_back();
xin.push_back(j);
if(j >= k){
ax1[i][j-k+1] = g[i][xax.front()];
in1[i][j-k+1] = g[i][xin.front()];
}
}
xax.clear();
xin.clear();
}
for(int i = 1;i <= b-k+1;++i){
for(int j = 1;j <= a;++j){
if(!yax.empty() && yax.front()<j-k+1) yax.pop_front();
while(!yax.empty() && ax1[j][i]>=ax1[yax.back()][i]) yax.pop_back();
yax.push_back(j);
if(!yin.empty() && yin.front()<j-k+1) yin.pop_front();
while(!yin.empty() && in1[j][i]<=in1[yin.back()][i]) yin.pop_back();
yin.push_back(j);
if(j >= k){
ax2[j-k+1][i] = ax1[yax.front()][i];
in2[j-k+1][i] = in1[yin.front()][i];
}
}
yax.clear();
yin.clear();
}
for(int i = 1;i <= a-k+1;++i) for(int j = 1;j <= b-k+1;++j) ans = min(ans,ax2[i][j] - in2[i][j]);
printf("%d",ans);
return 0;
}
```
你管这叫码量小
by hnxxwpf @ 2024-04-06 19:45:57
@[xiaoxiaoyyds](/user/793036)
```
#include<iostream>
#include<list>
using namespace std;
int a,b,k,g[1001][1001],ax1[1001][1001],ax2[1001][1001],in1[1001][1001],in2[1001][1001],ans = 0x3f3f3f3f;
list<int> xax,xin,yax,yin;
int main(){
scanf("%d%d%d",&a,&b,&k);
for(int i = 1;i <= a;++i){
for(int j = 1;j <= b;++j){
scanf("%d",&g[i][j]);
if(!xax.empty() && xax.front()<j-k+1) xax.pop_front();
while(!xax.empty() && g[i][xax.back()]<=g[i][j]) xax.pop_back();
xax.push_back(j);
if(!xin.empty() && xin.front()<j-k+1) xin.pop_front();
while(!xin.empty() && g[i][xin.back()]>=g[i][j]) xin.pop_back();
xin.push_back(j);
if(j >= k){
ax1[i][j-k+1] = g[i][xax.front()];
in1[i][j-k+1] = g[i][xin.front()];
}
}
xax.clear();
xin.clear();
}
for(int i = 1;i <= b-k+1;++i){
for(int j = 1;j <= a;++j){
if(!yax.empty() && yax.front()<j-k+1) yax.pop_front();
while(!yax.empty() && ax1[j][i]>=ax1[yax.back()][i]) yax.pop_back();
yax.push_back(j);
if(!yin.empty() && yin.front()<j-k+1) yin.pop_front();
while(!yin.empty() && in1[j][i]<=in1[yin.back()][i]) yin.pop_back();
yin.push_back(j);
if(j >= k){
ax2[j-k+1][i] = ax1[yax.front()][i];
in2[j-k+1][i] = in1[yin.front()][i];
}
}
yax.clear();
yin.clear();
}
for(int i = 1;i <= a-k+1;++i) for(int j = 1;j <= b-k+1;++j) ans = min(ans,ax2[i][j] - in2[i][j]);
printf("%d",ans);
return 0;
}
```
你管这叫码量小？！
by hnxxwpf @ 2024-04-06 19:46:40
我是用二维 ST 表做的，感觉还是有点难度的 qwq
```cpp
#include <bits/stdc++.h>
#define _rep(i_,a_,b_) for(int i_ = a_;i_ <= b_;++i_)
int in(void) { int x; scanf("%d",&x); return x; }
typedef long long ll;
using namespace std;
const int kN = 1005;
int st[11][kN][kN],lg[kN],ans[kN][kN],A[kN][kN];
int a=in(),b=in(),n=in();
typedef int func_t(int,int);
int query(int x,int y,func_t fuc) {
int _ = lg[n],endx = x + n - 1,endy = y + n - 1;
return fuc(fuc(st[_][x][y],st[_][endx - (1 << _) + 1][y]),fuc(st[_][x][endy - (1 << _) + 1],st[_][endx - (1 << _) + 1][endy - (1 << _) + 1]));
}
void init_st(func_t fuc) {
_rep(i,1,a) _rep(j,1,b) st[0][i][j] = A[i][j];
_rep(sz,1,10) for(int i = 1;i + (1 << sz) - 1 <= a; ++i) for(int j = 1;j + (1 << sz) - 1 <= b;++j) {
#define L (1 << (sz - 1))
st[sz][i][j] = fuc(st[sz-1][i][j],st[sz-1][i + L][j]);
st[sz][i][j] = fuc(st[sz][i][j],fuc(st[sz-1][i][j + L],st[sz-1][i + L][j + L]));
}
}
int Min(int a,int b) { return min(a,b); }
int Max(int a,int b) { return max(a,b); }
int main() {
_rep(i,1,a) _rep(j,1,b) A[i][j] = in();
_rep(i,2,kN - 1) lg[i] = lg[i >> 1] + 1;
init_st(Min);
for(int i = 1;i + n - 1 <= a;++i) for(int j = 1;j + n - 1 <= b;++j) ans[i][j] = query(i,j,Min);
init_st(Max);
int anss = 0x7fffffff;
for(int i = 1;i + n - 1 <= a;++i) for(int j = 1;j + n - 1 <= b;++j) anss = min(anss,query(i,j,Max) - ans[i][j]);
printf("%d\n",anss);
return 0;
}
```
by sqrtDataStructure @ 2024-04-06 19:48:16