哈希 #STL #POI #Year2008

对于每个串做 \(hash\) ，每次操作后只对被影响的等价类更新答案

// Author: xiaruize
int n, l, m;
char s[1005][105];
multiset<ull> st;
ull hsh[1005];
int res[1005];

void solve()
{
	cin >> n >> l >> m;
	rep(i, 1, n) cin >> (s[i] + 1);
	rep(i, 1, n)
	{
		ull val = 0;
		rep(j, 1, l) val = val * 13331ull + s[i][j];
		st.insert(val);
		hsh[i] = val;
	}
	rep(i, 1, n) res[i] = st.count(hsh[i]);
	rep(i, 1, m)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		swap(s[a][b], s[c][d]);
		if (a == c)
		{
			st.erase(st.find(hsh[a]));
			ull val = 0;
			rep(j, 1, l) val = val * 13331ull + s[a][j];
			st.insert(val);
			hsh[a] = val;
			int tmp = st.count(val);
			rep(j, 1, n)
			{
				if (hsh[j] == hsh[a])
					res[j] = max(res[j], tmp);
			}
		}
		else
		{
			st.erase(st.find(hsh[a]));
			st.erase(st.find(hsh[c]));
			ull val = 0;
			rep(j, 1, l) val = val * 13331ull + s[a][j];
			st.insert(val);
			hsh[a] = val;
			val = 0;
			rep(j, 1, l) val = val * 13331ull + s[c][j];
			st.insert(val);
			hsh[c] = val;
			int tmp = st.count(hsh[a]), tmp2 = st.count(hsh[c]);
			rep(j, 1, n)
			{
				if (hsh[j] == hsh[a])
					res[j] = max(res[j], tmp);
				if (hsh[j] == hsh[c])
					res[j] = max(res[j], tmp2);
			}
		}
	}
	rep(i, 1, n) cout << res[i] << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}