题意：给定n*m的矩阵小格。每个小格都有一个数值，代表这个位置人的身高。给q个询问，每个询问给 x,y 要求在这个n*m的矩阵中找一个x*y的子矩阵（n是行m是列，x是行，y是列）这个子矩阵中除去最高的那个人。剩余人的方差。求满足x*y的子矩阵的方差最小的xy坐标，并输出方差
首先贡献一发方差公式：
可以把它分拆成
((x1*x1+x2*x2+.....+xn*xn) - 2*(x1+x2+..+xn)*(平均值)+n*(平均值)*(平均值))/n
想到这里的时候已经成功了一半了。所谓好的开端就是成功的一半。
现在我们转换一下问题：
我转换成了一下三个小问题：
1)求出给定的一个大矩形中的某个子矩形的和，我们希望复杂度尽量低
2)求出给定的一个大矩形中的某个子矩形的平方的和，我们希望复杂度尽量低
3)求出给定的一个大矩形中的某个子矩形的最大值，我们希望复杂度也尽量低
好了，如果能明白并写出这三个小问题的解。那么这题也就这样了。
1)可以预处理出左上角到当前i,j位置的和sum1[i][j]，这样查询的时候就可以直接O(1)的查询了，对于给定的x,y,x1,y1这个矩形。那么这个矩形的值为：
sum1[x1][y1]-sum1[x-1][y1]-sum1[x1][y1-1]-sum1[x-1][y-1]
2)可以预处理出左上角到当前i,j位置的平方的和，这样查询的时候也可以直接O(1)的查询，同上。1)和2)是同一个做法。
3)2维RMQ求子矩形的最大值。
好了，代码：
//author: CHC
//First Edit Time: 2014-07-23 15:00
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 310
int rec[MAXN][MAXN];
int dp[MAXN][MAXN][10][10];
int n,m;
int summ[MAXN][MAXN];
int sumn[MAXN][MAXN];
int sum1[MAXN][MAXN];
int sum2[MAXN][MAXN];
inline int maxm(int a,int b,int c,int d){
if(a<b)a=b; if(a<c)a=c; if(a<d)a=d;
return a;
}
void st()
{
for(int k=0;(1<<k)<=n;k++)
for(int l=0;(1<<l)<=m;l++)
for(int i=1;i+(1<<k)-1<=n;i++)
for(int j=1;j+(1<<l)-1<=m;j++)
{
if(!k&&!l){
dp[i][j][k][l]=rec[i][j];
}
else if(k==0){
dp[i][j][k][l]=max(dp[i][j][k][l-1],dp[i][j+(1<<(l-1))][k][l-1]);
}
else if(l==0){
dp[i][j][k][l]=max(dp[i][j][k-1][l],dp[i+(1<<(k-1))][j][k-1][l]);
}
else {
dp[i][j][k][l]=maxm(dp[i][j][k-1][l-1],dp[i+(1<<(k-1))][j][k-1][l-1],
dp[i][j+(1<<(l-1))][k-1][l-1],dp[i+(1<<(k-1))][j+(1<<(l-1))][k-1][l-1]);
}
}
}
int rmq2dmax(int x,int y,int x1,int y1){
int k=log(x1-x+1)/log(2);
int l=log(y1-y+1)/log(2);
return maxm(dp[x][y][k][l],dp[x1-(1<<k)+1][y][k][l],
dp[x][y1-(1<<l)+1][k][l],dp[x1-(1<<k)+1][y1-(1<<l)+1][k][l]);
}
void pre_do(){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
summ[i][j]=summ[i][j-1]+rec[i][j];
sum1[i][j]=sum1[i-1][j]+summ[i][j];
sumn[i][j]=sumn[i][j-1]+rec[i][j]*rec[i][j];
sum2[i][j]=sum2[i-1][j]+sumn[i][j];
}
}
int getare1(int x,int y,int x1,int y1){
return sum1[x1][y1]-sum1[x-1][y1]-sum1[x1][y-1]+sum1[x-1][y-1];
}
int getare2(int x,int y,int x1,int y1){
return sum2[x1][y1]-sum2[x-1][y1]-sum2[x1][y-1]+sum2[x-1][y-1];
}
int main()
{
memset(summ,0,sizeof(summ));
memset(sum1,0,sizeof(sum1));
int cas=0;
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&rec[i][j]);
st();
pre_do();
int q;
scanf("%d",&q);
printf("Case %d:\n",++cas);
int nn,mm;
while(q--){
scanf("%d%d",&nn,&mm);
int posx=1,posy=1;
double fancha=-1.0;
for(int x=1;x+nn-1<=n;x++)
for(int y=1;y+mm-1<=m;y++){
int ma=rmq2dmax(x,y,x+nn-1,y+mm-1);
int a1=getare1(x,y,x+nn-1,y+mm-1)-ma;
int a2=getare2(x,y,x+nn-1,y+mm-1)-ma*ma;
double _x=(double)a1/(nn*mm-1);
double val=1.0*(a2-2*_x*a1+(nn*mm-1)*_x*_x)/(nn*mm-1);
if(fancha<0||fancha>val){
fancha=val;
posx=x;posy=y;
}
//printf("%lf\n",a2-2*_x*a1+(nn*mm-1)*_x*_x);
//printf("%d %lf %lf\n",a2,2*_x*a1,(nn*mm-1)*_x*_x);
//printf("%d %d ma:%d a1:%d a2:%d val:%lf _x:%lf\n",x,y,ma,a1,a2,val,_x);
}
if(fancha<0)fancha=0.0;
printf("(%d, %d), %.2lf\n",posx,posy,fancha);
}
}
return 0;
}