OTL写manacher的mhy。


我没有那么高端去研究st怎么搞,所以就用了一个二维hash。从四个角各来一遍真是爽翻了。需要注意的是hash的时候行之间和列之间的值要不同才能区别,不然有数据随便可以卡掉。


代码么,巨丑无比。


#include <cstdio>

#include <cctype>

#include <memory.h>

#include <algorithm>


using namespace std;


#define uint _uint_


typedef unsigned long long int uint;


const int maxn = 1009;

const uint bh = 1e9 + 93;

const uint bv = 1e9 + 7;


#define readInt(_s_) {\

int _d_;\

_s_ = 0;\

while (!isdigit(_d_ = getchar()));\

while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\

}


int n, m, a[maxn][maxn];

uint h[4][maxn][maxn], ph[maxn * 2], pv[maxn * 2];


void preHash() {

ph[0] = 1;

pv[0] = 1;

for (int i = 1; i < maxn * 2; ++ i)

ph[i] = ph[i - 1] * bh, pv[i] = pv[i - 1] * bv;

memset(h, 0, sizeof(h));

for (int ti = 0; ti < 4; ++ ti) {

int x0, x1, xd;

if (ti & 2) {

x0 = n;

x1 = 1;

xd = -1;

}

else {

x0 = 1;

x1 = n;

xd = 1;

}

int y0, y1, yd;

if (ti & 1) {

y0 = m;

y1 = 1;

yd = -1;

}

else {

y0 = 1;

y1 = m;

yd = 1;

}

for (int x = x0; x != x1 + xd; x += xd)

for (int y = y0; y != y1 + yd; y += yd)

h[ti][x][y] = h[ti][x - xd][y] * bh + h[ti][x][y - yd] * bv\

  - h[ti][x - xd][y - yd] * bv * bh + (uint)a[x][y];

}

}


inline int getRange(int d, int x0, int y0, int x1, int y1) {

return h[d][x1][y1] - h[d][x0][y1] * ph[abs(x1 - x0)] - h[d][x1][y0] * pv[abs(y1 - y0)]\

+ h[d][x0][y0] * ph[abs(x1 - x0)] * pv[abs(y1 - y0)];

}


int calc(int tx, int ty) {

int x0 = (tx >> 1), x1 = tx - x0;

int y0 = (ty >> 1), y1 = ty - y0;

if (x0 ^ x1)

if (a[x0][y0] != a[x0][y1] || a[x0][y0] != a[x1][y0] || a[x0][y0] != a[x1][y1])

return 0;

int l = 1, r = min(min(x0, n - x1 + 1), min(y0, m - y1 + 1));

while (l < r) {

int mid = (l + r + 1) >> 1;

int h0 = getRange(0, x0 - mid, y0 - mid, x0, y0);

int h1 = getRange(1, x0 - mid, y1 + mid, x0, y1);

int h2 = getRange(2, x1 + mid, y0 - mid, x1, y0);

int h3 = getRange(3, x1 + mid, y1 + mid, x1, y1);

if (h0 != h1 || h1 != h2 || h2 != h3)

r = mid - 1;

else

l = mid;

}

//if (l > 1 || (x0 != x1 && l))

//printf("%d %d %d\n", tx, ty, l);

return l;

}


int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif


readInt(n);

readInt(m);

for (int i = 1; i <= n; ++ i)

for (int j = 1; j <= m; ++ j)

readInt(a[i][j]);

preHash();

int ans = 0;

for (int i = 2; i <= n * 2; ++ i)

for (int j = 2; j <= m * 2; ++ j)

if ((i ^ j ^ 1) & 1)

ans += calc(i, j);

printf("%d\n", ans);

}