[POI2018] Różnorodność

题目描述

给定一个 $n$ 行 $m$ 列的矩阵，请对于每个长宽均为 $k$ 的连续子正方形，统计里面出现过的数值的种类数。

$n,m\le3000$ ， $k\le \min(n,m)$ 。

题解

用一个 $n\times k$ 大窗口从左往右滑动，这样相当于把二维化成一维。这样一列增一列减地转移。

再考虑大窗口内的 $k\times k$ 小窗口。对于每个权值，它的贡献很像扫描线，用数据结构维护权值所在的行数，对于当前操作的某行，小窗口的下端刚好够到此行（或者如果在前面 $k$ 内有相同权值，就是小窗口的上端在前面的下一行）、小窗口将走（即上端在此行）的区间就是此行的贡献区间，用差分维护即可。

数据结构用 bitset 就行了，然后发现它虽然有 _Find_next，但没有 _Find_last……遂手打。

复杂度 $\mathcal{O}\left(\frac{nm^2}{\omega}\right)$ 。

代码

bitset 你让我好调哇！！记得左移的 1 开 ull！！！

const int N = 3e3 + 5, M = 1e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m, k;
	int a[N][N];
	int ans1; ll ans2;
	bool Line[N][N];
	int ans[N], nxt[M], cnt[M];
	void update (int x) { ans1 = max(ans1, x), ans2 += x; }
	int c[N];
	void add (int l, int r, int val) {
		if (l > r) return;
		c[l] += val, c[r + 1] -= val;
	}
//	bitset<N> b[M];
	
	struct mybitset {
		unsigned ll arr[N / 64 + 5];
		int test (int p) { return (arr[p >> 6] >> (p & 63)) & 1;}
		void set(int p, int v = 1) {
			if (v) arr[p >> 6] |= (1ull << (p & 63));
			else arr[p >> 6] -= (1ull << (p & 63));
		}
		int _Find_next(int p) {
			int a = p >> 6, b = p & 63;
			for (int i = b + 1; i < 64; ++i) if (arr[a] & (1ull << i)) return p - b + i;
			for (int i = a + 1; i <= N / 64; ++i) 
				if (arr[i]) 
					for (int j = 0; j < 64; ++j) 
						if (arr[i] & (1ull << j)) return (i << 6) + j;
			return n + 1;
		}
		int _Find_last(int p) {
			int a = p >> 6, b = p & 63;
			for (int i = b - 1; i >= 0; --i) if (arr[a] & (1ull << i)) return p - b + i;
			for (int i = a - 1; i >= 0; --i) 
				if (arr[i]) 
					for (int j = 63; j >= 0; --j) 
						if (arr[i] & (1ull << j)) return (i << 6) + j;
			return 0;
		}
	}b[M];

	void get_first_window() {
		int tot = 0;
		for (int i = 1; i <= k; i++) 
			for (int j = 1; j <= k; j++) if ((cnt[a[i][j]]++) == 0) tot++;
		update (ans[1] = tot);
		for (int i = 1; i <= n - k; i++) {
			for (int j = 1; j <= k; j++) tot -= ((--cnt[a[i][j]]) == 0);
			for (int j = 1; j <= k; j++) if ((cnt[a[i + k][j]]++) == 0) tot++;
			update(ans[i + 1] = tot);
		}


		for (int i = 1; i <= M - 5; i++) b[i].set(0), b[i].set(n + 1);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= k; j++) {
				b[a[i][j]].set(i);
			}
	}

	int main () {
		n = Read(), m = Read(), k = Read();
		for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) a[i][j] = Read();
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) nxt[a[i][j]] = m + k + k;
			for (int j = m; j; j--) Line[i][j] = (nxt[a[i][j]] - j <= k), nxt[a[i][j]] = j;
		}
		get_first_window();
		//for (int i = 1; i <= n; i++) printf ("%d ", ans[i]); putchar(10);
		for (int j = 1; j <= m - k; j++) {
			for (int i = 1; i <= n; i++)
				if (!Line[i][j]) {
					int l = b[a[i][j]]._Find_last(i) + 1, r = b[a[i][j]]._Find_next(i) - 1;
					//printf ("[1]%d %d\n", l, r);
					add (max(l, i - k + 1), min(i, r - k + 1), -1);
					b[a[i][j]].set(i, 0);
				}
			for (int i = 1; i <= n; i++)
				if (!b[a[i][j + k]].test(i)) {
					int l = b[a[i][j + k]]._Find_last(i) + 1, r = b[a[i][j + k]]._Find_next(i) - 1;
					//printf ("[2]%d %d\n", l, r);
					add (max(l, i - k + 1), min(i, r - k + 1), 1);
					b[a[i][j + k]].set(i);
				}
			for (int i = 1; i <= n; i++) update(ans[i] += (c[i] += c[i - 1]))/*, printf ("%d ", ans[i]);putchar(10)*/;
			for (int i = 1; i <= n; i++) c[i] = 0;
		}
		printf ("%d %lld\n", ans1, ans2);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}