这道题我尝试过用一种四叉树写，但是由于复杂度有些高而且常数大，只过了三个点。
所以我用了另一种线段树写法。
先对每一行都建一棵线段树，然后将第 iii 行的从第 jjj 个数到第 j+n−1j+n-1j+n−1 个数中最大最小值存到 Maxi,jMax_{i,j}Maxi,j 和 Mini,jMin_{i,j}Mini,j 中，然后在对于每一列的 MaxMaxMax 和 MinMinMin 数组再建一个线段树，那就能求出每个 n×nn\times{n}n×n 的矩阵中最大数的值和最小数的值了。
当然这种做法并没有二维线段树更灵活。
学线段树学废了？
难度： 蓝
算法： 单调队列，线段树，ST 表等数据结构。
尝试一种二维 ST 表写法。
首先，预处理出 maxi,j,kmax_{i,j,k}maxi,j,k 为以 (i,j)(i,j)(i,j) 为左上角，边长 2k2^k2k 的正方形中的最大值，minminmin 同理。此处 k≤nk\le nk≤n 且 i+2k−1≤ai+2^k-1\le ai+2k−1≤a，j+2k−1≤bj+2^k-1\le bj+2k−1≤b。时间/空间复杂度 O(ablogn)O(ablogn)O(ablogn)。
然后，你就可以在 O(1)O(1)O(1) 的时间内获得每一个子矩形的最大/最小值了。方法就是把询问的子矩形拆成四个上述已经处理好的正方形，然后合并即可。
注意，如果需要计算 222 的幂次，请使用位运算，而不是 powpowpow。后者是带 logloglog 的。
代码量不大，加上许多不必要的卡常操作和注释后也才 1600B1600B1600B。
时间复杂度 O(ablogn)O(ablogn)O(ablogn)，遥遥领先。
#include<bits/stdc++.h> using namespace std; int n,m,k,ans=1000000000; int dep=1,len=2,max_st[1010][1010][10],min_st[1010][1010][10];//最大值和最小值的 st 表 inline int read(){ int x=0;int ch=getchar(); while (!isdigit(ch)&&(ch!=EOF)) ch=getchar(); while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x; }//读优 inline int maximum(int a,int b,int c,int d){return max(max(a,b),max(c,d));}//四数最大 inline int minimum(int a,int b,int c,int d){return min(min(a,b),min(c,d));}//四数最小 inline int max_que(int x,int y,int d){//查询以 x,y 为左上角边长为 d 的矩阵最大值 if(d==1) return max_st[x][y][0]; int r=log2(d-1),p=1<<r; return maximum(max_st[x][y][r],max_st[x+d-p][y][r],max_st[x][y+d-p][r],max_st[x+d-p][y+d-p][r]); } inline int min_que(int x,int y,int d){//查询以 x,y 为左上角边长为 d 的矩阵最小值 if(d==1) return min_st[x][y][0]; int r=log2(d-1),p=1<<r; return minimum(min_st[x][y][r],min_st[x+d-p][y][r],min_st[x][y+d-p][r],min_st[x+d-p][y+d-p][r]); } int main(){ n=read(),m=read(),k=read();//读入 & 建表 for(register int i=1;i<=n;i++){ for(register int j=1;j<=m;j++){ min_st[i][j][0]=max_st[i][j][0]=read(); } } while(1){ if(len>=k) break; for(register int i=1;i<=n-len+1;i++){ for(register int j=1;j<=m-len+1;j++){ max_st[i][j][dep]=max_que(i,j,len); min_st[i][j][dep]=min_que(i,j,len); } } dep++,len*=2; } for(register int i=1;i<=n-k+1;i++){//统计答案 for(register int j=1;j<=m-k+1;j++){ ans=min(ans,max_que(i,j,k)-min_que(i,j,k)); } } printf("%d",ans); }
By signing up a HFOJ universal account, you can submit code and join discussions in all online judging services provided by us.
Using your HFOJ universal account
C20250058
LV 9
@ 1 year ago
