RMQ求出矩阵区间最大，数组sum和pro分别存坐标i，j到右下角的矩阵所有元素和，和平方和，然后根据容斥求出某一矩阵的元素和，平方和。然后根据方差展开求最大坐标，就OK啦。。。。。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<map> #include<cmath> #include<algorithm> #define inf 0x3f3f3f3f #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; typedef long long ll; const int mx=3e2+10; int mat[mx][mx][10][10],_x,_y; int n,m,sum[mx][mx],cases=1,q,x,y; ll pro[mx][mx]; double ans; void RMQ(){ for(int r=0;(1<<r)<=n;r++){ for(int c=0;(1<<c)<=m;c++){ if(!r&&!c) continue; for(int i=1;i+(1<<r)-1<=n;i++){ for(int j=1;j+(1<<c)-1<=m;j++){ if(!r) mat[i][j][r][c]=max(mat[i][j][r][c-1],mat[i][j+(1<<(c-1))][r][c-1]); else mat[i][j][r][c]=max(mat[i][j][r-1][c],mat[i+(1<<(r-1))][j][r-1][c]); } } } } } int query(int a,int b){ int hi=log(x)/log(2.0),wi=log(y)/log(2.0); int k1=mat[a][b][hi][wi]; int k2=mat[a+x-(1<<hi)][b][hi][wi]; int k3=mat[a][b+y-(1<<wi)][hi][wi]; int k4=mat[a+x-(1<<hi)][b+y-(1<<wi)][hi][wi]; return max(max(k1,k2),max(k3,k4)); } void solve(int v,int a,int b){ int S=sum[a][b]-v; ll P=pro[a][b]-v*v; S-=sum[a+x][b]+sum[a][b+y]-sum[a+x][b+y]; P-=pro[a+x][b]+pro[a][b+y]-pro[a+x][b+y]; int c=x*y-1; double ave=1.0*S/c; double val=ave*ave+1.0*(P-2*ave*S)/c; if(val<ans){ ans=val; _x=a,_y=b; } } int main(){ while(cin>>n>>m){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mat[i][j][0][0]); for(int i=m+1;i>=1;i--) sum[n+1][i]=pro[n+1][i]=0; for(int i=n+1;i>=1;i--) sum[i][m+1]=pro[i][m+1]=0; for(int i=n;i>=1;i--){ int Sum=mat[i][m][0][0]; ll Pro=mat[i][m][0][0]*mat[i][m][0][0]; for(int j=m;j>=1;j--){ sum[i][j]=sum[i+1][j]+Sum; pro[i][j]=pro[i+1][j]+Pro; Sum+=mat[i][j-1][0][0]; Pro+=mat[i][j-1][0][0]*mat[i][j-1][0][0]; } } RMQ(); printf("Case %d:\n",cases++); scanf("%d",&q); while(q--){ ans=inf; scanf("%d%d",&x,&y); for(int i=1;i<=n-x+1;i++){ for(int j=1;j<=m-y+1;j++){ int v=query(i,j); solve(v,i,j); } } printf("(%d, %d), %.2lf\n",_x,_y,ans); } } return 0; }
