HDu 6052単調スタックデュアルポインタ
2267 ワード
各色の寄与を考慮し、現在の色を考慮すると、その色の格子が1であり、他の格子が0であり、0でないサブマトリクスの個数がその色の寄与である.各色の点を上から下へ、左から右へ遍歴し、各点に対して現在の点を含むが、同じ色の点に以前アクセスしたサブマトリクスの数は含まれない.(i,j)にアクセスするときは,次回は任意に取り,上界を列挙し,単調スタックからその上界の左右境界li,riを探し出し,2つのポインタで行う.この点の答え寄与に(j-li)*(ri-j)*(n-i+1)を加える
最後に、すべてのマトリクス数で除算します.
cuoをよく書いて、1年調整します.の
最後に、すべてのマトリクス数で除算します.
cuoをよく書いて、1年調整します.の
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int MAXN = 110;
int n, m, color[MAXN][MAXN];
struct Node
{
int row, col;
Node(){}
Node(int _i, int _j) :row(_i), col(_j){}
}stack[MAXN], stackr[MAXN];
int top, topr;
int pre[MAXN * MAXN][MAXN];
int now[MAXN * MAXN][MAXN];
void init()
{
memset(pre, 0, sizeof(pre));
}
void Count(int i, int j, int cc)
{
top = 0;
stack[top++] = Node{ i, 0 };
for (int k = 1; k <= j; k++){
Node tmp{ pre[cc][k], k }; //
while (top && tmp.row >= stack[top - 1].row){
top--;
}
stack[top++] = tmp;
}
return;
}
void Count2(int i, int j, int cc)
{
topr = 0;
stackr[topr++] = Node{ i, m + 1 };
for (int k = m; k >= j; k--){
Node tmp{ pre[cc][k], k }; //
while (topr && tmp.row >= stackr[topr - 1].row){ //
topr--;
}
stackr[topr++] = tmp; //
}
return;
}
int main()
{
int T;
scanf("%d", &T);
while (T--){
init();
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
scanf("%d", &color[i][j]);
}
}
ll ans = 0; //
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
Count(i, j, color[i][j]); // ,
Count2(i, j, color[i][j]); //
int l1 = 0, l2 = 0;
for (int k = i; k > pre[color[i][j]][j]; k--){ //
while (!(stack[l1].row >= k && (l1 + 1 == top||stack[l1 + 1].row < k)))
l1++; //
while (!(stackr[l2].row >= k && (l2 + 1 == topr || stackr[l2 + 1].row < k)))
l2++; //
ans += (ll)(j - stack[l1].col) * (ll)(stackr[l2].col - j) * (ll)(n - i + 1);
// * *
}
pre[color[i][j]][j] = i; // , pre
}
}
printf("%.9lf
", 4.0 * ans / (1.0 * n * (n + 1) * m * (m + 1)));
}
return 0;
}