hdu6052

201707

• 单独考虑每个颜色。
• 定义矩形的标志点：矩形最左最上的点。
• 对于一个点，求以它为标志点的所有矩形。
• u[i][j]表示点[i][j]最多能向上扩展多少。
• d[i][j]表示点[i][j]最多能向下扩展多少。
• o[i][j]表示点[i][j]是否是当前颜色。
• 这里初始化的方式可以学一下。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
const int N=105;
int n,m,p;
int a[N][N],u[N][N],d[N][N],o[N][N];
vector<pair<int,pii > > v;
pair<int*,int> sta[3*N*N];
void upd(int *x,int y) {
    sta[++p]=mp(x,*x);
    *x=y;
}
void back() {
    *sta[p].fi=sta[p].se;
    --p;
}
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        scanf("%d%d",&n,&m);
        ///init
        v.clear();
        p=0;
        ///read
        rep(i,1,n+1) {
            rep(j,1,m+1) {
                int x;scanf("%d",&x);
                a[i][j]=x;
                v.pb(mp(x,mp(j,i)));
                u[i][j]=0;d[i][j]=n;o[i][j]=0;
            }
        }
        ///solve
        sort(v.begin(),v.end());
        ll P=0,Q=0;
        rep(i,1,n+1) rep(j,1,m+1) Q+=1ll*(n-i+1)*(m-j+1);
        for(int ci=0,cj;ci<sz(v);ci=cj) {
            cj=ci+1;
            while(cj<sz(v)&&v[ci].fi==v[cj].fi) ++cj;
            for(int i=ci,j,x,y,w;i<cj;i=j) {
                vector<int> r;
                j=i;y=v[i].se.fi;
                while(j<cj&&v[j].se.fi==y) r.pb(v[j++].se.se);
                ///upd up
                x=w=0;
                rep(k,0,sz(r)) {
                    for(;w<=r[k];++w) upd(&u[w][y],x);
                    x=r[k];
                }
                for(;w<=n;++w) upd(&u[w][y],x);
                ///calc
                rep(k,0,sz(r)) {
                    w=r[k];
                    int xl=u[w][y],xr=n;
                    for(int _y=y;_y;--_y) {
                        if(_y!=y&&o[w][_y]) break;
                        xl=max(xl,u[w][_y]);
                        xr=min(xr,d[w][_y]);
                        if(xl+1>xr) break;
                        P+=1ll*(w-xl)*(xr-w+1)*(m-y+1);
                    }
                }
                ///upd down
                x=n+1;w=n;
                for(int k=sz(r)-1;k>=0;--k) {
                    for(;w>=r[k];--w) upd(&d[w][y],x-1);
                    x=r[k];
                }
                for(;w;--w) upd(&d[w][y],x-1);
                rep(k,0,sz(r)) upd(&o[r[k]][y],1);
            }
            while(p) back();
        }
        ///print
        printf("%.9f\n",1.0*P/Q);
    }
    return 0;
}