QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#946#208934#21696. 【NOIP Round #3】数圈圈yangtb2024zeq2022Failed.2024-10-10 15:25:142024-10-10 15:25:14

詳細信息

Extra Test:

Accepted
time: 0ms
memory: 20032kb

input:

5 5
bbbab
ababa
bbbab
abaaa
aabbb

output:

0

result:

ok "0"

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#208934#21696. 【NOIP Round #3】数圈圈zeq2022100 ✓2875ms210356kbC++144.2kb2023-10-09 22:12:322024-10-23 22:42:46

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n, m;
int a[2005][2005], b[2005][2005];
int suf[2][2005][2005], pre[2][2005][2005];
int L[2005][2005], R[2005][2005];
int D[2005][2005], U[2005][2005];
ll zeq[2][2][2005][2005];

void add0(ll *c, int x, int y) {
	for (; x <= 2000; x += x & -x) c[x] += y;
}

void add1(ll *c, int x, int y) {
	for (; x; x -= x & -x) c[x] += y;
}

ll query0(ll *c, int x) {
	ll res = 0;
	for (; x; x -= x & -x) res += c[x];
	return res;
}

ll query1(ll *c, int x) {
	ll res = 0;
	for (; x <= 2000; x += x & -x) res += c[x];
	return res;
}

ll solve(int ax, int ay, int bx, int by) {
	if (ax >= bx || ay >= by) return 0;
	ll ret = 0;
	if (by - ay >= bx - ax) {
		int mid = (ay + by) >> 1;
		ret = solve(ax, ay, bx, mid) + solve(ax, mid + 1, bx, by);
		for (int i = ax; i <= bx; ++i) {
			int left = max(L[i][mid], ay);
			int right = min(R[i][mid], by);
			for (int j = left; j <= mid; ++j) {
				add1(zeq[0][1][i], D[i][j], 1);
				add0(zeq[0][0][i], U[i][j], 1);
			}
			for (int j = mid + 1; j <= right; ++j) {
				add1(zeq[1][1][i], D[i][j], 1);
				add0(zeq[1][0][i], U[i][j], 1);
			}
		}
		for (int u = ax; u < bx; ++u) {
			int Lu = max(L[u][mid], ay), Ru = min(R[u][mid], by);
			for (int v = u + 1; v <= bx; ++v) {
				int Lv = max(L[v][mid], ay), Rv = min(R[v][mid], by);
				ll L = 0, R = 0;
				if (Lu >= Lv) L = query1(zeq[0][1][u], v);
				else L = query0(zeq[0][0][v], u);
				if (Ru <= Rv) R = query1(zeq[1][1][u], v);
				else R = query0(zeq[1][0][v], u);
				ret += L * R;
			}
		}
		for (int i = ax; i <= bx; ++i) {
			int left = max(L[i][mid], ay);
			int right = min(R[i][mid], by);
			for (int j = left; j <= mid; ++j) {
				add1(zeq[0][1][i], D[i][j], -1);
				add0(zeq[0][0][i], U[i][j], -1);
			}
			for (int j = mid + 1; j <= right; ++j) {
				add1(zeq[1][1][i], D[i][j], -1);
				add0(zeq[1][0][i], U[i][j], -1);
			}
		}
	} else {
		int mid = (ax + bx) >> 1;
		ret = solve(ax, ay, mid, by) + solve(mid + 1, ay, bx, by);
		for (int i = ay; i <= by; ++i) {
			int up = max(U[mid][i], ax);
			int down = min(D[mid][i], bx);
			for (int j = up; j <= mid; ++j) {
				add0(zeq[0][0][i], L[j][i], 1);
				add1(zeq[1][0][i], R[j][i], 1);
			}
			for (int j = mid + 1; j <= down; ++j) {
				add0(zeq[0][1][i], L[j][i], 1);
				add1(zeq[1][1][i], R[j][i], 1);
			}
		}
		for (int u = ay; u < by; ++u) {
			int Uu = max(U[mid][u], ax), Du = min(D[mid][u], bx);
			for (int v = u + 1; v <= by; ++v) {
				int Vu = max(U[mid][v], ax), Dv = min(D[mid][v], bx);
				ll U = 0, D = 0;
				if (Uu >= Vu) U = query1(zeq[1][0][u], v);
				else U = query0(zeq[0][0][v], u);
				if (Du <= Dv) D = query1(zeq[1][1][u], v);
				else D = query0(zeq[0][1][v], u);
				ret += U * D;
			}
		}
		for (int i = ay; i <= by; ++i) {
			int up = max(U[mid][i], ax);
			int down = min(D[mid][i], bx);
			for (int j = up; j <= mid; ++j) {
				add0(zeq[0][0][i], L[j][i], -1);
				add1(zeq[1][0][i], R[j][i], -1);
			}
			for (int j = mid + 1; j <= down; ++j) {
				add0(zeq[0][1][i], L[j][i], -1);
				add1(zeq[1][1][i], R[j][i], -1);
			}
		}
	}
	return ret;
}

int main() {
//	freopen("ex_circle8.in", "r", stdin);
	
	ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            char c;
            cin >> c;
            a[i][j] = c - 'a' + 1;
        }
    
    for (int j = 1; j <= m; ++j) {
    	U[1][j] = 1;
    	for (int i = 2; i <= n; ++i) {
    		if (a[i - 1][j] == a[i][j]) {
    			U[i][j] = U[i - 1][j];
			} else U[i][j] = i;
		}
		D[n][j] = n;
		for (int i = n - 1; i; --i) {
			if (a[i + 1][j] == a[i][j]) {
				D[i][j] = D[i + 1][j];
			} else D[i][j] = i;
		}
	}
	for (int i = 1; i <= n; ++i) {
		L[i][1] = 1;
		for (int j = 2; j <= m; ++j) {
			if (a[i][j - 1] == a[i][j]) {
				L[i][j] = L[i][j - 1];
			} else L[i][j] = j;
		}
		R[i][m] = m;
		for (int j = m - 1; j; --j) {
			if (a[i][j + 1] == a[i][j]) {
				R[i][j] = R[i][j + 1];
			} else R[i][j] = j;
		}
	}
    
    cout << solve(1, 1, n, m);

    return 0;
}
/*
5 5
bbbab
ababa
bbbab
abaaa
aabbb
*/