http://acm.hdu.edu.cn/showproblem.php?pid=5749
思路：
bestcoder 84
贡献：所有可能的子矩阵的面积和
//len1：子矩阵所有长的和
for(int i=;i<=L;i++){
for(int j=;j<=R;j++){
len1+=i+j-;//-1是因为1*1单元格也是鞍点
}
}
// #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = ;
const int M = 1e6+;
const long long MOD = 1LL<<;
#define LL long long
#define LB long double
#define mi() (l+r)>>1
double const pi = acos(-);
const double eps = 1e-;
void fre() {
freopen("in.txt","r",stdin);
} int a[N][N];
int l[N][N],r[N][N],u[N][N],d[N][N];
stack<int>st;
LL ans;
int n,m;
void calc(){
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
int L=j-l[i][j],R=r[i][j]-j,U=i-u[i][j],D=d[i][j]-i;
LL tem=(LL)L*R*U*D*(L+R)*(U+D)/;
ans=(ans+(LL)a[i][j]*tem)%MOD;
}
printf("%I64d\n",ans);
} int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
while(!st.empty()) st.pop();
for(int i=;i<=n;i++){
a[i][]=a[i][m+]=-inf;
while(!st.empty()) st.pop();st.push();
for(int j=;j<=m;j++){
while(!st.empty()&&a[i][st.top()]>a[i][j]) st.pop();
l[i][j]=st.top();
st.push(j);
}
while(!st.empty()) st.pop();st.push(m+);
for(int j=m;j>=;j--){
while(!st.empty()&&a[i][st.top()]>a[i][j]) st.pop();
r[i][j]=st.top();
st.push(j);
}
}
for(int j=;j<=m;j++){
a[][j]=a[n+][j]=inf;
while(!st.empty()) st.pop();st.push();
for(int i=;i<=n;i++){
while(!st.empty()&&a[st.top()][j]<a[i][j]) st.pop();
u[i][j]=st.top();
st.push(i);
}
while(!st.empty()) st.pop();st.push(n+);
for(int i=n;i>=;i--){
while(!st.empty()&&a[st.top()][j]<a[i][j]) st.pop();
d[i][j]=st.top();
st.push(i);
}
}
ans=;
calc();
}
return ;
}