【模板】 单调队列

 1 #include<bits/stdc++.h>
 2 using  namespace std;
 3 int a[1000+5][1000+5];
 4 int X[1000+5][1000+5];
 5 int x[1000+5][1000+5];
 6 int Y[1000+5][1000+5];
 7 int y[1000+5][1000+5];
 8 int Q[1000+5];
 9 int q[1000+5];
10 int main(){
11     int n,m,k;scanf("%d%d%d",&n,&m,&k);
12     for(int i=1;i<=n;++i){
13         for(int j=1;j<=m;++j)
14           scanf("%d",&a[i][j]);
15     }
16     int F,B,f,b;
17     for(int i=1;i<=n;++i){
18         F=B=f=b=Q[1]=q[1]=1;
19         for(int j=2;j<=m;++j){
20             while(a[i][j]>=a[i][Q[B]]&&F<=B) --B;
21             while(a[i][j]<=a[i][q[b]]&&f<=b) --b;
22             Q[++B]=q[++b]=j;
23             while(j-Q[F]>=k) ++F;
24             while(j-q[f]>=k) ++f;
25             if(j>=k){
26                 X[i][j-k+1]=a[i][Q[F]];
27                 x[i][j-k+1]=a[i][q[f]];
28             }
29         }
30     }
31     for(int i=1;i<=m-k+1;++i){
32         F=B=f=b=Q[1]=q[1]=1;
33         for(int j=2;j<=n;++j){
34             while(X[j][i]>=X[Q[B]][i]&&F<=B) --B;
35             while(x[j][i]<=x[q[b]][i]&&f<=b) --b;
36             Q[++B]=q[++b]=j;
37             while(j-Q[F]>=k) ++F;
38             while(j-q[f]>=k) ++f;
39             if(j>=k){
40                 Y[j-k+1][i]=X[Q[F]][i];
41                 y[j-k+1][i]=x[q[f]][i];
42             }
43         }
44     }
45     int ans=0x3f3f3f3f;
46     for(int i=1;i<=n-k+1;++i){
47         for(int j=1;j<=m-k+1;++j){
48             ans=min(ans,Y[i][j]-y[i][j]);
49         }
50     }
51     printf("%d",ans);
52     return 0;
53 }