BZOJ1047: [HAOI2007]理想的正方形

时间：2023-03-08 17:44:57
BZOJ1047: [HAOI2007]理想的正方形

传送门

蛤省省选果然水啊，我这种蒟蒻都能一遍A。

横向纵向维护两个单调队列，做两次求最大和最小的，总复杂度$O(NM)$

码农题，考察代码实现能力

 //BZOJ 1047
 //by Cydiater
 //2016.9.17
 #include <iostream>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <cmath>
 #include <ctime>
 #include <map>
 #include <iomanip>
 #include <string>
 #include <algorithm>
 #include <queue>
 using namespace std;
 #define ll long long
 #define up(i,j,n)        for(int i=j;i<=n;i++)
 #define down(i,j,n)        for(int i=j;i>=n;i--)
 ;
 const int oo=0x3f3f3f3f;
 inline int read(){
     ,f=;
     ;ch=getchar();}
     +ch-';ch=getchar();}
     return x*f;
 }
 int N,M,K,a[MAXN][MAXN],head[MAXN],tail[MAXN],lable_max[MAXN][MAXN],lable_min[MAXN][MAXN],q[MAXN][MAXN],extro_q[MAXN],extro_head,extro_tail,ans=oo;
 namespace solution{
     inline void push(int co,int id){q[co][++tail[co]]=id;}
     void init(){
         N=read();M=read();K=read();
         up(i,,N)up(j,,M)a[i][j]=read();
     }
     void Queue_max(){
         memset(tail,,sizeof(tail));
         up(i,,N)head[i]=;
         up(i,,N)up(j,,K){
             while(head[i]<=tail[i]&&a[i][j]>a[i][q[i][tail[i]]])tail[i]--;
             push(i,j);//load y
         }
         extro_head=;extro_tail=;
         up(i,,K-){
             while(extro_head<=extro_tail&&a[i][q[i][head[i]]]>a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--;
             extro_q[++extro_tail]=i;//load x
         }
         up(i,K,N){
             >K&&extro_head<=extro_tail)extro_head++;
             while(extro_head<=extro_tail&&a[i][q[i][head[i]]]>a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--;
             extro_q[++extro_tail]=i;//load x
             lable_max[i][K]=a[extro_q[extro_head]][q[extro_q[extro_head]][head[extro_q[extro_head]]]];
         }
         up(j,K+,M){
             up(i,,N){
                 >K&&head[i]<=tail[i])head[i]++;
                 while(head[i]<=tail[i]&&a[i][j]>a[i][q[i][tail[i]]])tail[i]--;
                 push(i,j);//load y
             }
             extro_head=;extro_tail=;
             up(i,,K-){
                 while(extro_head<=extro_tail&&a[i][q[i][head[i]]]>a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--;
                 extro_q[++extro_tail]=i;//load x
             }
             up(i,K,N){
                 >K&&extro_head<=extro_tail)extro_head++;
                 while(extro_head<=extro_tail&&a[i][q[i][head[i]]]>a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--;
                 extro_q[++extro_tail]=i;//load x
                 lable_max[i][j]=a[extro_q[extro_head]][q[extro_q[extro_head]][head[extro_q[extro_head]]]];
             }
         }
     }
     void Queue_min(){
         memset(tail,,sizeof(tail));
         up(i,,N)head[i]=;
         up(i,,N)up(j,,K){
             while(head[i]<=tail[i]&&a[i][j]<a[i][q[i][tail[i]]])tail[i]--;
             push(i,j);//load y
         }
         extro_head=;extro_tail=;
         up(i,,K-){
             while(extro_head<=extro_tail&&a[i][q[i][head[i]]]<a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--;
             extro_q[++extro_tail]=i;//load x
         }
         up(i,K,N){
             >K&&extro_head<=extro_tail)extro_head++;
             while(extro_head<=extro_tail&&a[i][q[i][head[i]]]<a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--;
             extro_q[++extro_tail]=i;//load x
             lable_min[i][K]=a[extro_q[extro_head]][q[extro_q[extro_head]][head[extro_q[extro_head]]]];
         }
         up(j,K+,M){
             up(i,,N){
                 >K&&head[i]<=tail[i])head[i]++;
                 while(head[i]<=tail[i]&&a[i][j]<a[i][q[i][tail[i]]])tail[i]--;
                 push(i,j);//load y
             }
             extro_head=;extro_tail=;
             up(i,,K-){
                 while(extro_head<=extro_tail&&a[i][q[i][head[i]]]<a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--;
                 extro_q[++extro_tail]=i;//load x
             }
             up(i,K,N){
                 >K&&extro_head<=extro_tail)extro_head++;
                 while(extro_head<=extro_tail&&a[i][q[i][head[i]]]<a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--;
                 extro_q[++extro_tail]=i;//load x
                 lable_min[i][j]=a[extro_q[extro_head]][q[extro_q[extro_head]][head[extro_q[extro_head]]]];
             }
         }
     }
     void slove(){
         Queue_max();
         Queue_min();
     }
     void output(){
         /*up(i,1,N){
             up(j,1,M)cout<<lable_max[i][j]<<' ';
             cout<<endl;
         }
         puts("");
         up(i,1,N){
             up(j,1,M)cout<<lable_min[i][j]<<' ';
             cout<<endl;
         }
         puts("");*/
         up(i,K,N)up(j,K,M)ans=min(ans,lable_max[i][j]-lable_min[i][j]);
         cout<<ans<<endl;
     }
 }
 int main(){
     //freopen("input.in","r",stdin);
     using namespace solution;
     init();
     slove();
     output();
     ;
 }

妈的，下次再也不起这么长的变量名了，敲到手麻

相关文章