bzoj1047 [HAOI2007]理想的正方形

优先队列维护每行每n个的最大值最小值,并且再通过优先队列扩展到二维即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000+5;
int a,b,n;
int num[maxn][maxn];
int maxi[maxn][maxn],mini[maxn][maxn];
int maxc[maxn][maxn],minc[maxn][maxn];
struct pq_Max{
priority_queue<int > a,b;
void ini(){while(!a.empty()) a.pop();while(!b.empty()) b.pop();}
void add(int x) {a.push(x);}
void del(int x) {b.push(x);}
int getmax(){
while(!b.empty() && a.top()==b.top()) {a.pop();b.pop();}
return a.top();
}
};
struct pq_Min{
priority_queue<int ,vector<int> ,greater<int > > a,b;
void ini(){while(!a.empty()) a.pop();while(!b.empty()) b.pop();}
void add(int x) {a.push(x);}
void del(int x) {b.push(x);}
int getmin(){
while(!b.empty() && a.top()==b.top()) {a.pop();b.pop();}
return a.top();
}
};
int main()
{
scanf("%d%d%d",&a,&b,&n);
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++)scanf("%d",&num[i][j]);
for(int i=1;i<=a;i++)
{
pq_Max bq;pq_Min sq;bq.ini();sq.ini();
for(int j=1;j<=b;j++)
{
bq.add(num[i][j]);sq.add(num[i][j]);
if(j>=n){
maxi[i][j]=bq.getmax();mini[i][j]=sq.getmin();
bq.del(num[i][j-n+1]);sq.del(num[i][j-n+1]);
}
}
}
for(int j=n;j<=b;j++)
{
pq_Max bq;pq_Min sq;
bq.ini();sq.ini();
for(int i=1;i<=a;i++)
{
bq.add(maxi[i][j]);sq.add(mini[i][j]);
if(i>=n){
maxc[i][j]=bq.getmax();minc[i][j]=sq.getmin();
bq.del(maxi[i-n+1][j]);sq.del(mini[i-n+1][j]);
}
}
}
int res=0x3f3f3f3f;
for(int i=n;i<=a;i++)
for(int j=n;j<=b;j++)
res=min(res,maxc[i][j]-minc[i][j]);
printf("%d\n",res);
return 0;
}